Store a set of words so that shared beginnings are stored once: a tree where each edge is a letter and each path spells a prefix. Then autocomplete, spell-check, and IP routing are just a walk down the tree. Its name comes from reTRIEval — and, awkwardly, its inventor meant it to rhyme with tree.
THE TECHNIQUE one node per shared prefix
Each node has a child per possible next letter; inserting a word walks or creates that path, marking the final node as a word-end. Every word sharing a prefix shares the same nodes up to where they diverge — so a prefix query is a single walk, and everything below is a completion. Type a prefix to autocomplete. live demo
HISTORY & CREDIT named, not invented; and mispronounced by design
Fredkin is called the trie’s inventor — he invented named it; the structure was already in print. And the “correct” pronunciation is the opposite of what everyone assumes. cited
1912 · Axel Thue describes the string-set idea abstractly. 1959 · René de la Briandais publishes the linked-list-of-children structure — a year before the name. 1960 · Edward Fredkin coins “trie” (“Trie Memory,” CACM), from reTRIEval — and intended it pronounced “tree.” Because that collides with “tree,” most people now say “try” — the opposite of the origin. 1968 · Donald Morrison’s PATRICIA / radix tree compresses chains of single-child nodes — the space-efficient trie that IP routers and suffix structures use.
Autocomplete, spell-check, longest-prefix IP routing, and the failure-links of Aho-Corasick all sit on this one shape. Fredkin named it, 1960
RECOMMEND FOR I-13 strings and links, both walls
A trie stacks two of the campaign’s standing wants: strings (the keys are sequences of characters) and dynamically linked nodes (a child per letter):
// node: children[26] (references) + isWord flag ; keys are strings
// both the character-sequence keys and the linked children are aggregates
Recommend: the aggregate wall, doubled — and it joins AVL (072) and red-black (073) on the linked-node want, plus the campaign’s standing string want (Boyer-Moore-061, KMP-063, BWT-065). A trie can be flattened into a node arena (a 2-D children table as parallel index arrays), which runs on I-13’s arrays for a fixed alphabet — the same pointerless encoding the other trees need, over a bounded alphabet. Note: the honest signal is now unmistakable — a cluster of darts (three trees + the string algorithms) all want heap-allocated linked structure over sequences, the corpus’s largest un-added aggregate.