Trie
What it is
This structure stores words one letter at a time, going down through a tree. People call it a trie (say it like "tree"), or a tree of letters. Each step down follows one letter. Two words that start the same way share the same steps at the start. Autocomplete and dictionary lookup both use this shape.
The core idea
Each point in the tree points to its possible next letters. Walking in one letter at a time costs only as many steps as the word's own length, not the number of words stored. A point also needs its own "this is the end of a word" marker, kept separate from simply having a next step. Without that marker, a stored prefix such as "ca" inside "car" would look like a stored word too. Looking for a prefix just walks the same steps and stops early, with no need for that marker at all.
Example
Insert "cat", "car", and "card". All three share the first two steps, c then a. After that shared a, they split: t for cat, r for car, with card continuing one more step past car's r.
Search("car")is true.Search("ca")is false, even though every letter of "ca" is in the tree.StartsWith("ca")is true, because some word keeps going from there.Search("cat")is true, and so isSearch("card").
Where you meet this
- Linux IPv4 routing uses
fib_trie, a compressed trie. A lookup walks down by address bits to find the longest matching route. (fib_trie) - httprouter, a Go web router, uses "a compressing dynamic trie (radix tree)" to match paths, which also lets it match patterns like
/user/:name. (httprouter) - Redis Streams "are implemented as radix trees". Redis has its own radix tree code,
rax. (Redis Streams, rax.h)
When to choose it: you ask questions about prefixes, like "which words start with ca", "which route matches this address best", or "which handler matches this path".
When not to: you only ever ask "is this exact word stored". A hash set does that with less memory, because a plain trie spends a node on every letter. A sorted list with binary search also answers prefix questions and is smaller. The compressed (radix) form saves memory by merging long single-child chains.
Common bugs
- Treating a stored prefix as if it were a stored word on its own.
- Losing an earlier word when a longer word that shares its start is inserted later.
- Checking only the last letter instead of every step along the way.
- Mixing up "this path exists" with "this path ends a word".
Keep it fast
A lookup should only touch the steps for the word's own letters, never the whole tree. Words that start the same way already share those steps. Don't give every word its own separate path when the start is identical.
Learn more
Autocomplete systems, IP routing tables, and spell checkers all use this same letter-by-letter tree.