What does a successful path prove?
A trie node represents the prefix written along its path from the root. Reaching that node proves that the path exists; it does not prove that the prefix itself is a stored key. A separate terminal marker answers the second question. For example, in the dictionary a, an, ant, ante, bat, bath, bats, the path for ba exists because it begins several keys, but ba itself is not stored.
The preceding section introduced the representation and deletion. Here we trace lookup and completion so that the meaning of each intermediate state is visible.
Definition 7.2.1
(Exact lookup and prefix completion)
Let be the set of stored keys and a query string. Exact lookup asks whether . Prefix completion asks for all keys that have as a prefix, that is, for some string (possibly empty). A key equal to is therefore a completion of .
Keep the invariant while reading
After consuming characters of a query , the current node represents exactly , provided all edges exist. Initially and the current node is the root. If the next edge exists, following it extends both the path and the consumed prefix by one character. If it is missing, no stored key can start with the entire query: every stored key beginning with that query would need the missing edge.
For exact lookup, after consuming every character inspect the terminal marker. With ba, both edges exist, but the marker is false; the answer is “not a key.” With an, the marker is true even though the node has descendants. A node can therefore be both a complete word and the start of longer words.
For prefix completion, first find the node for the query. If it exists, enumerate terminal nodes in its subtree, including the node itself when terminal. With ba, the completions are bat, bath and bats. Every emitted key has the requested prefix because its path passes through the query node; every stored key with that prefix ends at a terminal node below it, so a complete traversal finds it.
Concept lensAlgorithmic
Completions as a block of the sorted keys
List the keys in lexicographic order. The keys with prefix then form one contiguous block, and if the block is nonempty it begins at the first key that is at least . A binary search for that key, followed by a scan while the prefix still matches, yields the same completions as the trie. For ba in the dictionary above the search lands on the fifth key, bat, and the scan emits bat, bath, bats; for bad it lands on bat, which lacks the prefix, so the block is empty.
Theorem 7.2.2
(Correctness of trie lookup and completion)
Let a trie represent the set of stored keys in canonical form, meaning that its nonroot nodes are exactly the nonempty prefixes of stored keys and a node is terminal exactly when its string is stored. Let be a query string. If the search for meets a missing edge, then no key of has as a prefix. Otherwise the search ends at the node for , and exact lookup answers yes exactly when that node is terminal, that is, exactly when . Prefix completion emits exactly the keys of that have as a prefix, each once.
Proof
(Reading the path in both directions)
Suppose the search meets a missing edge, and assume that a stored key begins with the full query. Its path must contain every edge of that query, including the edge the search reported missing. This contradiction proves that there are no completions, and in particular that .
If no edge is missing, the invariant shows that the search ends at the node representing . In a canonical trie that node is terminal exactly when is a member, so the terminal marker decides exact lookup.
For completion, each emitted key is the string of a terminal node in the subtree of the query node, so its path passes through that node and it has as a prefix. Conversely, a stored key with prefix has a path through the query node and ends at a terminal node below it or at the node itself, so a complete traversal of the subtree reaches and emits it. Each node is visited once, so each key is emitted once.
Proof X-ray
Why a missing edge settles the whole query
The argument runs in two directions across the same structure. A stored key always has its complete path, because insertion creates every edge of a key. That is what makes a missing edge decisive: the proof takes a hypothetical key beginning with the query and reads its path, instead of searching all keys. Conversely, the terminal marker is set exactly for stored keys, which is what lets the marker decide membership once the path succeeds.
Both facts come from canonical form. If an earlier pruning had removed an edge still needed by a stored key, the missing-edge conclusion would no longer be justified. A path that ends successfully has a different conclusion from a missing edge: it establishes a prefix, after which the marker, not the path, decides membership.
Counterexample mode
Reaching a node does not prove a stored key
A tempting rule is: if the search consumes every character of without a missing edge, then is stored. In the dictionary a, an, ant, ante, bat, bath, bats, the query ba consumes both characters and reaches the node ba, yet ba is not among the seven keys; its terminal marker is false. The rule fails because the node is only a prefix of bat, bath and bats. The repair is to inspect the terminal marker after the path succeeds.
The converse intuition also fails: a node with descendants is not thereby a non-key. The node an has the descendants ant and ante, and its marker is true, so an is stored.
Worked example 7.2.3
(Three exact lookups)
Take the dictionary a, an, ant, ante, bat, bath, bats. The nodes below the root are a, an, ant, ante, b, ba, bat, bath and bats; the terminal ones are a, an, ant, ante, bat, bath and bats.
For ba, the edges b and a exist and the marker is false, so ba is not a key. For an, the edges exist and the marker is true, so an is a key although the node has children. For bad, the search reaches ba and finds no edge d, so bad is not a key, and the missing edge also shows that no key begins with bad.
Worked example 7.2.4
(Two prefix completions)
For the query ba, the query node is not terminal, so nothing is emitted for it. Its subtree has the child bat, which is terminal and is emitted first; below bat, visiting the children h and s in alphabet order emits bath, then bats. The completions are bat, bath, bats.
For the query an, the query node is terminal and is emitted first. Then its child ant is terminal, and below it ante is terminal. The completions are an, ant, ante. The key a is not a completion of an, because a does not have an as a prefix.
Worked example 7.2.5
(Edge cases: the empty query and a query past a leaf)
The empty query consumes no edge and stays at the root. This dictionary does not contain the empty string, so the root is not terminal and the exact lookup answers no. As a prefix, the empty string matches every key, so completion emits all seven keys, in the order a, an, ant, ante, bat, bath, bats.
Now query batss. The characters b, a, t, s follow existing edges and reach the node bats. That node has no child s, so the search meets a missing edge: batss is not a key and has no completions.
Count the work being claimed
Proposition 7.2.6
(Cost of lookup and completion)
Assume each child lookup takes constant time, and that the children of a node can be enumerated at constant cost per existing child. For a query of length , exact lookup uses at most child lookups and time. If the query node exists and its subtree has nodes, and the emitted keys have characters in total, completion takes time.
Proof
(Following the query, then visiting the subtree)
The search consumes one query character per child lookup and stops at the first missing edge or after characters, so it makes at most lookups and then reads one marker. Completion then visits each of the nodes of the subtree once at constant cost, plus constant cost per existing child, which totals because a subtree with nodes has edges. Writing the emitted keys costs .
Common mistake
(Calling the whole completion )
Following the query is , but completion may then visit a large subtree and emit many strings. The query a in the dictionary above has length 1, yet it emits four keys, so the cost is not a function of alone. It is misleading to call the entire enumeration without also bounding this additional work.
Common mistake
(Assuming the empty-query answers must agree)
The empty query consumes no edges and leaves the search at the root. Exact lookup is true precisely when the root is terminal, meaning the empty string was stored. As a prefix, the empty string matches every stored key. These two answers need not agree, as the dictionary above shows: the lookup says no, while the completion lists seven keys.
Check yourself
Quick check
(If the search for bad reaches ba and the d edge is missing, can badger be stored?)
Consider the path that badger would need.
Solution · Answer
No; its path would require the missing d edge.
Quick check
(In an arbitrary dictionary, if an is terminal and also has children, must ant be stored?)
Does having a child tell you which letter the child carries?
Solution · Answer
No. Having a child alone does not establish that the full ant path exists or ends at a terminal node. If the only child of an is g, for example, the dictionary may contain ang and not ant.
Quick check
(In the dictionary a, an, ant, ante, bat, bath, bats, what are the completions of ante?)
Is the query node terminal? Does it have a subtree?
Solution · Answer
Only ante itself. The query node is terminal, so it is emitted, and it has no children, so nothing else is emitted.