Trie

A trie, or prefix tree, is a data structure for string keys. Each edge represents the next character, so keys with the same prefix share a path from the root. An instrument picker can follow the characters a user types and then list matching symbols without scanning the whole catalogue. A terminal flag marks where a stored key ends. Sedgewick and Wayne, Tries, §5.2

Take the strings ES, ESM, ESH and NQ in an illustrative symbol namespace. To insert a key, follow its characters from the root, create any missing edges, and mark the final node as terminal. The E → S path is shared by three keys. At ES, the terminal flag records the key ES itself, and the outgoing H and M edges extend it to ESH and ESM.

The terminal flag also tells you what to preserve when a key is removed. Clearing the flag at ES removes that exact key while leaving ESH and ESM searchable. A node can be pruned once it has neither a stored key nor any children. Sedgewick and Wayne, deletion in an R-way trie

For an exact lookup of a non-empty key with length $m$, the worst-case work is $O(m)$ when selecting a child by character takes constant time. A missing edge can end the search early. Listing completions adds work after the prefix is found. Let $p$ be the prefix length, $V$ the number of nodes visited in its subtree, and $C$ the total characters in the returned strings. With constant-time child lookup, children already iterable in sorted order in time proportional to their number, and a mutable path buffer, the time complexity is $O(p+V+C)$. For the example, finding the prefix takes two edge steps. The traversal then visits three subtree nodes, including ES itself, and writes eight characters across the three results. Copying the entire path at every edge or sorting children during the query can add work.

A hash table keyed by full symbol supports exact lookup, but its buckets do not group symbols by shared prefix. A binary search tree orders complete keys and can find prefix matches as a lexicographic range. A trie branches on one character at a time and gathers matches from one subtree. A suffix tree indexes the suffixes of a text, which lets a search start at any position in that text. Here the keys are whole symbols and the query starts at their first character. Szpankowski, Tries, “Tries and Suffix Trees”