tries

Tries are tree-like data structures used to store associative arrays where keys are typically strings. A trie, or prefix tree, encodes common prefixes as shared paths from the root. Each edge corresponds to a character, and a node may have children for possible next characters. A node is typically marked to indicate the end of a valid key. The root represents the empty prefix.

Insertion, search, and prefix search traverse along characters; the time complexity for these operations is proportional to the length of the key, O(length). Keys sharing a prefix share the same path, and enumerating all keys with a given prefix requires a traversal of the corresponding subtree.

Tries can be memory-intensive, because a separate node is created for many prefixes and each node stores pointers to children. In practice, space usage depends on the alphabet size and the dataset. Variants such as compressed tries (radix or Patricia tries) collapse chains of single-child nodes to improve space efficiency and speed in large datasets.

Common uses include dictionary storage, autocomplete, spell checking, and IP routing tables where long-prefix matching is needed. Tries excel at prefix-based queries and exact string lookups, and they support efficient enumeration of all keys sharing a given prefix.

The concept traces back to René de la Briandais, who described the Briandais trie in 1959. The term "trie" is short for retrieval and reflects the data structure’s emphasis on prefix-based access.