Search tools and guides ⌘K
II · Trees, with shape

Trie (prefix tree)

A tree you walk one character at a time.

1959 · 1960 · René de la Briandais · Edward Fredkin
The story

Briandais introduced the structure for retrieval; Fredkin gave it the name "trie", pronounced "tree" originally, now usually "try" to disambiguate. Each edge is labelled with one character; each node is a prefix. Searching for a string of length k takes O(k), not O(k log n).

How it works

Root is empty string. Each child edge is one character; each node optionally marks "this prefix is a complete word". Lookup walks the input character by character. Insert allocates nodes for any new prefixes.

Where it lives

Search autocomplete. Spell-checkers. IP routing tables (a radix trie variant). Firewall ACLs. Browser URL bar. Virtually every text-input system has a trie hiding in it.

The key insight

Trie memory cost can dominate. Radix tries (compressed tries) merge single-child chains into edge labels: same lookup, dramatically less memory. The Linux kernel's routing table is a level-compressed trie.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it.
← All data structures