Tries

A trie is a tree that stores words letter by letter, one node per letter, so that words with the same beginning share the same path from the root. It matters because it answers questions about prefixes, the opening letters of a word, in time that depends only on the prefix's length: the question behind autocomplete, command completion and spelling suggestions, which a hash set can answer only by checking every word. The topic starts with the layout and the end-of-word mark, then inserts four words and searches for five by hand. It shows what goes wrong when the mark is left out, implements the trie in three languages with a map of children at each node, and compares it with a hash set of words on speed and memory. It ends with an exercise on suggesting commands from a typed prefix.