Why Balance Keeps the Tree Short

Since the start of the chapter we have relied on one claim: keeping every node balanced keeps the tree short, so the height stays about $\log n$ whatever order the values arrive in.

The balance property says a node’s two subtrees differ in height by at most one. So a node cannot have one tall subtree and one almost-empty one: if one subtree has height $3$, the other has height at least $2$. Every extra level of height needs nodes on both sides, so the node count grows much faster than the height.

To make this precise, we ask how tall an AVL tree of $n$ nodes can get. We answer it by asking the reverse question: for a given height $h$, what is the fewest nodes an AVL tree that tall could possibly have? An AVL tree that tall with only that many nodes is as lean as the balance property allows. It is the most lopsided shape the property still permits. This is the minimal AVL tree of height $h$. In the search tree chapter we saw that a perfect binary tree of height $h$ has $2^{h+1}-1$ nodes. That is the most nodes a height-$h$ tree can have. The minimal AVL tree is the other extreme.

The minimal AVL tree of height $0$ is a single leaf: $1$ node. The minimal AVL tree of height $1$ is a root with one child: $2$ nodes.

At height $2$, the root has to reach down two levels on one side, so it needs a subtree of height $1$ beneath it. The balance property then forbids the other side from being empty; it has to be at least height $0$. The way to satisfy both with the fewest nodes is a height-$1$ subtree on one side and a single node on the other:

       ╭───╮
       │ 7 │
       ╰─┬─╯
    ┌────┴─────┐
  ╭─┴─╮      ╭─┴─╮
  │ 5 │      │ 9 │
  ╰─┬─╯      ╰───╯
  ┌─┘
╭─┴─╮
│ 3 │
╰───╯

The total node count is $4$, which is one more than the sum of the node counts of the two subtrees: $1+2+1=4$.

The same pattern works at every height: the minimal AVL tree of height $h$ is a root on top of the minimal AVL trees of heights $h-1$ and $h-2$. For height $3$, the count is $1+4+2=7$. The counts form the sequence

$$1,2,4,7,12,20,\dots$$

This is a Fibonacci-like sequence, and it grows exponentially. We do not need the exact formula here. We only need the growth rate: the node count more than doubles every two levels.

The minimal AVL tree of height $h$ has the fewest nodes of any AVL tree of that height, so every AVL tree of height $h$ has at least that many. So with only $n$ nodes, the height cannot exceed a constant times ${\log }_{2}n$. (The exact constant works out to about $1.44$.) Whatever order the values arrive in, an AVL tree of $n$ nodes stays about $\log n$ tall.