Tries

A trie has one node for every distinct prefix of the stored strings. In the basic R-way trie each node has R links, one per possible character, so a successful search follows exactly one link per character of the key, L steps however many keys are stored, and a miss usually stops after a few characters. The cost is space: Sedgewick and Wayne count (R+1)N links for N keys, most of them null, and their benchmark R-way trie ran out of memory on a large input. Ternary search tries need far less memory (4N links in the same comparison) and in that benchmark ran as fast as hashing for string keys. Edward Fredkin named the structure in 1960 from “retrieval” and meant it to be said “tree”; many say “try” to tell the two apart.

Tries shine where hash tables can’t help: finding every key with a given prefix (autocomplete), wildcard matches, and the longest stored prefix of a string. That last one is how routers pick a route: Sedgewick and Wayne’s example forwards a packet for 128.112.136.12 by the longest matching prefix it knows, such as 128.112. The Linux kernel keeps its routing table (fib_trie) as an LC-trie, a trie with path and level compression, and searches it by backtracking toward the longest matching prefix.

Tries are not part of the general collections in these languages: Rust’s std::collections lists sequences, maps, sets and a binary heap, and Go’s container packages are heap, list and ring. They come from libraries or are written for the job, often over a hash map of children per node.