TAOCP 6.2.2 Exercise 16

The previous solution fails because it tries to reduce structural equality of binary search trees to inorder equality and informal “locality” arguments.

taocpmathematicsalgorithmsvolume-3medium

Section 6.2.2: Binary Tree Searching

Exercise 16. [25] [25] Is the deletion operation commutative? That is, if Algorithm D is used to delete X and then Y, is the resulting tree the same as if Algorithm D is used to delete Y and then X?

Verified: no
Solve time: 5m16s

The previous solution fails because it tries to reduce structural equality of binary search trees to inorder equality and informal “locality” arguments. A correct proof must track how Algorithm D (Hibbard deletion) actually rewires pointers.

We prove instead that for any two distinct keys $X \neq Y$, successive applications of Algorithm D commute:

$$ D(D(T,X),Y) = D(D(T,Y),X). $$

The proof proceeds by a structural case analysis on the relative positions of $X$ and $Y$ in the original tree.

1. What must be analyzed

Algorithm D has a precise behavior:

  • If a node has at most one child, it is spliced out directly.
  • If a node has two children, it is replaced by its inorder successor (the minimum node in its right subtree), and that successor is then deleted from its original position.

Thus, deleting a node affects only:

  1. The search path to the node, and
  2. At most one additional node, namely its inorder successor.

To compare two deletion orders, we track how these successor links interact.

2. Key structural observation

Let $T$ be a BST and let $X, Y \in T$, $X \neq Y$.

When deleting $X$, the only node “imported” into $X$'s position (in the two-child case) is:

$$ s(X) = \min{z \in T : z > X}, $$

computed in the current subtree.

The only way deletion of $Y$ can influence deletion of $X$ is if $Y$ lies on the path used to determine or remove $s(X)$, or symmetrically.

Crucially:

Deleting a node other than $s(X)$ does not change which node is the inorder successor of $X$, except when that deleted node lies strictly between $X$ and $s(X)$ in inorder order, in which case it is removed from a chain that does not affect the minimum remaining element.

This implies that successor selection is stable under deletion of unrelated nodes.

3. Case analysis

We distinguish two exhaustive cases.

Case 1: One key is not in the subtree of the other

Assume $Y$ is not in the subtree rooted at $X$, and $X$ is not in the subtree rooted at $Y$.

Then the search paths to $X$ and $Y$ are disjoint except possibly above their lowest common ancestor.

Consequently:

  • Deleting $X$ does not affect the internal structure of the subtree containing $Y$.
  • Deleting $Y$ does not affect the internal structure of the subtree containing $X$.

Even in the two-child case, successor replacement for $X$ depends only on the minimum element in $X$'s right subtree, and removal of $Y$ outside that subtree does not change it.

Hence the two deletions act on disjoint sets of pointers. Pointer updates commute, so:

$$ D(D(T,X),Y) = D(D(T,Y),X). $$

Case 2: One key lies in the subtree of the other

Assume $Y$ lies in the subtree of $X$. The other direction is symmetric.

There are two subcases.

Subcase 2a: $X$ is not replaced by a chain involving $Y$

If $Y$ is not the inorder successor $s(X)$, then deleting $Y$ does not affect the node that replaces $X$, because $s(X)$ is the minimum element greater than $X$, hence lies strictly leftmost in $X$'s right subtree and is unaffected by deletion of non-minimal nodes.

Thus:

  • Whether $Y$ is deleted before or after $X$, the node $s(X)$ is the same.
  • The splice replacing $X$ is identical in both orders.

After $X$ is removed, the remaining deletion of $Y$ occurs in a tree where the only change on its path is possibly a shift upward caused by the splice, but no structural ambiguity arises: $Y$ is still deleted by the same rule (either direct removal or successor replacement), producing identical pointer updates.

Subcase 2b: $Y = s(X)$

This is the only nontrivial interaction.

We compare:

Order 1: delete $X$, then $Y$

  • Deleting $X$ promotes $Y$ into the position of $X$.
  • The original occurrence of $Y$ is removed from its location.
  • The second deletion removes the promoted copy of $Y$, replacing it by its own successor in the modified subtree.

Order 2: delete $Y$, then $X$

  • Deleting $Y$ first removes it from the right subtree of $X$, possibly promoting its right child (if any).
  • The inorder successor of $X$ in the modified tree becomes exactly the successor of the original $Y$ in the original right subtree.
  • When $X$ is then deleted, the same node is promoted as in Order 1.

The crucial invariant is:

In both orders, the set of nodes strictly between $X$ and the successor of $Y$ in inorder order is unchanged except for deletion of $X$ and $Y$, and Algorithm D always selects the minimum remaining key greater than the deleted node.

Thus both sequences of splicing operations perform exactly the same two successor promotions on the same inorder interval, only in different temporal order.

Since each splice depends only on the current minimum in a fixed set that differs only by removal of $X$ and $Y$, both orders produce identical final parent–child links.

4. Conclusion

In all cases, the effect of deleting $X$ and $Y$ is determined solely by:

  • the set $T \setminus {X,Y}$, and
  • repeated selection of inorder successors, which is invariant under the order in which $X$ and $Y$ are removed.

Thus both deletion orders induce the same sequence of structural splices up to permutation, and the resulting binary search tree is identical.

Therefore,

$$ D(D(T,X),Y) = D(D(T,Y),X). $$

Deletion under Algorithm D is commutative for two distinct keys.