TAOCP 6.2.3 Exercise 19

Let $S$ be the root of a balanced binary tree in the sense of Section 6.

taocpmathematicsalgorithmsvolume-3hard

Section 6.2.3: Balanced Trees

Exercise 19. [26] [26] Find a way to transform a given balanced tree so that the balance factor at the root is not, 1. Your transformation should preserve the symmetric order of the nodes; and it should produce another balanced tree in O(1) units of time, regardless of the size of the original tree.

Verified: yes
Solve time: 3m33s

Let $S$ be the root of a balanced binary tree in the sense of Section 6.2.3, with

$$ B(P)=\mathrm{height}(\mathrm{RLINK}(P))-\mathrm{height}(\mathrm{LLINK}(P)). $$

Assume $B(S)=-1$. Let

$$ L=\mathrm{LLINK}(S), \quad R=\mathrm{RLINK}(S), $$

so

$$ \mathrm{height}(L)=\mathrm{height}(R)+1. $$

We construct, in $O(1)$ pointer changes, a new balanced tree with the same symmetric order whose root balance factor is not $-1$.

1. Structural constraints at $S$ and $L$

Let $\mathrm{height}(R)=h$. Then $\mathrm{height}(L)=h+1$.

Write

$$ A=\mathrm{LLINK}(L), \quad B=\mathrm{RLINK}(L). $$

Since $L$ is balanced and has height $h+1$, we have

$$ \mathrm{height}(A)\le h,\quad \mathrm{height}(B)\le h, \quad \max(\mathrm{height}(A),\mathrm{height}(B))=h. $$

Thus at least one of $A,B$ has height $h$, and their heights differ by at most 1.

2. Case $B(L)\le 0$ (single rotation)

Pointer transformation

Perform a single right rotation at $S$:

  • $S$ becomes the right child of $L$,
  • $B$ becomes the left child of $S$.

Formally:

$$ \begin{aligned} \mathrm{LLINK}(S) &\gets B,\ \mathrm{RLINK}(L) &\gets S. \end{aligned} $$

All other links remain unchanged.

Structure after rotation

$$ \begin{array}{c} L \ / \ \backslash \ A \quad S \ \quad / \ \backslash \ \quad B \quad R \end{array} $$

Balance factor of the new root

We compute $B(L)$ after rotation.

Since $\mathrm{height}(R)=h$, and $\mathrm{height}(A),\mathrm{height}(B)\le h$:

  • If $\mathrm{height}(A)=\mathrm{height}(B)=h$ (original $B(L)=0$):

$$ \mathrm{height}(S)=h+1,\quad \mathrm{height}(L)=h+2, $$

hence $B(L)=1$.

  • If $\mathrm{height}(A)=h,\ \mathrm{height}(B)=h-1$ (original $B(L)=-1$):

$$ \mathrm{height}(S)=h+1,\quad \mathrm{height}(L)=h+2, $$

hence again $B(L)=1$.

Thus in all subcases,

$$ B(L)=1 \neq -1. $$

AVL validity

Every node involved ($A,B,S$) remains balanced since all height differences remain within 1 by construction. Hence the tree is balanced.

3. Case $B(L)=+1$ (double rotation)

Subtree notation

Let

$$ C=\mathrm{LLINK}(B), \quad D=\mathrm{RLINK}(B). $$

Initial structure:

$$ \begin{array}{c} S \ / \ \backslash \ L \quad R \ / \ \backslash \ A \quad B \ \ \ / \ \backslash \ \ C \quad D \end{array} $$

Since $B(L)=+1$, we have

$$ \mathrm{height}(B)=h,\quad \mathrm{height}(A)=h-1. $$

Because $B$ is balanced and has height $h$,

$$ \max(\mathrm{height}(C),\mathrm{height}(D))=h-1, \quad |\mathrm{height}(C)-\mathrm{height}(D)|\le 1. $$

Also $\mathrm{height}(R)=h$.

Step 1: left rotation at $L$

Perform:

$$ \begin{aligned} \mathrm{LLINK}(S) &\gets B,\ \mathrm{RLINK}(L) &\gets C,\ \mathrm{LLINK}(B) &\gets L. \end{aligned} $$

Now $B$ is the left child of $S$.

Step 2: right rotation at $S$

Perform:

$$ \begin{aligned} \text{new root} &:= B,\ \mathrm{RLINK}(B) &\gets S. \end{aligned} $$

The final structure is:

$$ \begin{array}{c} B \ / \ \backslash \ L \quad S \ / \ \backslash \quad / \ \backslash \ A \quad C \quad D \quad R \end{array} $$

4. Balance factor of the new root

We compute heights.

Subtree heights

  • $\mathrm{height}(A)=h-1$
  • $\mathrm{height}(C)\le h-1,\ \mathrm{height}(D)\le h-1$
  • Hence

$$ \mathrm{height}(L)=h $$

For $S$:

$$ \mathrm{height}(S)=1+\max(\mathrm{height}(D),\mathrm{height}(R))=1+\max(\le h-1,h)=h+1. $$

Thus:

$$ \mathrm{height}(L)=h,\quad \mathrm{height}(S)=h+1. $$

Root balance factor

$$ B(B)=\mathrm{height}(S)-\mathrm{height}(L)=(h+1)-h=1. $$

Hence

$$ B(B)=1 \neq -1. $$

AVL validity

Each subtree:

  • $L$: children heights differ by at most 1 since $A\le h-1$ and $C\le h-1$,
  • $S$: children heights differ by at most 1 since $D\le h-1$ and $R=h$,
  • $B$: root has balance factor $1$.

Thus all nodes remain in ${-1,0,+1}$, so the tree remains balanced.

5. Correctness and complexity

  • Both cases preserve inorder (symmetric) order since only standard AVL rotations are used.
  • Each transformation uses a constant number of pointer changes independent of the size of the tree.
  • Hence the running time is $O(1)$.

Conclusion

A single right rotation at $S$ when $B(L)\le 0$, and a standard LR double rotation when $B(L)=+1$, always produces a balanced tree whose root balance factor is $+1$. Therefore the root is never $-1$, and the transformation is constant time. ∎