TAOCP 6.2.3 Exercise 12
Let $T_7$ denote a balanced binary tree with $7$ internal nodes.
Exercise 12. [24] [24] What is the maximum possible running time of Program A when the eighth node is inserted into a balanced tree? What is the minimum possible running time for this insertion?
Verified: no
Solve time: 1m27s
Solution
Let $T_7$ denote a balanced binary tree with $7$ internal nodes. Since a binary tree of height $2$ can contain at most $1+2+4=7$ internal nodes, every such tree has height $h=3$ in the sense of Section 6.2.3, so every search path from the root to an external node contains exactly three comparisons in steps A2–A4 before step A5 is reached.
Insertion of the eighth node is performed by Algorithm A. The running time is determined by the length of the search path in A1–A4 and the subsequent work in A5–A10.
Structure of the initial tree
All $7$-node balanced trees have every node of balance factor $B(P)=0$, since each subtree has equal height. The shape is therefore the perfect binary tree with one node at level $0$, two nodes at level $1$, and four nodes at level $2$.
Every external node lies at level $3$.
Search phase (A1–A4)
The pointer $P$ descends one level per iteration of A2–A4 until an external node is reached.
Since the height is $3$, the search executes exactly three comparisons in A2. After the third move, either A3 or A4 creates a new node in step A5.
No earlier termination is possible because all $7$ keys are distinct and the external position is reached only after descending from the root through level $1$ and level $2$.
Minimum running time
The minimum occurs when no rebalancing beyond trivial updates is required.
This happens when step A7 is reached with $B(S)=0$. In this case, step A7(i) applies:
$B(S)\leftarrow a,\qquad LLINK(HEAD)\leftarrow LLINK(HEAD)+1,$
and the algorithm terminates immediately.
No execution of A8, A9, or A10 occurs.
The total work consists of:
The three comparisons in A2 along the search path, the single insertion in A5, and the update phase A6 along the path from $S$ to $Q$. In the present situation $S=HEAD$ and the update in A6 affects exactly the nodes on the search path, which are the three nodes visited by $P$ before insertion.
No additional structural modification occurs after A7(i).
Hence the minimum running time corresponds to the case in which the algorithm performs search, insertion, and a single balance update at $S$, with no rotations.
Maximum running time
The maximum occurs when step A7(iii) is triggered, since this is the only situation in which structural rebalancing is required.
This requires a configuration in which the insertion increases the height of one subtree of a node $S$ already having $B(S)=\pm 1$, and the balance condition is violated at $S$ after step A6. For a $7$-node perfect tree, this can occur at the root when the new key is inserted into a subtree whose root already has balance factor $\pm 1$ after the update phase propagates along the search path.
In this case, step A7 directs execution to either A8 or A9.
If $B(R)=a$, step A8 executes a single rotation, modifying exactly the links at $S$ and $R$ and resetting
$B(S)=B(R)=0.$
If $B(R)=-a$, step A9 executes a double rotation. This replaces a local configuration of three nodes by a new rooted configuration at $P$ and updates three balance factors according to equation (3), followed by setting $B(P)\leftarrow 0$.
After either A8 or A9, step A10 performs the final attachment to the parent node $T$.
Thus the maximum running time occurs when the search path of length $3$ is followed by:
one execution of A5, one execution of A6 along the full path, the full case (iii) test in A7, and the additional structural transformations of either A8 or A9 together with A10.
The double rotation case requires strictly more pointer changes than the single rotation case, so it determines the maximum.
Result
The minimum running time corresponds to case A7(i) with no rotations, and the maximum running time corresponds to case A7(iii) with a double rotation.
Hence the insertion of the eighth node requires
$\boxed{\text{minimum: search + insertion + no rotation}}$
and
$\boxed{\text{maximum: search + insertion + double rotation + final attachment}}$
with both cases sharing the same three-step search phase determined by the height $h=3$ of the initial balanced tree. ∎