TAOCP 6.3 Exercise 8

Section 6.3: Digital Searching

Exercise 8. [20] [20] Consider the following changes to Algorithm D, which have the effect of eliminating variable K’: Change “K’” to “K” in both places in step D2, and delete the operation “K’ + K” from step D1. Will the resulting algorithm still be valid for searching and insertion?

Verified: yes
Solve time: 1m19s

Solution

Algorithm D maintains two variables during a descent in a digital search tree: $K$, the working copy of the search argument whose leading digit (or bit) determines the branching, and $K'$, a preserved copy used when the full key must be stored or compared at a node. Step D1 initializes $K'$ by setting $K' \leftarrow K$, and subsequent steps modify $K$ while retaining $K'$ unchanged.

After the proposed modification, step D1 no longer performs $K' \leftarrow K$, and every occurrence of $K'$ in step D2 is replaced by $K$. Thus the algorithm uses a single variable $K$ throughout the descent, and $K$ is also the variable that is progressively transformed during navigation of the tree.

In Algorithm D, the navigation step repeatedly extracts successive digits (or bits) from $K$, and this extraction modifies $K$ so that after $j$ steps, $K$ no longer contains the original argument but only the suffix beginning after the first $j$ digits. When a node comparison requires the original key, the algorithm relies on $K'$ to supply it unchanged. In particular, insertion requires storing the complete original key in a terminal node once the search reaches a null link.

Under the modification, the value available at that moment is the transformed $K$, not the original argument. The stored key would therefore depend on how many digits were consumed during traversal, so two identical search arguments arriving by different paths could be inserted with different residual values of $K$. This violates the requirement that a node stores the full original search argument.

A concrete contradiction arises by considering any successful insertion path in which at least one digit is examined. After the first modification of $K$, the leading digit used to branch is removed from $K$. At termination, $K$ contains only the unprocessed suffix, while the algorithm would insert this suffix as the key if $K'$ is not available. Since different keys can share suffixes after partial consumption, two distinct original keys can produce identical residual $K$ values at the point of insertion, causing loss of injectivity between input keys and stored keys in the tree.

Therefore the modified procedure cannot correctly implement insertion into a digital search tree, since it fails to preserve the original key required for storage and equality testing at terminal nodes. Since insertion is not correct, the combined searching and insertion algorithm is not valid.

This completes the proof. ∎