Trie

A trie, also known as a prefix tree, is a tree-based data structure used for storing a dynamic set of strings or associative arrays where keys are typically strings. Each node represents a common prefix of keys, and edges are labeled with single characters. The root corresponds to the empty prefix, and a path from the root to a node spells a string. Nodes may mark whether the path to that node constitutes a stored key and may also hold associated values.

Operations on a trie include inserting a key, searching for a key, and checking for keys that share a given prefix (startsWith). The time complexity for these operations is proportional to the length of the key, O(m), making tries efficient for prefix-based queries and for workloads with many related keys. Tries enable fast completion and lookup without scanning the entire data set.

Implementation considerations include the representation of child links. Nodes can hold fixed-size arrays for small alphabets or dynamic maps for larger or sparse alphabets. While tries offer fast lookups, they can use a large amount of memory because each character in every key can create a node. Memory-efficient variants exist, such as compact tries (radix or Patricia tries), where chains of single-child nodes are collapsed to reduce space usage.

Common applications of tries include dictionary storage, autocomplete and spell checking, and routing tables in networking. The concept was introduced by Rene de la Briandais in 1959, and since then has become a foundational structure in text processing and related fields.