Trie
A trie stores words as paths from a root, one letter per node. Words that start the same way share the same first nodes, and a ring marks where a word ends. Finding a word, or every word with a given prefix, takes one step per letter.
Insert 3 words: car, cat, card. Each node is one letter; a word is a path down from the root.
1function insert(root, word) {2 let node = root;3 for (const ch of word) {4 if (!node.children.has(ch)) {5 node.children.set(ch, newNode());6 }7 node = node.children.get(ch);8 }9 node.isWord = true;10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | L | insert or look up a word of length L |
| average | L | however many words are stored |
| worst | L | the same: the path is one node per letter |
| space | total letters | shared prefixes are stored once |
Where it breaks
- A word inside another word. Pick app apple ape: "app" ends partway down the path to "apple". Without the ring, there would be no way to tell "app" was ever inserted.
- Little sharing, lots of nodes. Pick no sharing: nothing is shared, so it is 9 nodes for 9 letters. Each node also needs room for its children, so a trie can take far more memory than a plain list of words.
- When a hash set is better. For exact lookups only, a hash set is simpler and smaller. A trie earns its keep with prefix questions: autocomplete, spell checkers and IP routing tables.