Tries: One Node per Letter
A trie is a tree that stores words one letter per node, so words with the same start share their early nodes. This lesson deep-dives the data structure that finds every word under a typed prefix.
Words under one prefix
The demo builds a trie from a fixed word list and walks to the node for car. Every word collected under that node starts with car.
words = ["cat", "car", "card", "care", "dog", "door"]
def build_trie(words):
root = {}
for word in words:
node = root
for letter in word:
if letter not in node:
node[letter] = {}
node = node[letter]
node["end"] = True
return root
def collect(node, prefix):
found = []
if "end" in node:
found.append(prefix)
for letter in sorted(node):
if letter != "end":
found = found + collect(node[letter], prefix + letter)
return found
def walk(trie, prefix):
node = trie
for letter in prefix:
if letter not in node:
return None
node = node[letter]
return node
trie = build_trie(words)
node = walk(trie, "car")
for word in collect(node, "car"):
print(word)Shared starts save nodes
A flat list stores every letter of every word, even the letters words share. The printout counts the flat letters against the trie nodes for the same words.
words = ["cat", "car", "card", "care", "dog", "door"]
def build_trie(words):
root = {}
for word in words:
node = root
for letter in word:
if letter not in node:
node[letter] = {}
node = node[letter]
node["end"] = True
return root
def collect(node, prefix):
found = []
if "end" in node:
found.append(prefix)
for letter in sorted(node):
if letter != "end":
found = found + collect(node[letter], prefix + letter)
return found
def walk(trie, prefix):
node = trie
for letter in prefix:
if letter not in node:
return None
node = node[letter]
return node
trie = build_trie(words)
def count_nodes(node):
total = 1
for key in node:
if key != "end":
total = total + count_nodes(node[key])
return total
flat_letters = 0
for word in words:
flat_letters = flat_letters + len(word)
print("letters in a flat list:", flat_letters)
print("nodes in the trie, root included:", count_nodes(trie))One walk per prefix
Each typed prefix gets its own short walk down the trie. A prefix no word starts with collects an empty list, as the last line shows.
words = ["cat", "car", "card", "care", "dog", "door"]
def build_trie(words):
root = {}
for word in words:
node = root
for letter in word:
if letter not in node:
node[letter] = {}
node = node[letter]
node["end"] = True
return root
def collect(node, prefix):
found = []
if "end" in node:
found.append(prefix)
for letter in sorted(node):
if letter != "end":
found = found + collect(node[letter], prefix + letter)
return found
def walk(trie, prefix):
node = trie
for letter in prefix:
if letter not in node:
return None
node = node[letter]
return node
trie = build_trie(words)
for prefix in ["c", "do", "z"]:
node = walk(trie, prefix)
if node is None:
print(prefix, "->", [])
else:
print(prefix, "->", collect(node, prefix))Example
terms = [
("photo", 900),
("photos", 800),
("photo editor", 700),
("photography", 500),
("photo print", 300),
("photo book", 200),
]
def build_trie(terms):
root = {}
for term, count in terms:
node = root
for letter in term:
if letter not in node:
node[letter] = {}
node = node[letter]
node["count"] = count
return root
def collect(node, prefix):
found = []
if "count" in node:
found.append((prefix, node["count"]))
for letter in sorted(node):
if letter != "count":
found = found + collect(node[letter], prefix + letter)
return found
trie = build_trie(terms)
node = trie
for letter in "pho":
node = node[letter]
matches = collect(node, "pho")
matches.sort(key=lambda pair: (-pair[1], pair[0]))
for term, count in matches[:5]:
print(term, count)
print("suggestions shown:", len(matches[:5]))Key points
- Prefix: the starting letters of a word, or the text typed so far in the box.
- Trie: a tree that stores words one letter per node.
- Shared start: words with the same prefix share the nodes for those letters.
- Lookup: walk one node per typed letter, then collect every word stored under that node.
- Saving: the 6 words in the demo hold 21 letters in a flat list, but the trie stores them in 12 nodes.
In this example, each word ends at a node that also stores its search count, so the words under pho can be ranked. The printout shows the top 5 in count order, and the lowest-count word is left out.
Note
the trie stores words only; the ranking counts live at the end node of each word.
Try it Yourself
Edit the code, then press Run.
Running is simulated
Exercise
Why does a trie store the words card and care cheaply?