A path and a stored word are different facts
Definition 7.1.1
(Trie, terminal marker and canonical form)
A trie stores a set of finite strings over an ordered finite alphabet of size . The root represents the empty prefix. Each edge is labeled by one character, and a node's path from the root spells its prefix. A node may be marked terminal to say that the corresponding string itself is in the set. A nonroot path without a terminal marker represents a prefix of a stored string, not a stored word. The root is the exception: it exists even when the set is empty.
A trie is canonical for a set when its nonroot nodes are exactly the nonempty prefixes of strings in , so that every nonroot node is a prefix of at least one stored string, and a node is terminal exactly when its string belongs to .
The insertion and pruning operations below preserve canonical form. This lesson treats a set, not a multiset: inserting an existing string does not increase its multiplicity. The empty string, if allowed, is represented by the root's terminal marker.
Concept lensCombinatorial
Counting nodes by shared prefixes
Sort the stored strings lexicographically as and put . The prefix of of each length greater than is not a prefix of any earlier string, so
where lcp is the length of the longest common prefix. For in, inn, tea, ten, to the terms are , giving nonroot nodes. Sharing saves exactly the common prefix lengths.
Insert, find, and enumerate
To insert a string, follow its characters from the root, creating a missing child when needed, and mark the final node terminal. To test exact membership, follow the path and answer yes only if the final node exists and is terminal. A missing edge proves absence; arriving at a nonterminal node means the exact word does not belong to the set. A nonroot node is still a prefix of a stored word; the root may exist even for the empty set. Inserting the empty string only marks the root.
For a prefix query, first follow the prefix. If its path is missing, no stored word has that prefix. Otherwise traverse its subtree and emit a string at each terminal node, including the prefix itself if that node is terminal. Visiting children in alphabet order gives lexicographic order when a node is emitted before its descendants. This is enumeration: merely finding the prefix node is not the cost of producing all answers.
Trace and a shared prefix
Worked example 7.1.2
(Building a trie with a shared prefix)
Insert to, tea, ten, in, inn into an empty trie. The represented prefixes are the empty prefix and
There are nine nodes including the root. The terminal nodes are exactly the five inserted words. The node te is not terminal; in is terminal and also has a child for inn. Enumerating prefix te emits tea, then ten.
Counterexample mode
A prefix node can also be a word
If we delete in, removing its entire node and subtree would also destroy inn. Clearing only the terminal marker at in removes the exact word while preserving the longer word. Reaching the node is therefore not enough to decide exact membership after deletion.
Common mistake
(Reading a reached node as a stored word)
In the trace trie the path te exists, so a lookup that stops when the path ends would answer yes. But te is not terminal, and the set does not contain it. Membership needs both a complete path and a terminal marker.
Delete without damaging other words
For a present string, follow its path and clear the terminal marker. Then walk back toward the root: remove the current nonroot node only while it has no children and is not terminal. Stop when either condition fails. If the string is absent, leave the trie unchanged. Never remove the root, even if it becomes an unmarked leaf.
Theorem 7.1.3
(Insertion, lookup and deletion keep the trie canonical)
Let a trie be canonical for a finite set of strings, and let be a string. Inserting yields a canonical trie for . The membership test answers yes exactly when . Deleting as described above leaves the trie unchanged if , and otherwise yields a canonical trie for .
Proof
(Which nodes are still needed after a deletion)
Insertion adds nodes only for the prefixes of that were missing, and every prefix of is a prefix of a member of . It marks the final node terminal and changes nothing else. By canonical form, the path of exists and ends at a terminal node exactly when , which gives the membership test.
For deletion, suppose and let be the nodes on the path of , with the root and the node of . After the marker at is cleared, the terminal nodes are exactly the members of . Call a nonroot node needed if its prefix is a prefix of some member of . A node off the path of is a prefix of some member of other than , so it is needed; only can be unneeded.
The loop moves up from . It removes a node only when that node is nonterminal and has no child at that moment. Such a node is unneeded: a member of extending its prefix would force a node for a longer prefix, hence a child, and the only children ever removed were unneeded themselves. The loop stops at the first node that is terminal or has a child. A terminal node is a member of , so it is needed. A child that still exists is needed: a child off the path of is a prefix of a member other than ; a child of extends properly, so it is a prefix of a member other than ; and if the loop stops at with , its path child was already removed, so any remaining child is off the path. In every case the stopping node is needed. Every ancestor of a needed node is a prefix of the same member, so all of them are needed and none is removed.
Thus the pruned trie has exactly the nodes for the prefixes of members of , with terminal markers exactly at those members. If , either the path is missing or its node is not terminal, and nothing is changed.
Proof X-ray
Why the loop needs both stopping conditions
Each stopping condition protects something different. A terminal marker protects a word that ends at the node; a child protects a longer word that passes through it. Neither alone is enough. Take and delete tom: the node m is removed, and to is then a childless leaf. A loop that tested only "has no children" would delete to and lose a stored word. A loop that tested only "not terminal" would instead delete a prefix node of a longer word, which is the failure shown in the counterexample above.
The argument closes at the first needed node. Everything above it is a prefix of that node's string, so no ancestor needs a separate check. The loop can therefore stop at the first failure and never has to look at the rest of the path.
Worked example 7.1.4
(Deleting from the trace trie)
In the trace, deleting tea clears its marker and prunes only its final a node: te remains because it still leads to ten. Deleting in instead clears its marker but prunes no node, since inn remains. Deleting the empty string clears the root marker if it was set; it never deletes the root or other words.
Worked example 7.1.5
(Edge cases: absent words, the last word and the empty string)
Deleting tex from the trace trie finds no edge x, so the string is absent and nothing changes. Deleting te also changes nothing: the node exists, but it is not terminal, so te is not a member.
Now let . Deleting a clears the marker. The node a is nonterminal and has no children, so it is pruned. The loop reaches the root and stops, leaving the root alone: the trie of the empty set.
Finally let , so the root is terminal and has the child a. Deleting clears the root's marker and does nothing else, and a is still a member.
Costs depend on the representation
Proposition 7.1.6
(Costs with an array of child slots)
Suppose each node has an array of child slots, indexed by character in constant time. Exact lookup of a length- string takes time. Insertion and deletion take time; if is treated as a fixed constant, this is . If a subtree traversal visits nodes and emits characters in total, finding a prefix of length and enumerating in alphabet order takes . The representation uses child slots for nodes.
Proof
(Counting nodes visited and slots scanned)
Lookup follows at most edges and visits at most nodes, at constant cost each. Insertion creates at most nodes, and initializing the child slots of each costs . Deletion walks down at most nodes and then up; each "has no children" test scans slots, and each removal costs , giving . For enumeration, finding the prefix node costs , scanning child slots costs per visited node, which is , and writing the output costs . Storage is slots per node.
Sparse maps can save slots, but their lookup and ordered-traversal costs depend on the chosen map.
Common mistake
(Charging an enumeration only for the prefix)
Finding the prefix node takes , but the answer may be the whole subtree below it. The cost includes the visited nodes and the output . A short prefix with a large subtree is expensive even though the prefix path is cheap.
Exercises with solutions
Quick check
(Prefix versus word. In the trace, is te an exact member?)
Check the terminal marker, not only the path.
Solution · Answer
No. Its node exists, but is not terminal.
Quick check
(Deletion. After deleting tea, which of ten and to remain?)
Which nodes does each path use?
Solution · Answer
Both remain; neither path uses the removed final a node.
Quick check
(Root. How is the empty string stored?)
The root is the only node that represents the empty prefix.
Solution · Answer
By marking the root terminal; the root exists whether or not the empty string is a member.
Quick check
(Output cost. Why is finding a prefix node alone insufficient to bound enumeration?)
Think about what must still be done after the prefix node is found.
Solution · Answer
The algorithm may still visit many descendants and must emit the characters of the matching words.