TAOCP 6.2.2 Exercise 12
Let $Q$ be the node selected for deletion, chosen uniformly from the $N$ nodes of a binary search tree formed by random insertion of $N$ keys.
Section 6.2.2: Binary Tree Searching
Exercise 12. [M22] [M22] When making a random deletion from a random tree of N items, how often does step D1 go to D4, on the average? (See the proof of Theorem H.)
Verified: yes
Solve time: 1m13s
Solution
Let $Q$ be the node selected for deletion, chosen uniformly from the $N$ nodes of a binary search tree formed by random insertion of $N$ keys.
Step D1 goes to D4 exactly when
$$ \operatorname{RLINK}(T)=\Lambda, $$
where $T \leftarrow Q$. Hence the event “D1 goes to D4” is equivalent to “the right subtree of $Q$ is empty”.
Let $S$ denote the number of nodes in the subtree rooted at $Q$. Conditioning on $S=s$, the keys in this subtree arise from a random permutation of $s$ distinct keys, so the root of this subtree is equally likely to be any of the $s$ keys. The right subtree is empty exactly when the root is the maximum key in this subtree, which occurs for exactly one of the $s$ possibilities. Therefore,
$$ \Pr(\operatorname{RLINK}(Q)=\Lambda \mid S=s)=\frac{1}{s}. $$
Let $X_s$ be the number of nodes in the tree whose subtree size equals $s$. Then the probability that a uniformly chosen node has subtree size $s$ is $X_s/N$. The expected value of $X_s$ in a random binary search tree is known from the analysis of random binary trees (as used in Section 6.2.2) to be
$$ \mathbb{E}(X_s)=\frac{2N}{(s+1)(s+2)}. $$
Hence the probability that the randomly chosen node has subtree size $s$ is
$$ \frac{\mathbb{E}(X_s)}{N}=\frac{2}{(s+1)(s+2)}. $$
Let $P_N$ be the desired average probability that step D1 goes to D4. Then
$$ P_N=\sum_{s=1}^{N} \frac{2}{(s+1)(s+2)} \cdot \frac{1}{s} =\sum_{s=1}^{N} \frac{2}{s(s+1)(s+2)}. $$
The identity
$$ \frac{2}{s(s+1)(s+2)}=\frac{1}{s(s+1)}-\frac{1}{(s+1)(s+2)} $$
gives a telescoping sum:
$$ P_N=\sum_{s=1}^{N}\left(\frac{1}{s(s+1)}-\frac{1}{(s+1)(s+2)}\right) =\frac{1}{1\cdot 2}-\frac{1}{(N+1)(N+2)}. $$
Thus,
$$ P_N=\frac{1}{2}-\frac{1}{(N+1)(N+2)}. $$
This completes the derivation. ∎
$$ \boxed{\frac{1}{2}-\frac{1}{(N+1)(N+2)}} $$