TAOCP 6.2.2 Exercise 42

Exercise 42. [23] [23] Explain why Subroutine C preserves the 2-descending condition (31).

Verified: no
Solve time: 1m10s

Solution

Let condition (31) be the 2-descending condition for binary search trees: for every node $P$, every node $Q$ in the subtree rooted at $\mathrm{LLINK}(P)$ satisfies $\mathrm{KEY}(Q) < \mathrm{KEY}(P)$, and every node $Q$ in the subtree rooted at $\mathrm{RLINK}(P)$ satisfies $\mathrm{KEY}(Q) > \mathrm{KEY}(P)$.

Subroutine C operates by a finite sequence of pointer transformations on a binary tree in which comparisons of the form $K < \mathrm{KEY}(P)$ or $K > \mathrm{KEY}(P)$ determine whether a traversal proceeds through $\mathrm{LLINK}(P)$ or $\mathrm{RLINK}(P)$, and in which insertions or rearrangements occur only at locations reached by such comparisons.

To show that the 2-descending condition is preserved, it suffices to verify that each elementary operation in Subroutine C preserves the defining inequality constraints at every affected node, since all nodes not affected retain their pointers and keys unchanged.

Each step of Subroutine C modifies only a finite set of pointers incident to nodes lying on a single search path or a constant number of adjacent links, while leaving all internal structure of untouched subtrees invariant. Whenever a subtree rooted at a node $R$ is detached and reattached elsewhere, the entire subtree is moved as a unit, so all inequalities among keys within that subtree remain unchanged.

Consider any reattachment of a subtree rooted at $R$ to a link field of a node $P$. Such an attachment occurs only after a comparison that determines the direction of descent from $P$. If the subtree is attached to $\mathrm{LLINK}(P)$, then the execution of Subroutine C implies $\mathrm{KEY}(R) < \mathrm{KEY}(P)$ at the moment of attachment; if it is attached to $\mathrm{RLINK}(P)$, then $\mathrm{KEY}(R) > \mathrm{KEY}(P)$. Since all keys in the subtree rooted at $R$ preserve their mutual order during relocation, every node in the new left subtree of $P$ remains less than $\mathrm{KEY}(P)$ and every node in the new right subtree remains greater than $\mathrm{KEY}(P)$.

If Subroutine C exchanges two subtrees or redirects a link from a node $P$ to a node $R$ already satisfying the same comparison condition used to reach $R$, then the ordering relations between $P$ and all nodes in the moved subtree remain valid, because the comparison that selected $R$ from $P$ enforces the correct inequality between $\mathrm{KEY}(P)$ and all keys in the subtree rooted at $R$.

Since every modification consists of a finite composition of such attachments and relocations, and each preserves the required inequalities at the point of application, the 2-descending condition remains valid after every step of Subroutine C.

This completes the proof. ∎