TAOCP 6.2.2 Exercise 11
We restart the counting from the actual behavior of step D3, since the previous argument misidentified what is being counted.
Section 6.2.2: Binary Tree Searching
Exercise 11. [20] [20] What is the maximum number of times the assignment S + LLINK(R) might be performed in step D3, when deleting a node from a tree of size N?
Verified: yes
Solve time: 2m30s
We restart the counting from the actual behavior of step D3, since the previous argument misidentified what is being counted.
Let $R_0 = \mathrm{RLINK}(T)$. In step D3 we repeatedly execute
$$ S \leftarrow \mathrm{LLINK}(R), $$
and then test whether $\mathrm{LLINK}(S) = A$. If not, we set $R \leftarrow S$ and continue. Hence each iteration advances one step down the left-link chain starting at $R_0$, and the loop terminates exactly when $S$ is the first node on this chain whose left link is null.
Let us describe the sequence of nodes visited. Define
$$ R_0, R_1, R_2, \dots, R_k $$
where
$$ R_{i+1} = \mathrm{LLINK}(R_i), $$
and $R_k$ is the first node with $\mathrm{LLINK}(R_k) = A$. This is exactly the leftmost chain reachable from $R_0$.
Now observe the key point: in each iteration of the loop, the assignment $S \leftarrow \mathrm{LLINK}(R)$ is executed once, and $S$ becomes the next node $R_{i+1}$. This happens even in the final iteration when $R_k$ is reached. Therefore, the assignment is executed once for every node $R_1, R_2, \dots, R_k$, and also for the step that produces $R_k$. In total, it is executed once per node on the chain from $R_0$ down to $R_k$.
Hence, the number of executions is exactly the number of nodes in this left-link chain starting at $R_0$.
If this chain contains $m$ nodes, then the assignment is executed $m$ times.
Now we bound $m$. The chain lies entirely within the subtree rooted at $R_0$, which contains at most $N-1$ nodes because $T$ itself is not in that subtree. Therefore,
$$ m \le N - 1. $$
This bound is achievable: if all $N-1$ nodes in the subtree rooted at $R_0$ form a single left-linked chain, then each iteration advances exactly one node along this chain until the last node is reached, and every node contributes one execution of the assignment.
Therefore, the maximum possible number of executions of
$$ S \leftarrow \mathrm{LLINK}(R) $$
in step D3 is
$$ \boxed{N - 1}. $$