Trie
A prefix tree: each edge is a character, each root-to-node path spells a prefix. Lookup costs O(word length) regardless of how many words are stored — the autocomplete structure.
A trie stores strings by sharing prefixes: the root is the empty string, and each child edge adds one character. Words that share a prefix share that entire path, so "car", "cart" and "care" store c-a-r once. Nodes carry an end-of-word flag to distinguish stored words from mere prefixes.
Search and insert walk one node per character — O(L) for a word of length L, independent of the number of stored words. That beats hash maps for prefix queries: to autocomplete "ca", walk two edges and every word below that node is a completion, enumerable in output order.
The cost is memory: sparse child pointers per node. Compressed variants (radix/Patricia tries) merge single-child chains, and Aho-Corasick adds failure links to match many patterns simultaneously in one pass over text.
Operations
| Operation | Complexity |
|---|---|
| insert word | O(L) |
| exact search | O(L) |
| prefix query | O(L) |
| autocomplete | O(L + results) |
Where it's used
Autocomplete and spell-checking, IP routing (longest prefix match), T9 input, dictionary compression, multi-pattern search.