Ternary Search Tree (Trie with BST of children) Visualization

A trie whose children form a binary search tree

A trie node has one child pointer for every letter of the alphabet, and most of them are null. A ternary search tree (TST, described by Bentley and Sedgewick in 1997) keeps the trie's idea of going one level deeper per letter, but stores the children of a trie node as a small binary search tree of letters. Every node holds one letter (or none yet) and three links:

• = (equal, the green links): this letter matched; continue with the next letter of the word;
• < (less, grey): words that have a smaller letter at this position;
• > (greater, grey): words that have a larger letter at this position.

So the < and > links connect the alternatives for one position of the word (they form a binary search tree ordered by letter), and only an = link moves on to the next position. The edge labels in the animation show the rule and the letter it compares with: <D, =D, >D.

In this visualization, the end of a word is marked on the node that is reached after following the = link of its last letter. That node is green. For CAR the path is C, =, A, =, R, =, and the node reached is green. A node with no letter (an empty circle) is a place where no letter has been stored yet, typically the end of a word. A green node with a letter means two things at once: a word ends just above it, and longer words continue through its letter. The page turns what you type into capital letters and drops everything that is not a letter (up to 12 letters).

Searching

Compare the first remaining letter of the word with the letter at the node. If they are equal, drop that letter and follow =. If the word's letter is smaller, follow <, and if it is larger, follow >, keeping the letter. When the word runs out, the word is stored exactly when the node reached is green.

find(node, s):                            // s = the letters not matched yet
    if node is null:
        return false                      // fell off the tree
    if s is empty:
        return node.isWord                // the word ended just above this node
    if node.letter is empty:
        return false                      // no word continues from here
    if s[0] == node.letter:
        return find(node.equal, s[1..])   // matched: go on with the next letter
    if s[0] < node.letter:
        return find(node.less, s)         // same position, smaller letter
    else:
        return find(node.greater, s)      // same position, larger letter

Inserting

Insertion makes the same moves, creating nodes where the search would fall off. A new node starts without a letter; the first word that reaches it with letters left stores its next letter there and creates an empty = child for the letter after that. When the word runs out, the node reached is marked.

insert(node, s):                          // the root is created (empty) first
    if s is empty:
        node.isWord = true                // turn it green
        return
    if node.letter is empty:              // take this node for the letter s[0]
        node.letter = s[0]
        node.equal = new empty node
        insert(node.equal, s[1..])
    else if s[0] == node.letter:
        insert(node.equal, s[1..])
    else if s[0] < node.letter:
        if node.less is null: node.less = new empty node
        insert(node.less, s)
    else:
        if node.greater is null: node.greater = new empty node
        insert(node.greater, s)

Deleting

Find the word and clear its mark. Then remove the nodes that are no longer needed, from the bottom up. A node is still needed if it has an = child (longer words pass through its letter) or if it is a green leaf. An unmarked leaf is removed; if it was its parent's = child, the parent's letter is no longer used by any word, so the letter is cleared and the parent is checked in turn. A node whose letter is unused but which still has < or > children is taken out of its binary search tree of letters exactly as in a BST deletion.

delete(word):
    node = the node where find(word) ends
    if node is null or not node.isWord:
        return                            // not stored: nothing to do
    node.isWord = false
    cleanup(node)

cleanup(node):
    if node.equal is not null:
        return                            // other words go through this letter
    if node has no children:
        if node.isWord: return            // a word still ends here
        remove node from its parent
        if node was its parent's = child:
            clear the parent's letter
        cleanup(parent)
    else:                                 // only < and/or > children: take it out of its BST
        if node has one child:
            r = that child
        else:
            r = the largest node in node.less  // its predecessor
            move r to node's place
        put r where node was
        if node.isWord: r.isWord = true   // the node now first on the = path keeps the mark

The last line matters because a word's mark is always on the first node below an = link (or on the root). When that node is replaced, the node taking its place becomes the first node there, so it has to take over the mark.

A worked example

Insert CAR, CAT, CART, DOG and CA into an empty tree. Each line is a node: the link that leads to it, its letter in brackets ([ ] for none), and * if it is green:

insert CAR     insert CAT     insert CART    insert DOG     insert CA
[C]            [C]            [C]            [C]            [C]
 =[A]           =[A]           =[A]           =[A]           =[A]
   =[R]           =[R]           =[R]           =[R]           =[R]*
     =[ ]*          =[ ]*          =[T]*          =[T]*          =[T]*
                    >[T]             =[ ]*          =[ ]*          =[ ]*
                      =[ ]*        >[T]           >[T]           >[T]
                                     =[ ]*          =[ ]*          =[ ]*
                                             >[D]           >[D]
                                               =[O]           =[O]
                                                 =[G]           =[G]
                                                   =[ ]*          =[ ]*

1. CAR: the empty root takes C, its new = child takes A, the next one R, and the empty node after R is marked.
2. CAT: C and A match. At R, T is larger, so a > child is created; it takes T, and the node after it is marked. R and T are now the two letters that can follow CA.
3. CART: C, A, R match and the search reaches the green end node of CAR with T left. That node has no letter, so it takes T; it stays green because CAR still ends there.
4. DOG: D is larger than C, so it goes into a new > child of the root, followed by O, G and a marked empty node.
5. CA: after C and A the word is used up at the node R, which is simply marked: no new node is needed for a word that is a prefix of stored words.

Now find C: after C the node reached is A, which is not green: not found. CAB: at R, B is smaller and there is no < child: not found. CARTS: after CART the empty green node has no letter to compare S with: not found.

Delete CAR: its mark on T is cleared, and T has an = child, so nothing else changes. Delete CART: the empty node after T is an unmarked leaf and is removed; T loses its letter and, now an unmarked leaf, is removed too; R loses its letter. R still has the > child T (from CAT), so it is taken out of the letter BST: T takes its place and also its green mark, because CA is still a word. The tree is now C =A =T* =[ ]* plus the DOG branch.

Print visits a node's word first, then the <, = and > subtrees, so the words come out in alphabetical order. New random tree builds a tree from 10 to 50 random made-up words, listed below the tree in the order they are inserted.

Why it works

Take all the nodes that can be reached from one node by < and > links only: they hold different letters, ordered like a binary search tree, and together they are exactly the children of one node of the corresponding trie. Following an = link is following the trie edge for that letter. So a TST search walks the trie path of the word, finding each letter with a binary search among the possible letters at that position, and the mark placed after the last = link plays the role of the trie's word-end flag. Deletion keeps every letter BST a valid binary search tree, which is why it uses the usual BST deletion cases.

Unlike a trie, the shape depends on the insertion order: the first word to reach a position becomes the root of that position's letter BST.

Running time and space

A search for a word of length L follows L = links, plus the < and > steps inside the letter BSTs. With an alphabet of σ letters (26 here), each of those BSTs has at most σ nodes, so the worst case is O(L σ). That happens when words arrive in alphabetical order: every letter BST becomes a chain. When the words are inserted in random order, the letter BSTs are about balanced and a search costs about L + O(log n) comparisons for n words. Insertion and deletion follow the same path, plus constant work per node (and the predecessor walk of a BST deletion).

A TST has one node per letter position that a trie would have (plus, in this version, at most one empty end node per word), but each node needs only 3 links instead of 26. That makes it much smaller than an array-based trie while keeping prefix queries and ordered output. A hash table is faster on exact lookups (O(L) expected) but has no order and no prefix search. A balanced BST of whole strings takes O(L log n), because it may re-read the same leading letters at every level; a TST never compares a letter of the word that has already been matched.

Common mistakes and edge cases

• Only = consumes a letter. Going < or > keeps the same letter of the word; a search that drops a letter on a side link looks in the wrong place.
• A word that is a prefix of another (CA, CAR): its mark sits on a node that also has a letter. Marks are flags, not leaves.
• Deleting must not lose other words: stop at nodes with an = child or with a mark, and when a node is replaced in its letter BST, move its mark to the replacement.
• Tall trees: words inserted in sorted order make long </> chains. Inserting in random order, or the middle word of a sorted list first, keeps the tree shallow.
• Other conventions: many textbooks mark the node holding the last letter instead of the node after it. That saves the empty end nodes but needs a special case for the empty string, which this page does not accept.

Uses

Ternary search trees are a compact symbol table for strings: they support exact lookups, autocomplete (find the node for the prefix, then list the words in its = subtree in order), spell checking, partial-match queries such as C?T (at a wildcard, explore all three links), and near-neighbour search for words within a given number of differing letters. They are a good choice when the alphabet is large (Unicode) and a 26- or 65536-way array per node would waste memory.

References

Ternary search tree