CSE Roadmap

Core tier · about 4 hours · 8 parts

Part 4 of 8 · 2 min read

The trie

A tree of letters.

A trie (said "try", from "retrieval") is a tree that stores strings letter by letter. The root is the empty string. Each node holds one letter, and the path from the root to a node spells a prefix. Nodes that end a real query are marked, and store its frequency.

root
 |- t
 |   |- r - e - e   (tree: 10)
 |   |    |- u - e  (true: 35)
 |   |    '- y      (try: 29)
 |   '- o - y       (toy: 14)
 '- w - i
     |- s - h       (wish: 23)
     '- n           (win: 50)

Plain lookup. To get the top k for a prefix, (1) walk down the prefix, which takes about p steps for a prefix of length p, (2) visit every query below that node, and (3) sort them and take the best k. Step 2 can be huge for a short prefix, so this is too slow.

Optimisation 1: cap the prefix length. Users rarely type very long prefixes. Limit p to a small number such as 50. Walking down then takes a fixed small time.

Optimisation 2: cache the top k at every node. Each node stores its own best 5 queries. The answer for a prefix is then just a read of one node. For the node "tr" in the picture, the list is true 35, try 29, tree 10. This uses much more memory, but the book argues it is a good trade: space for speed.

With both changes, a lookup is a short walk plus one read, which takes a small, fixed time.

A worked example (made up). For the prefix "t" with k = 3, the cached list is true 35, try 29, toy 14. Tree (10) is fourth and is left out. No tree walk and no sorting happen at query time.

Trie (prefix tree)

A trie is a tree where each step down adds one letter, so every node stands for a prefix and its descendants are the strings that start with it.

Example: the node for "tr" has children for "e" and "u" and "y", leading to tree, true and try.

Check yourself: 1. What does the root of a trie stand for? 2. Why cache the top k at every node? 3. What is the cost of that cache?