TAOCP 6.2.3 Exercise 2
Let the search path for the insertion end at the new node $Q$, and let the path from the root $R$ to $Q$ be R = v_0, v_1, \dots, v_k = Q.
Exercise 2. [16] [16] Explain why the tree has gotten one level higher if we reach step A7 with B(S) = 0.
Verified: yes
Solve time: 2m35s
Let the search path for the insertion end at the new node $Q$, and let the path from the root $R$ to $Q$ be
$$ R = v_0, v_1, \dots, v_k = Q. $$
Recall from the algorithm that $S$ is the deepest node on this path such that $B(S) \neq 0$. The condition in the problem is that step A7 is reached with $B(S)=0$. Hence there is no node on the path from $R$ to $Q$ with nonzero balance factor before insertion, so
$$ B(v_i)=0 \quad \text{for all } 0 \le i < k. $$
Thus every internal node on the search path has two subtrees of equal height before insertion.
Local height effect at a node with balance factor $0$
Let $v$ be a node on the path with $B(v)=0$. Before insertion, suppose both subtrees of $v$ have height $h$. Then the height of $v$ is $h+1$.
The insertion occurs in exactly one subtree of $v$, increasing its height from $h$ to $h+1$, while the other subtree remains of height $h$. After insertion, the height of $v$ becomes
$$ \max(h+1, h) + 1 = h+2. $$
Hence the height of $v$ increases from $h+1$ to $h+2$, that is, it increases by exactly $1$. Moreover, its new balance factor becomes $\pm 1$, but this does not affect height propagation.
Propagation up the path
We apply the same argument inductively upward along the path.
Assume that for some node $v_i$, the height of its child on the search path increases by $1$, and that $B(v_i)=0$ before insertion. Then both subtrees of $v_i$ were originally of equal height, so the increase in one subtree forces the height of $v_i$ itself to increase by $1$, exactly as in the computation above.
Therefore, since every node $v_i$ on the path from $Q$ to $R$ has balance factor $0$ before insertion, the height increase propagates from $Q$ all the way up to the root without interruption or cancellation.
Conclusion
The root $R$ has its subtree height increased by $1$. Therefore the height of the entire tree increases by one level when step A7 is reached with $B(S)=0$.
This is precisely because a node with balance factor $0$ cannot absorb a unit increase in one subtree without increasing its own height, so no ancestor on the search path blocks the propagation of the height increase.