Ternary Search Tree

A ternary search tree is a cross between a trie and a binary search tree. It has the same function as a trie, but takes up way less space.

In a trie, each node stores a single letter along with links to nodes for other letters that can come next.

How much space does a trie node take up?

It depends on the number of links we store. If we're using our trie to store English words, each node could have 26 forward links—one for each letter:

This means we need to set aside space for lots of links in each node, even though we'll usually only need a few of them. We're wasting space!

Ternary search trees to the rescue!

In a ternary search tree, each node has space for three links:

• The center link points to a node with a letter that follows the current node's letter.
• The left link points to a node with a letter that is earlier in the alphabet than the current node's letter.
• The right link points to a node with a letter that is later in the alphabet than the current node's letter.

To see this in action, let's take a trie and build up an equivalent ternary search tree.

We'll work with this trie:

To start off, let's add Maria to our ternary search tree:

So far, looks a lot like a trie. Let's add David next.

Since D comes before M, the left link of the "M" node connects to the new "D" node.

What happens if we add in Mario?

We can reuse the first four nodes from Maria. For the last node, since O comes after A, the right link of the "A" node connects to the new "O" node.

Let's add a few more names:

• Mary: We can reuse the first three nodes from Maria. Then, since Y comes after I, the right link of the "I" node connects to the new "Y" node.

  

• Dan: Keep the first two nodes from David, and then add a new left link to the "V" node connecting to a new "N" node.

  

• Martina: Take the first three nodes from Maria. Then, since T comes after I, the new "T" node has to fall to the right of the "I" node.

  Here's where things get tricky. There's already a right link on the "I" node, connecting to a "Y" node (from Mary). We can't add another right link to the "I" node, since we only have room for three links.

  Instead, let's look at the "Y" node. Since T comes before Y, and the "Y" node doesn't already have a left link, we can use add one connecting to our new "T" node.

  

• Mariana: Use all five nodes from Maria. Then, add a center link to the "A" node at the end of Maria connecting it to the new "N" node.

All together, here's what we've got:

At first glance, it looks like ternary search trees take up about the same amount of space as tries, since they have roughly the same number of nodes. But remember, each ternary search tree node has space for just three links to other nodes, making them much smaller than trie nodes with space for at least 26 links. This means we're saving a lot of space by using a ternary search tree instead of a trie.