Trie
A trie stores words by their letters, one node per letter, so every path from the root spells a prefix and words that begin the same way share the same nodes. Inserting a word follows the existing path as far as it goes and only creates nodes for the part that is new. Looking a word up is the same walk: a missing child means the word is not there, and even a full match only counts if the last node was marked as the end of a word. Because the walk depends only on the word's length, a trie answers prefix questions, autocomplete above all, faster than any sorted list.
The trie holds car, cart, cat, dog, terminal nodes in green. Search "cart": walk one letter at a time; a missing child ends it, and reaching the last letter is only a hit if that node is terminal.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
Next letter 'c', children here: c, d. Continue?
Answer: Yes, follow 'c'. The child exists.
Next letter 'a', children here: a. Continue?
Answer: Yes, follow 'a'. The child exists.
Next letter 'r', children here: r, t. Continue?
Answer: Yes, follow 'r'. The child exists.
Next letter 't', children here: t. Continue?
Answer: Yes, follow 't'. The child exists.
All letters of "cart" matched. Is it a stored word?
Answer: Yes, the node is terminal. The end node carries the terminal mark.
How it runs, step by step
The trie holds car, cart, cat, dog, terminal nodes in green. Search "cart": walk one letter at a time; a missing child ends it, and reaching the last letter is only a hit if that node is terminal.
Searching cart in a trie of 4 words.
Letter 'c'. Children here: c, d. Follow 'c'.
Follow c.
Letter 'a'. Children here: a. Follow 'a'.
Follow a.
Letter 'r'. Children here: r, t. Follow 'r'.
Follow r.
Letter 't'. Children here: t. Follow 't'.
Follow t.
Every letter matched and the last node is terminal: "cart" is stored.
Found.
"cart" found. The walk touched at most 4 nodes: O(length), independent of how many words are stored.
Found.
Remember
- One node per letter; a path from the root is a prefix; shared prefixes share nodes.
- Insert follows existing children and creates the missing ones; the last node is marked terminal.
- Search fails on a missing child, and a full match without a terminal mark is only a prefix.
Where this is used
SearchLucene and Elasticsearch term index
Lucene holds the index of its term dictionary in memory as a finite state transducer, a trie over the terms with shared prefixes stored once and identical tails merged as well, mapping a prefix to the offset of the on-disk block that holds those terms. A prefix query or a completion suggester walks that structure down to the prefix and enumerates what hangs below it. This is why foo* is cheap in Elasticsearch and *foo is not: only one of the two is a walk from the root, and the other has to touch every term.
BlockchainEthereum account state
Accounts live in a Merkle Patricia trie keyed by the hash of the address, and each contract's storage is a second trie of the same kind keyed by the hash of the slot number, so a path down either one is the nibbles of that key and every node is named by the hash of its own contents. One root hash therefore commits to the whole state, and a light client can be handed just the nodes along a single path as proof of what a balance is. Because an update only changes nodes on one path, applying a transaction rehashes a few dozen nodes rather than the entire state.
GamesScrabble move generation
Engines such as Quackle keep the lexicon as a DAWG, a trie whose identical suffix subtrees have been merged into one, which shrinks it by roughly an order of magnitude and lets the whole dictionary stay in memory. Move generation walks the graph a letter at a time and abandons a branch the moment no tile on the rack matches a child, so the overwhelming majority of impossible placements are never enumerated at all. The GADDAG variant indexes each word from every one of its letters outward, so a play can be grown in both directions from a tile already on the board.
Text inputKeypad predictive text
On a phone keypad each digit stands for three or four letters, so a typed sequence is ambiguous until the dictionary rules the alternatives out. T9-style input keeps a trie of the dictionary and, on each keypress, advances only the live paths whose next letter sits on that key, so the surviving set shrinks with every digit and the suggestion is whatever is left. Filtering a word list instead would re-read the dictionary on every keypress; the trie only has to extend the frontier it is already holding.
Why it works this way
Why a terminal flag, instead of just checking for a leaf
The obvious shortcut is to treat a childless node as a word end, and it breaks the moment one stored word is a prefix of another. Insert card and then car: car creates no nodes at all, it only sets a flag on a node that already has a child, so a leaf test would report card and miss car entirely. The converse fails too once deletes are in play, since a delete that clears the flag without pruning leaves a childless node that no longer ends any word. Nothing about a node's shape says whether a word ends there, which is why the flag is stored on the node.
Deleting a word cannot simply delete its nodes
car and card share their first three nodes, so tearing out card's path would take car with it. The safe order is to clear the terminal flag first, then walk back up removing a node only while it has no children and is not itself terminal, stopping at the first node that fails that test. Clearing the flag and pruning nothing is still correct, because search trusts the flag and nothing else, but a trie under a long insert-and-delete workload then never gives any memory back.
Is a trie actually faster than a hash map?
For a plain lookup, usually not. Hashing a string already reads every character of it, so both are O(length), but the hash map does one probe into a contiguous table while the trie does a pointer chase per character, each one a likely cache miss. A node that holds a fixed array of 26 children also costs 208 bytes of pointers on a 64-bit machine, or half that on a JVM with compressed references, whether those children exist or not, and near the leaves almost all of them are empty. The trie earns its place only when you need prefixes or sorted order, which a hash map cannot give you at any price.
Walking to the prefix is the cheap part
Reaching the prefix node costs one step per character, but listing the words below it costs a step per node in that entire subtree, so a one-letter prefix over a dictionary means walking most of the trie. Production autocomplete does not pay that at query time: it stores the best few completions, ranked by frequency, on each node, so the answer is read straight off the node the walk lands on. The lookup was never the expensive part of a suggester; the ranking is.
Read more
- TrieWikipedia
- Deterministic acyclic finite state automaton (DAWG)Wikipedia
- Merkle Patricia trieethereum.org
- Using finite state transducers in LuceneMike McCandless
- Trie visualisedUSF