TAOCP 6.3 Exercise 16

Exercise 16. [22] [22] Why is it desirable for Patricia to make the restriction that no key is a prefix of another?

Verified: yes
Solve time: 1m07s

Solution

Patricia trees represent a set of strings by a compressed trie in which each branching decision is determined by inspecting selected character positions, and in which nodes are arranged so that every stored key corresponds to a unique terminating condition in the structure.

If a key $K$ is a prefix of another key $K'$, then the path determined by the characters of $K$ is also an initial segment of the path determined by $K'$. In a Patricia representation, this forces both keys to share the same sequence of decisions for all characters of $K$, so the search for $K'$ passes through the point where $K$ would naturally terminate.

At that point the structure must distinguish whether the search should stop with success or continue downward. If no additional mechanism is introduced, the node reached by $K$ cannot be interpreted unambiguously: it is simultaneously the endpoint of a stored key and an internal point on the path to a longer key. A Patricia tree therefore requires either an explicit end-of-word marker or an additional boolean indicator at nodes to record whether a key ends there.

When the restriction is imposed that no key is a prefix of another, this ambiguity disappears. Every root-to-leaf path corresponds to exactly one key, and no internal position in the tree represents a complete key. Consequently, successful search can be determined purely by structural descent without storing or testing an auxiliary termination condition at intermediate nodes.

This restriction also simplifies insertion and search logic. During search, the algorithm never encounters a situation where a partial match is itself a valid key that must be distinguished from a longer continuation. Every mismatch or completion corresponds unambiguously either to failure or to reaching the unique leaf representing the key. This removes the need for extra comparisons or special-case handling during traversal.

In addition, compression in Patricia relies on merging non-branching paths into single decisions. If prefix relationships are allowed, nodes that would otherwise be eliminated by compression must be retained or annotated to preserve key termination information, which reduces the effectiveness of the compression scheme and complicates updates.

Thus, forbidding prefix relationships ensures that each key corresponds to a unique terminal structure position, eliminates ambiguity between internal and terminal nodes, and allows Patricia search and insertion algorithms to operate using only structural information from the compressed trie.

This completes the proof. ∎