An autocomplete box receives a few typed characters and needs to find stored strings that start with them. Those characters are a prefix: an initial sequence of a string. If several keys begin with the same sequence, they have a common prefix. For example, “and”, “ant”, and “anthem” share “an”. Storing that shared path once makes prefix lookup a natural operation rather than a scan of unrelated keys. section 6.4.5 section 6.2.6
In a trie, each edge represents one character. Following edges from the root spells a prefix; a node marked as a key also spells a stored string. An unmarked node can still represent a useful prefix. To find every key starting with a given prefix, follow its path, then collect the marked keys in the subtree. If the path does not exist, the result is empty. section 6.2 section 6.2.6
Keep three related questions separate:
- Does this whole string occur as a key? An exact search must finish at a key node. section 6.2 section 6.3.2
- Which stored keys start with this prefix? Find its path and enumerate the matching branch. section 6.2.6
- What is the longest stored key that prefixes this string? Follow the string’s path and retain the deepest key encountered; a merely shared path is not enough. section 6.2.5
A radix trie compresses paths into edges labeled with strings rather than single characters. At a node, outgoing labels cannot share a common prefix, so the next character selects at most one candidate edge. Compare its label with the remaining input to find their longest common prefix. Inserting a key that diverges partway through an edge requires splitting that edge at the shared prefix and adding a branching node. section 6.3.1 section 6.3.3
Figure 6.15 Possible cases comparing a search string to a node's links. (1) An edge’s label completely matches part of the string. (2) An edge’s label and the search string have a common prefix that is shorter than both strings. (3) The search string is a prefix of one of the edge’s labels. (4) The search string has no common prefix with any of the edges.
The four edge-match cases show why a label can match completely, diverge partway, contain the entire search string, or share no prefix with it. section 6.3.1
Prefix lookup needs extra care in a radix trie: the requested prefix may end inside an edge, with no node at that point. If all requested characters match, enumerate keys below that edge; if the strings diverge before the request ends, there are no matches. By contrast, an exact-key search cannot accept a match that stops inside an edge. section 6.3.6 section 6.3.2
For a trie with a prefix of length m and j nodes, finding and enumerating matching keys has a worst-case bound of O(m+j) when results are accumulated efficiently; traversal cost grows with the branch explored. Long shared prefixes can save storage, but node and link overhead may instead make a trie larger than a binary search tree. Radix compression reduces path overhead while making edge matching and updates more involved. section 6.2.6 section 6.2.1 section 6.3.3
