TAOCP 6.2.2 Exercise 14

The original argument fails because it assumes a uniform “shift” of depths along the entire search path from $x$ to the chosen replacement node.

taocpmathematicsalgorithmsvolume-3medium

Section 6.2.2: Binary Tree Searching

Exercise 14. [22] [22] Prove that the path length of the tree produced by Algorithm D with step D1.5 added is never more than the path length of the tree produced without that step. Find a case where step D1.5 actually decreases the path length.

Verified: no
Solve time: 4m26s

The original argument fails because it assumes a uniform “shift” of depths along the entire search path from $x$ to the chosen replacement node. In Algorithm D, only a very specific set of nodes changes depth: the deleted node, and the nodes in the single subtree that is physically reattached after removing the successor or predecessor. No global path compression occurs.

A correct proof must therefore track exactly which nodes change depth under each of the two possible choices in step D1.5.

1. Precise structure of Algorithm D in the two-child case

Let $x$ be the node to be deleted, with

$$ A = LLINK(x), \quad B = RLINK(x), $$

both non-null.

Let

  • $s$ be the inorder successor of $x$, i.e. the leftmost node in $B$,
  • $p$ be the inorder predecessor of $x$, i.e. the rightmost node in $A$.

Define:

  • $T_s'$: delete $x$, replace it by $s$, then delete $s$ from $B$,
  • $T_p'$: delete $x$, replace it by $p$, then delete $p$ from $A$.

These are exactly the two outcomes available to step D1.5.

2. Correct analysis of internal path length change

Let $P(T)$ be the internal path length.

Key observation

In both constructions:

  1. The node chosen ($s$ or $p$) moves into the position of $x$, decreasing its depth by exactly $\mathrm{depth}(y)$, where $y \in {s,p}$.
  2. The only other nodes whose depths change are those in the subtree that gets reattached when $y$ is removed from its original position.

No other node changes depth.

Case: successor $s$

Let $s$ be the leftmost node in $B$. Then $s$ has no left child. Let

$$ R(s) = RLINK(s). $$

When $s$ is removed from its parent in $B$, its right subtree $R(s)$ is reattached one level higher (to the parent of $s$). Hence:

  • every node in $R(s)$ decreases depth by $1$,
  • $s$ decreases depth by $\mathrm{depth}(s)$,
  • all other nodes keep their depth.

Therefore the total decrease in internal path length is:

$$ P(T) - P(T_s') = \mathrm{depth}(s) + |R(s)|. $$

So

$$ P(T_s') = P(T) - \mathrm{depth}(s) - |R(s)|. $$

Case: predecessor $p$

Symmetrically, $p$ is the rightmost node in $A$, and has no right child. Let

$$ L(p) = LLINK(p). $$

When $p$ is removed, its left subtree $L(p)$ is reattached one level higher, so:

$$ P(T_p') = P(T) - \mathrm{depth}(p) - |L(p)|. $$

3. Correct comparison of the two outcomes

Subtracting the two expressions:

$$ P(T_s') - P(T_p') = -\mathrm{depth}(s) - |R(s)| + \mathrm{depth}(p) + |L(p)|. $$

Thus the better choice is determined by maximizing the quantity

$$ F(y) = \mathrm{depth}(y) + |S(y)|, $$

where $S(y)$ is the subtree that gets shifted up when $y$ is removed ($R(s)$ for successor, $L(p)$ for predecessor).

Hence:

  • successor is better iff $F(s) \ge F(p)$,
  • predecessor is better iff $F(p) \ge F(s)$.

This shows that the effect of each choice is completely determined by local structural data of the two candidate nodes, not by any global path-shifting phenomenon.

4. Why step D1.5 never increases path length

Step D1.5 selects the choice (successor or predecessor) that gives the smaller resulting internal path length.

Therefore, if the original Algorithm D (without D1.5) corresponds to a fixed choice, say always using the successor, producing $T_s'$, then:

$$ P(T_{\text{D1.5}}) = \min(P(T_s'), P(T_p')) \le P(T_s'). $$

Hence the internal path length with D1.5 is never larger than without it.

No additional assumptions are required, since both $T_s'$ and $T_p'$ are valid outcomes of the same deletion operation, differing only in which of the two symmetric candidates is chosen.

5. A case where D1.5 strictly decreases path length

Construct a tree where the successor choice has a large reattached subtree, while the predecessor choice has a small one.

Let $x$ be the root.

  • Left subtree $A$: a single node $p$ with no children.
  • Right subtree $B$:

$$ x \to s \to b_1 \to b_2 \to b_3 $$

and additionally attach a large left subtree $U$ to $s$, where $|U| = m$, and all nodes in $U$ lie under $LLINK(s)$.

Then:

  • $p$ has no children, so $|L(p)| = 0$,
  • $s$ has large $R(s)$-type contribution through its right-side structure (or symmetrically, we can attach a large subtree to the successor side in the predecessor construction).

More concretely:

  • make $R(s)$ contain $m$ nodes,
  • keep $L(p)=\varnothing$.

Then:

$$ P(T_s') = P(T) - \mathrm{depth}(s) - m, \quad P(T_p') = P(T) - \mathrm{depth}(p). $$

For sufficiently large $m$,

$$ P(T_s') < P(T_p'). $$

Thus the successor choice yields strictly smaller internal path length, and step D1.5 selects it, producing a strict improvement over the opposite fixed rule.

Conclusion

  1. The original proof failed because it incorrectly assumed uniform depth decreases along the search path. In reality, only the chosen node and a single reattached subtree affect internal path length.
  2. The correct change in internal path length is

$$ P(T_y') = P(T) - \mathrm{depth}(y) - |S(y)|, $$

where $S(y)$ is the subtree shifted upward when $y$ is removed.

  1. Step D1.5 correctly selects the candidate minimizing this quantity, so it can only decrease (or preserve) internal path length relative to a fixed-choice version of Algorithm D.
  2. There exist trees where one candidate has a strictly larger shifted subtree, making D1.5 produce a strictly smaller path length.