Ternary search tree versus array tries

Why this matters

The first lesson in this module built a trie with an array of 26 slots in every node. One slot per letter makes lookups fast, because the next node for letter c is found with one index, next[c - 'a']. The cost is memory. A node that only ever uses the letter x still carries 26 slots, and 25 of them stay empty.

A ternary search tree (TST) is a different layout. Each node holds one letter and three links instead of 26. It stores the same words with much less memory, and the price is that each letter takes a few more steps to find. This lesson builds both structures, runs them on the same 50,000 words, and measures the difference in memory and in time.

The radix tree lesson earlier in this module shrinks a trie by joining letters into longer edges. A TST takes another route. It keeps one letter per node, so it is still a trie-like tree, but the links are arranged differently.

The two layouts

Picture an array trie node as a row of 26 mailboxes, one for each letter. Each mailbox holds the number of the next node, or -1 when the mailbox is empty. Looking up a letter means opening one mailbox. The row is always 26 mailboxes long, whether two of them are used or twenty-six.

A TST node holds one letter and three links:

• eq points to the node for the next letter of the word. You follow it after the letter in this node matches.
• lo points to a node for a smaller letter. It sits at the same position in the word, so it is a sibling.
• hi points to a node for a larger letter, also a sibling.

Each node also has an end flag. It is true when the word ends at this letter.

To find a letter, you start at a node. If the letter you want is smaller than the node's letter, you follow lo. If it is larger, you follow hi. If it matches, you follow eq and move to the next letter of the word. The siblings form a small binary search tree over the letters that appear at that position. This is why the structure is called ternary: each node has three children.

Building a small TST step by step

Insert four words in this order: cat, cab, dog, do. Each step below names the node that is created or changed.

1. Insert cat. The tree is empty, so c becomes the first node. a is the eq link of c, and t is the eq link of a. The t node gets end set to true, because cat ends there.
2. Insert cab. Start at c, which matches, and follow eq to a, which also matches. The next letter is b. The node for a links eq to t, and b is smaller than t, so b becomes the lo link of t. The b node gets end set to true.
3. Insert dog. Start at c. The letter d is larger than c, so d becomes the hi link of c. Then o follows eq from d, and g follows eq from o. The g node gets end set to true.
4. Insert do. Start at c, follow hi to d, then eq to o. The word ends at o, so o gets end set to true.

The dump method in the class below prints every node. This is the output for the four words above, with one line per node:

0: ch=c lo=-1 eq=1 hi=4 end=false
1: ch=a lo=-1 eq=2 hi=-1 end=false
2: ch=t lo=3 eq=-1 hi=-1 end=true
3: ch=b lo=-1 eq=-1 hi=-1 end=true
4: ch=d lo=-1 eq=5 hi=-1 end=false
5: ch=o lo=-1 eq=6 hi=-1 end=true
6: ch=g lo=-1 eq=-1 hi=-1 end=true
contains do: true
contains ca: false
contains dogs: false

Read line 2 as "node 2 holds t. Its lo link goes to node 3, which holds b. It has no eq or hi link. The word ends here." Line 4 holds d and is the hi link of node 0. The -1 values mean there is no link.

Notice that ca is false even though c and a are both on the tree. The a node has end set to false, because no stored word ends at ca. Prefixes and words are different things, and the flag is what separates them.

The TST code

The code below stores nodes in a vector. Links are indexes into that vector, not pointers. A vector can move its items to a new place in memory when it grows, and a pointer would then point at old memory. An index stays valid after the move.

class TernarySearchTree {
public:
    void insert(string_view word) {
        if (word.empty()) return;
        root_ = insert_at(root_, word, 0);
    }
 
    bool contains(string_view word) const {
        if (word.empty()) return false;
        int idx = root_;
        size_t pos = 0;
        while (idx != -1) {
            const Node& n = nodes_[idx];
            char c = word[pos];
            if (c < n.ch) {
                idx = n.lo;
            } else if (c > n.ch) {
                idx = n.hi;
            } else {
                if (pos + 1 == word.size()) return n.end;
                ++pos;
                idx = n.eq;
            }
        }
        return false;
    }
 
    size_t node_count() const { return nodes_.size(); }
    size_t bytes() const { return nodes_.size() * sizeof(Node); }
 
    void dump() const {
        for (size_t i = 0; i < nodes_.size(); ++i) {
            const Node& n = nodes_[i];
            cout << i << ": ch=" << n.ch << " lo=" << n.lo << " eq=" << n.eq
                 << " hi=" << n.hi << " end=" << n.end << "\n";
        }
    }
 
private:
    struct Node {
        char ch;
        int lo = -1;
        int eq = -1;
        int hi = -1;
        bool end = false;
    };
    vector<Node> nodes_;
    int root_ = -1;
 
    int make_node(char c) {
        nodes_.push_back(Node{.ch = c});
        return static_cast<int>(nodes_.size()) - 1;
    }
 
    int insert_at(int idx, string_view word, size_t pos) {
        if (idx == -1) idx = make_node(word[pos]);
        char c = word[pos];
        if (c < nodes_[idx].ch) {
            int child = insert_at(nodes_[idx].lo, word, pos);
            nodes_[idx].lo = child;
        } else if (c > nodes_[idx].ch) {
            int child = insert_at(nodes_[idx].hi, word, pos);
            nodes_[idx].hi = child;
        } else if (pos + 1 < word.size()) {
            int child = insert_at(nodes_[idx].eq, word, pos + 1);
            nodes_[idx].eq = child;
        } else {
            nodes_[idx].end = true;
        }
        return idx;
    }
};

insert_at is recursive. It returns the index of the node it was given, or of the new node it made. The caller stores that index in its own lo, hi or eq link. This way a new node is attached without any pointer to a vector item.

The small program below builds the tree from the four words and prints the dump and three checks. It uses the class above, and the Node{.ch = c} designated initializer needs C++20, so compile with -std=c++20. The boolalpha flag makes end and the contains results print as true or false.

int main() {
    cout << boolalpha;
    TernarySearchTree t;
    for (string_view w : {"cat", "cab", "dog", "do"}) t.insert(w);
    t.dump();
    cout << "contains do: " << t.contains("do") << "\n";
    cout << "contains ca: " << t.contains("ca") << "\n";
    cout << "contains dogs: " << t.contains("dogs") << "\n";
}

The array trie for comparison

The second class is the 26-slot trie from the first lesson of this module, with the same interface. It is short because the structure is simple.

class ArrayTrie {
public:
    ArrayTrie() { nodes_.push_back(Node{}); }
 
    void insert(string_view word) {
        if (word.empty()) return;
        int cur = 0;
        for (char c : word) {
            int slot = c - 'a';
            if (nodes_[cur].next[slot] == -1) {
                nodes_.push_back(Node{});
                nodes_[cur].next[slot] = static_cast<int>(nodes_.size()) - 1;
            }
            cur = nodes_[cur].next[slot];
        }
        nodes_[cur].end = true;
    }
 
    bool contains(string_view word) const {
        if (word.empty()) return false;
        int cur = 0;
        for (char c : word) {
            cur = nodes_[cur].next[c - 'a'];
            if (cur == -1) return false;
        }
        return nodes_[cur].end;
    }
 
    size_t node_count() const { return nodes_.size(); }
    size_t bytes() const { return nodes_.size() * sizeof(Node); }
 
private:
    struct Node {
        array<int, 26> next;
        bool end = false;
        Node() { next.fill(-1); }
    };
    vector<Node> nodes_;
};

Comparing both on 50,000 words

The benchmark builds both structures from the same list of 50,000 random lowercase words, each 4 to 10 letters long. A simple random number generator makes the list the same on every run. It then looks up every stored word, and then 50,000 words from a second list that mostly are not stored. The main function, with the parts that matter, is below.

vector<string> make_words(size_t count, uint32_t seed) {
    uint32_t state = seed;
    auto next = [&state]() {
        state = state * 1664525u + 1013904223u;
        return state >> 8;
    };
    vector<string> words;
    words.reserve(count);
    for (size_t i = 0; i < count; ++i) {
        size_t len = 4 + next() % 7;
        string w;
        for (size_t k = 0; k < len; ++k) {
            w.push_back(static_cast<char>('a' + next() % 26));
        }
        words.push_back(w);
    }
    return words;
}
 
int main() {
    vector<string> words = make_words(50000, 12345);
    vector<string> misses = make_words(50000, 999);
 
    ArrayTrie arr;
    TernarySearchTree tst;
    for (const string& w : words) {
        arr.insert(w);
        tst.insert(w);
    }
 
    cout << "words inserted: " << words.size() << "\n";
    cout << "array trie: nodes " << arr.node_count() << ", bytes " << arr.bytes() << "\n";
    cout << "ternary tree: nodes " << tst.node_count() << ", bytes " << tst.bytes() << "\n";
 
    auto time_lookups = [](const vector<string>& queries, auto&& lookup) {
        auto start = chrono::steady_clock::now();
        size_t hits = 0;
        for (const string& q : queries) {
            if (lookup(q)) ++hits;
        }
        auto end = chrono::steady_clock::now();
        auto us = chrono::duration_cast<chrono::microseconds>(end - start).count();
        return pair{hits, us};
    };
 
    auto [arr_hits, arr_us] = time_lookups(words, [&](const string& q) { return arr.contains(q); });
    auto [tst_hits, tst_us] = time_lookups(words, [&](const string& q) { return tst.contains(q); });
    cout << "stored words found: array " << arr_hits << " in " << arr_us
         << " us, ternary " << tst_hits << " in " << tst_us << " us\n";
 
    auto [arr_m, arr_mus] = time_lookups(misses, [&](const string& q) { return arr.contains(q); });
    auto [tst_m, tst_mus] = time_lookups(misses, [&](const string& q) { return tst.contains(q); });
    cout << "second list found: array " << arr_m << " in " << arr_mus
         << " us, ternary " << tst_m << " in " << tst_mus << " us\n";
 
    size_t mismatches = 0;
    for (const string& q : misses) {
        if (arr.contains(q) != tst.contains(q)) ++mismatches;
    }
    cout << "mismatches between the two structures: " << mismatches << "\n";
}

make_words uses a fixed seed, so every run builds the same words. The program also starts with the includes <array>, <chrono>, <cstdint>, <iostream>, <string>, <string_view> and <vector>, and using namespace std;, followed by both classes above. This is the output of one run, with the benchmark lines:

words inserted: 50000
array trie: nodes 214407, bytes 23155956
ternary tree: nodes 214406, bytes 4288120

The two structures have almost the same number of nodes. Each distinct prefix of the stored words gets one node in both structures. The array trie has one extra node, the root, which has no letter. The TST has no root node, so it has one fewer.

The memory is very different. The array trie uses 108 bytes for each node, and the TST uses 20 bytes. On this machine with g++ 15 on 64-bit Linux, the array node holds 26 int slots (104 bytes), a bool, and padding up to 108. The TST node holds one char, three int links, and a bool, which fits in 20 bytes. The totals are 214,407 times 108, which is 23,155,956 bytes, and 214,406 times 20, which is 4,288,120 bytes. The TST uses about 5.4 times less memory on this data.

The timings came from two runs on the same machine. The stored-word timings swapped order between the runs, so read the pattern, not the exact values.

run 1
stored words found: array 50000 in 5400 us, ternary 50000 in 10979 us
second list found: array 123 in 6131 us, ternary 123 in 13442 us
mismatches between the two structures: 0
 
run 2
stored words found: array 50000 in 21670 us, ternary 50000 in 11523 us
second list found: array 123 in 5988 us, ternary 123 in 13512 us
mismatches between the two structures: 0

The numbers are in microseconds, where 1000 microseconds is one millisecond. Both runs show the same pattern for the second list. Most of these words are not stored, so the lookup has to fail. The array trie fails when it reaches a slot that is -1. The TST has to follow a chain of siblings at each letter and compare the letter with each one. On this data the TST took about two times longer for failed lookups. The two structures gave the same answer for all 50,000 words, which is what the mismatch count of zero shows.

The exact microseconds are not the lesson. They depend on the machine, the compiler options and what else is running. The lesson is the trade. The TST uses far less memory, and every letter costs a few more comparisons.

Tracing three lookups

The dump from the small tree shows how the walk moves. Each step is one visit to a node. In a visit, the walk compares the letter it wants with the node's letter, then follows lo, hi or eq.

Look up cab. Visit node 0, which holds c. The letter matches, and cab has more letters, so the walk follows eq to node 1, which holds a. That matches too, so it follows eq to node 2, which holds t. The wanted letter is b, which is smaller than t, so the walk follows lo to node 3. That node holds b, and it is the last letter of cab. Its end flag is true, so the answer is true. The walk made four visits.

Look up dogs. Visit node 0. The letter d is larger than c, so the walk follows hi to node 4, which holds d. The letter matches, so it follows eq to node 5, which holds o, and then eq to node 6, which holds g. The word dogs still has an s left, so the walk follows eq from g. That link is -1, the loop stops, and the answer is false. The walk made four visits and found that dogs has no path.

Look up ca. Visit node 0 and follow eq to node 1, which holds a. The letter matches and it is the last letter, so the answer is the end flag of node 1. The flag is false, which is why ca is not a word.

In an array trie, the same three lookups take one index per letter, with no sibling checks. The TST pays for the saved memory with the extra visits and comparisons that you can count in these traces.

When a TST is the better choice

A TST is worth considering when the alphabet is large, such as all of Unicode, because an array of one slot per possible character would be huge. Each TST node holds only one character, so the cost does not grow with the alphabet size. The cost grows with the number of siblings at a position instead.

An array trie is the better choice when the alphabet is small and lookups must be as fast as possible. Lowercase English letters give 26 slots, which is a small price for a single index per letter. A program that makes many lookups on a small alphabet usually gains more from speed than it loses in memory.

Both structures keep the words in no particular order. If you need the words in sorted order, or a list of all words that start with a prefix, you walk the tree. The walk is similar in both structures, so the choice does not change that part of the code.

Common mistakes

Using a letter outside a to z in the array trie

The array trie turns a letter into a slot with c - 'a'. An uppercase letter gives a negative number, and std::array does not check the index unless the library is built with checks turned on. Calling contains on "Banana" with the array trie from this lesson reads index 'B' - 'a', which is -31. With the assertion checks of the standard library turned on, the program stops with this message:

/usr/include/c++/15/array:219: constexpr const std::array<_Tp, _Nm>::value_type& std::array<_Tp, _Nm>::operator[](size_type) const [with _Tp = int; long unsigned int _Nm = 26; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The fix is to lower-case the word before the lookup, or to reject letters outside a to z before the index is used. Without the checks, the program may read other memory and give a wrong answer without any message.

Listing designated fields out of order

Designated initializers, such as Node{.ch = c}, must list the fields in the order they are declared. Writing .end before .ch gives this error with g++:

bug_designator.cpp:6:48: error: designator order for field ‘Node::ch’ does not match declaration order in ‘Node’
    6 |     nodes.push_back(Node{.end = true, .ch = 'a'});
      |                                                ^

The fix is to write the fields in declaration order, or to set only the one field you need.

Keeping a reference into the vector while inserting

It is tempting to write Node& n = nodes_[idx]; and then call make_node while n is still in use. make_node calls push_back, which can move every node to new memory. The reference then points at memory that no longer holds the node, and the program may crash or silently write to the wrong place. The code in this lesson stores indexes and reads nodes_[idx] again after each call that can grow the vector. This error does not give a message on every run, so it is easy to miss in testing.

Setting end on the wrong node

The end flag marks the letter where a word stops. If you set it on the first letter of a word, every prefix of that word becomes a stored word. For example, setting end on the c node after inserting cat would make contains("c") return true. The check is simple: insert one word and test the word, its prefix and a longer word. A correct tree gives true, false and false.

Comparing the wrong link on a mismatch

When the letter is smaller, the search must follow lo. When it is larger, it must follow hi. Swapping the two does not crash. The search then walks the wrong branch and reports that stored words are missing. The mismatch count in the benchmark is a good check, because it compares the TST against the array trie on the same queries.

Practice

Exercise 1: Draw the tree

Insert bat and then bad into an empty TST. Which node holds d, and which link leads to it?

Show the answer

The first letter is b, and it becomes the root. a is its eq link, and t is the eq link of a. When bad is inserted, d is smaller than t, so d becomes the lo link of t. The d node holds the end flag, and the t node also holds it because bat is a word. The node for d is reached from the t node through lo.

Exercise 2: Bytes per node

The benchmark output says the array trie used 23,155,956 bytes for 214,407 nodes. How many bytes is each node? Use the same calculation for the TST with 4,288,120 bytes and 214,406 nodes.

Show the answer

For the array trie, 23,155,956 divided by 214,407 is 108. For the TST, 4,288,120 divided by 214,406 is 20. The TST node is about one-fifth the size, which is where the 5.4 times figure comes from.

Exercise 3: A prefix is not a word

After inserting only cat, what do contains("ca"), contains("cat") and contains("cats") return?

Show the answer

They return false, true and false. ca is a prefix of cat, but its last node does not have end set. cat is stored, so it returns true. cats has an extra letter that was never stored.

Exercise 4: Count the nodes for one word

Insert only the word hello into each structure. How many nodes does each one have? The array trie counts its root too.

Show the answer

The TST has 5 nodes, one for each letter. The array trie has 6 nodes, the root plus one for each letter. This is the same one-extra-node difference seen in the benchmark.

Exercise 5: Explain the slow failed lookups

Why does the TST take longer than the array trie to report that a word is missing, even though both trees hold the same words?

Show the answer

The array trie reads one slot for each letter. If the slot is empty, the lookup stops at once. The TST at each letter has to compare the letter with the node it reaches, and then with its siblings through lo and hi, before it knows that no link matches. A failed lookup can therefore cost several comparisons on each letter, and the sibling chain can be up to 26 long at one position.

Summary

• A ternary search tree node holds one letter and three links: eq for the next letter, and lo and hi for siblings with smaller and larger letters.
• The TST in this lesson used 20 bytes per node and the array trie used 108 bytes per node on the same 50,000 words, about 5.4 times less memory.
• Both structures built nearly the same number of nodes, because each new letter at a position creates one node in either layout.
• Lookups in the TST take more comparisons per letter, and failed lookups were about two times slower in this benchmark.
• Store links as indexes into a vector, not as pointers into it, because the vector can move its items when it grows.
• Check a new tree against a simple one on the same queries, and count the mismatches.