Why it matters
The array trie from the first lesson of this module is simple and fast. Each node has 26 slots, one for each letter, and a lookup is one list index per character. The cost is space. A node that only ever needs one child still reserves all 26 slots, and most of those slots stay empty. For 10,000 words, that waste is about a million unused slots.
A ternary search tree, written TST, is a different design that keeps the same idea of walking down one letter at a time, but gives each node only three links. The price is speed, because a lookup sometimes has to move sideways before it moves down. This lesson builds both structures in Python, runs them on the same words, and measures what each one costs. A link here means a reference, a variable that points to another object. A reference slot is one place in memory that holds such a link. Counting reference slots is the simplest honest way to compare memory, and the lesson uses it for that reason.
Start with the waste
Take a node for the letter q in a list of English words. In English, q is almost always followed by u. So the node for q has one child that is used and 25 slots that are not. That is fine for one node. Across a whole dictionary it adds up to a lot of empty space.
The program later in this lesson makes the point with numbers. It inserts 10,000 random lowercase words into an array trie. The trie has about 43,000 nodes, counting the root, and each node has 26 slots. That gives about 1.1 million reference slots.
Every node except the root is the child of exactly one parent, and each parent-to-child link uses one slot. So only about 43,000 of those 1.1 million slots are in use, and the rest are empty, which is about 96 percent. This share does not depend on the words. In any array trie with 26 slots per node, about 1 slot in 26 is in use. Random letters are not English, so real words would share more prefixes and have fewer nodes, but the empty share would stay about the same.
The idea: one letter and three links per node
A TST node holds four things.
ch: the one letter this node stands for.mid: the node for the next letter of the word, one level down.left: a node in the same level whose letter is smaller thanch.right: a node in the same level whose letter is larger thanch.
It also has the end-of-word flag, is_word, the same as in the array trie.
The left and right links turn each level into a small sorted tree. At one level, the letters that follow the same prefix are arranged like a binary search tree. The mid link moves down one level, to the next letter of the word.
Build a TST for three words. First insert cat. The root is a node for c. Its mid link points to a node for a, whose mid link points to a node for t. The t node has is_word set, because cat ends there.
Next insert car. Start at the c node. It matches, so move down with mid to the a node. It matches again. Now compare the next letter, r, with the t node at this level. r is smaller than t, so follow left. There is no node there yet, so create one for r and set its is_word flag, because car ends there.
Last insert dog. Start at c. The letter d is larger than c, so follow right. There is no node there, so create one for d. Then mid leads to a new o node and then to a new g node, which is marked as a word end.
Here is the same tree drawn as text. A * marks a node where a word ends.
Level 1: c ----right----> d
| |
mid mid
v v
Level 2: a o
| |
mid mid
v v
Level 3: r* <--left-- t* g*Look at level 3. The node t* has a left link to r*, because r is smaller than t. The c node has a right link to d, because d is larger than c. Each node has at most one left, one mid and one right link. That is the three links the name refers to.
Searching the tree
A search for a word follows the same rule as the insert. Start at the root with the first letter. At each node, compare the letter you want with ch.
- If the letter is smaller, follow
leftand keep the same letter. - If the letter is larger, follow
rightand keep the same letter. - If the letter matches and it is the last letter, the answer is the node's
is_wordflag. - If the letter matches and more letters follow, follow
midand move to the next letter. - If the link you need is empty, the word is not stored.
Take the search for dot in the tree above. The root c does not match d, and d is larger, so follow right to d. It matches. Two letters are left, so follow mid to o. It matches, and one letter is left. Follow mid to g. The letter t is larger than g, so follow right from g. That link is empty, so the answer is no. The path dot does not exist.
The program: a worked example with five words
The first example used three words. The next one uses the five words cat, car, card, care and dog. It is also the first program in this lesson, so every part of it is listed. It builds a TST and an array trie with the same words and prints the nodes of the TST.
Save the code as tst_demo.py, then run it with python3 tst_demo.py.
import random
import sys
import time
class TstNode:
def __init__(self, ch):
self.ch = ch
self.left = None
self.mid = None
self.right = None
self.is_word = False
class TernarySearchTree:
def __init__(self):
self.root = None
self.node_count = 0
def insert(self, word):
if len(word) == 0:
raise ValueError("empty word")
self.root = self._insert(self.root, word, 0)
def _insert(self, node, word, i):
c = word[i]
if node is None:
node = TstNode(c)
self.node_count += 1
if c < node.ch:
node.left = self._insert(node.left, word, i)
elif c > node.ch:
node.right = self._insert(node.right, word, i)
elif i < len(word) - 1:
node.mid = self._insert(node.mid, word, i + 1)
else:
node.is_word = True
return node
def contains(self, word):
if len(word) == 0:
return False
node = self.root
i = 0
while node is not None:
c = word[i]
if c < node.ch:
node = node.left
elif c > node.ch:
node = node.right
elif i < len(word) - 1:
node = node.mid
i += 1
else:
return node.is_word
return False
def with_prefix(self, prefix):
out = []
if len(prefix) == 0:
return out
node = self.root
i = 0
while node is not None:
c = prefix[i]
if c < node.ch:
node = node.left
elif c > node.ch:
node = node.right
elif i < len(prefix) - 1:
node = node.mid
i += 1
else:
if node.is_word:
out.append(prefix)
self._collect(node.mid, prefix, out)
return out
return out
def _collect(self, node, path, out):
if node is None:
return
self._collect(node.left, path, out)
here = path + node.ch
if node.is_word:
out.append(here)
self._collect(node.mid, here, out)
self._collect(node.right, path, out)
def print_links(self):
self._print_links(self.root)
def _print_links(self, node):
if node is None:
return
self._print_links(node.left)
left = "-" if node.left is None else node.left.ch
mid = "-" if node.mid is None else node.mid.ch
right = "-" if node.right is None else node.right.ch
print(f"node {node.ch} left={left} mid={mid} right={right} word={node.is_word}")
self._print_links(node.mid)
self._print_links(node.right)
class ArrayTrie:
class Node:
def __init__(self):
self.children = [None] * 26
self.is_word = False
def __init__(self):
self.root = ArrayTrie.Node()
self.node_count = 1
def insert(self, word):
node = self.root
for ch in word:
i = ord(ch) - ord("a")
if node.children[i] is None:
node.children[i] = ArrayTrie.Node()
self.node_count += 1
node = node.children[i]
node.is_word = True
def contains(self, word):
node = self.root
for ch in word:
node = node.children[ord(ch) - ord("a")]
if node is None:
return False
return node.is_word
def random_words(count, seed):
rng = random.Random(seed)
words = []
for _ in range(count):
length = 3 + rng.randrange(8)
words.append("".join(chr(ord("a") + rng.randrange(26)) for _ in range(length)))
return words
def time_lookups(structure, words, reps):
hits = 0
start = time.perf_counter_ns()
for _ in range(reps):
for w in words:
if structure.contains(w):
hits += 1
elapsed = time.perf_counter_ns() - start
if hits != len(words) * reps:
raise AssertionError("missed a stored word")
return elapsed
print("== Part 1: five words ==")
small = ["cat", "car", "card", "care", "dog"]
tst = TernarySearchTree()
arr = ArrayTrie()
for w in small:
tst.insert(w)
arr.insert(w)
print("TST nodes:", tst.node_count)
print("array trie nodes:", arr.node_count)
tst.print_links()
print("contains car:", tst.contains("car"))
print("contains ca:", tst.contains("ca"))
print("withPrefix ca:", tst.with_prefix("ca"))
print("withPrefix do:", tst.with_prefix("do"))
print("withPrefix x:", tst.with_prefix("x"))
print()
print("== Part 2: 10,000 random words ==")
words = random_words(10_000, 42)
big_tst = TernarySearchTree()
big_arr = ArrayTrie()
for w in words:
big_tst.insert(w)
big_arr.insert(w)
t_nodes = big_tst.node_count
a_nodes = big_arr.node_count
print(f"TST nodes: {t_nodes}, reference slots: {t_nodes * 3}")
print(f"array trie nodes: {a_nodes}, reference slots: {a_nodes * 26}")
checked = 0
for p in ["a", "ab", "qu", "zz", "k", "mo"]:
expected = [w for w in sorted(set(words)) if w.startswith(p)]
if expected != big_tst.with_prefix(p):
raise AssertionError("prefix mismatch for " + p)
checked += 1
print("prefix checks against a sorted list:", checked, "passed")
print('words under "ab":', len(big_tst.with_prefix("ab")))
print()
print("== Part 3: lookup time (one run, this machine) ==")
time_lookups(big_tst, words, 2)
time_lookups(big_arr, words, 2)
reps = 20
tst_ns = time_lookups(big_tst, words, reps)
arr_ns = time_lookups(big_arr, words, reps)
lookups = len(words) * reps
print(f"TST: {tst_ns / lookups:.1f} ns per lookup")
print(f"array trie: {arr_ns / lookups:.1f} ns per lookup")The output from one run is:
== Part 1: five words ==
TST nodes: 9
array trie nodes: 10
node c left=- mid=a right=d word=False
node a left=- mid=t right=- word=False
node r left=- mid=d right=- word=True
node d left=- mid=- right=e word=True
node e left=- mid=- right=- word=True
node t left=r mid=- right=- word=True
node d left=- mid=o right=- word=False
node o left=- mid=g right=- word=False
node g left=- mid=- right=- word=True
contains car: True
contains ca: False
withPrefix ca: ['car', 'card', 'care', 'cat']
withPrefix do: ['dog']
withPrefix x: []
== Part 2: 10,000 random words ==
TST nodes: 43120, reference slots: 129360
array trie nodes: 43121, reference slots: 1121146
prefix checks against a sorted list: 6 passed
words under "ab": 20
== Part 3: lookup time (one run, this machine) ==
TST: 1156.8 ns per lookup
array trie: 1197.8 ns per lookupThe program prints each node after its left subtree and before its mid and right subtrees, so the rows do not follow the picture from top to bottom. Each row is one node, and its left, mid and right fields say which letter each link points to. Read row t: its left is r, and it has no mid or right. That matches the tree above.
Part 1 also shows the two counts for five words. The TST has 9 nodes and the array trie has 10. The array count includes the root. The TST has no root letter, so it has one fewer. Part 2 shows the same pattern at a larger size, where the TST has 43,120 nodes and the array trie has 43,121.
The two counts always differ by one. Each TST node stands for one distinct prefix that is not empty. Each array trie node also stands for one such prefix, and the array trie has one more node for the empty prefix at the root.
The random words in Part 2 come from Python's random number generator with the seed 42. Java's generator with the same seed gives different words, so a run in another language gives different counts. The relationship between the counts stays the same.
Worked example two: counting memory
Part 2 of the program is the memory comparison. Both structures hold the same 10,000 words, so the difference comes from the design.
A TST uses 43,120 nodes with 3 links each, which is 129,360 reference slots. The array trie uses 43,121 nodes with 26 slots each, which is 1,121,146 reference slots. The array trie uses about 8.7 times as many slots for the same words.
Slots are the honest unit here. The number of bytes one slot takes depends on the Python version and the machine, so the lesson does not turn slots into bytes. The two structures differ in another way too. In the code above, each array trie node is two objects, the node itself and its list of 26 children. Each TST node is one object with three link attributes. So the array trie has more objects as well as more slots.
The TST saves space whatever the alphabet is. A node always has three links. The array trie gets bigger as the alphabet gets bigger. If each node needed 65,536 slots for a larger character set, the array design would be impractical, while the TST would still have three links per node.
Worked example three: lookup speed
Part 3 measures lookups. It runs contains on each of the 10,000 stored words 20 times, which is 200,000 lookups, once for each structure. It runs a warm-up pass first, so that the timer does not include the first call's setup work. The timer is time.perf_counter_ns, which measures elapsed time in nanoseconds.
In this run the TST took 1,156.8 nanoseconds per lookup and the array trie took 1,197.8 nanoseconds per lookup. Those two numbers are almost the same. Three more runs of the same program gave these pairs, in nanoseconds per lookup: TST 1,093.5 and array 977.4; TST 1,124.7 and array 1,012.0; TST 1,110.1 and array 1,061.9. In those runs the array trie was 4 to 11 percent faster, while the run above had the TST about 3 percent faster. The gap is small and its direction changes between runs, so the difference is not reliable.
The reason is the work each lookup does in Python. Every step of either structure runs several Python instructions, such as a comparison, an attribute read and a loop step. The array trie saves a few of them per letter, but the TST also spends some on the sideways moves. The two effects roughly cancel out at this word length. Your numbers will differ, because the speed of a computer depends on what else it is doing. The ratio is the useful part, and in this run the ratio is close to 1.
The TST does more work per letter in the worst case. The array trie does one index per letter. The TST does at least one comparison at each node. When the letter is not the one stored at the node, it moves sideways to left or right, and compares again. A level of the TST can hold up to 26 letters, so in the worst case one letter costs up to 26 sideways steps. In Python each step is a few instructions, so the extra steps are visible in the code, even though they can be hidden in the total.
Which one to choose
The table compares the two designs on the points that matter in practice.
| Array trie | Ternary search tree | |
|---|---|---|
| Links per node | 26 for lowercase letters | 3 |
| Lookup per letter | one list index | one or more comparisons |
| Memory when the data is sparse | many empty slots | fixed three links |
Use the array trie when the alphabet is small, the data is dense and speed matters most. Use the TST when the alphabet is large or when most nodes have only one or two children and memory is tight. A dict per node is a third option, covered in the dictionaries and sets lesson of module 22. It trades memory for a hash lookup at each letter. In Python a dict is often the simplest choice for a trie node, which is why the earlier lessons of this module use it.
The TST also supports prefix listing with the same walk as the array trie. The autocomplete lesson in this module covers that use.
Common mistakes
Inserting an empty string. An empty word has no letters to walk, so the insert method cannot start. If you call insert("") on a version without the check, Python raises an error at the first letter:
def insert_no_check(word):
first = word[0]
return first
insert_no_check("")The output is:
Traceback (most recent call last):
File "main.py", line 6, in <module>
insert_no_check("")
~~~~~~~~~~~~~~~^^^^
File "main.py", line 2, in insert_no_check
first = word[0]
~~~~^^^
IndexError: string index out of rangeThe method in the program raises a ValueError with the message empty word instead. Check for the empty string first and decide what it means for your data.
Forgetting the case of the letters. The array trie turns a letter into an index with ord(ch) - ord("a"). An uppercase letter gives a negative index. Python counts negative indexes from the end of the list, so the result depends on the letter. The capital C has code 67, so ord("C") - ord("a") is -30, which is below the start of a list of 26 items, and Python raises an error:
IndexError: list index out of rangeThe capital T gives -13, which is inside the range for a negative index, so Python does not raise an error. It stores the letter in slot 13, which is n. The word is then in the wrong place with no message. Convert the input to lowercase before you insert or search, with word.lower().
Passing None as the word. A None value is not a string, and len cannot read it. The program calls len(word) first, so a None word fails there:
TypeError: object of type 'NoneType' has no len()Decide whether None is allowed at the start of each method. If it is, return False for it before the length check.
Building the TST recursively on a very long word. The insert method in the program calls itself once per letter. Python allows 1,000 nested calls by default. A word of 900 letters inserts without trouble on the machine used for this lesson. A word of 1,200 letters fails with:
RecursionError: maximum recursion depth exceededWords in a dictionary are short, so this is rare. If your input can be long, write the insert as a loop, the same way contains is written.
Stopping the search too early. A search that returns True as soon as the path exists is wrong. The path to ca exists in the five-word tree, because cat and car pass through it. Only the is_word flag at the last letter says whether ca was stored. The program returns False for contains("ca") for this reason.
Practice
Exercise 1. Insert tea and ten into an empty TST and then into an empty array trie. How many nodes does each one have, and how many reference slots does each one use? Count the array trie root.
Show the answer: The TST nodes are for the non-empty prefixes t, te, tea and ten, so there are 4 nodes. That is 4 times 3 equals 12 reference slots. The array trie has the root, plus one node each for t, te, tea and ten, so 5 nodes. That is 5 times 26 equals 130 reference slots.
Exercise 2. Trace contains("dot") on the five-word tree from the program. Say which links the search follows and where it stops.
Show the answer: The root is the c node. The letter d is larger, so the search follows right to the d node that starts dog. The letter matches, so it follows mid to o, then mid to g. At g, the letter t is larger, and the right link of g is empty. The search returns False.
Exercise 3. Add a method count_words to TernarySearchTree that returns how many distinct words are stored. Use the same recursion pattern as _print_links.
Show the answer: Add these two methods inside the class.
def count_words(self):
return self._count_words(self.root)
def _count_words(self, node):
if node is None:
return 0
own = 1 if node.is_word else 0
return own + self._count_words(node.left) + self._count_words(node.mid) + self._count_words(node.right)Each node is counted once. A node with is_word set adds 1, and the method adds the counts from the three sub-trees. Inserting cat twice does not change the count, because the second insert sets the same flag. On the five-word tree with cat inserted twice, this code returns 5.
Exercise 4. A text editor needs to store words in any language, so the alphabet could hold 65,536 characters. Which structure uses less memory per node, and why?
Show the answer: The TST uses less memory. An array trie node needs one slot per possible character, so 65,536 slots per node. A TST node needs three links whatever the alphabet size. The TST is slower per letter in the worst case, but its memory does not grow with the alphabet.
Exercise 5. Explain in one or two sentences why the TST node count is always one less than the array trie node count for the same words.
Show the answer: Each non-empty prefix of a stored word has exactly one TST node, and the array trie has one node per prefix plus the root for the empty prefix. So the array trie count is the TST count plus one.
Summary
- A TST node holds one letter, the end-of-word flag and three links:
left,midandright. - A TST stores the same prefixes as an array trie, with one node per non-empty prefix.
- On 10,000 random words, the TST used 129,360 reference slots and the array trie used 1,121,146.
- In the measured run, the TST and the array trie took about the same time per lookup in Python.
- The array trie is the better choice for a small alphabet and dense data. The TST is the better choice for a large alphabet or sparse data.