A trie (prefix tree) stores one character per edge, so words sharing a prefix share a path — insertion, search and prefix lookup all run in O(|query|) time, independent of how many words are stored. Its weakness is memory: a long unbranching chain of characters still costs one node per character.
A radix trie (also called a PATRICIA trie or compressed trie) fixes this by merging every node that has exactly one child and is not itself a word ending into its parent edge, so a chain of single-character edges becomes one edge labelled with the whole substring:
compress(node):
for each child c of node:
label = edge(node, c)
while c is not a word AND c has exactly 1 child:
label += edge(c, c's only child)
c = c's only child
emit compressed edge "label" -> compress(c)
This guarantees a hard bound: a radix trie built from n distinct keys has at most 2n − 1 nodes, no matter how long the keys are — because every internal node left standing has ≥ 2 children or is a word ending, so the branching structure alone bounds the count. Lookup cost stays O(|query|) — you just compare against longer substrings per step instead of one character.
- Left diagram — the uncompressed trie: one node per character.
- Right diagram — the same word set as a PATRICIA trie: single-child chains merged into one labelled edge.
- Prefix query — walks both trees simultaneously edge by edge, consuming as much of your query as each edge label matches, highlights the path in both diagrams, and cross-checks that the two structures return the exact same word list — exactly how a real autocomplete index turns a keystroke into a suggestion list, independent of how the index is stored internally.
Real-world relevance: compressed radix/PATRICIA tries back IP routing tables (Linux's fib_trie), and are the standard structure behind fast prefix-based autocomplete and spell-check indexes where memory, not just speed, matters.