AVL tree worst case height proof

Question

The worst case height of AVL tree is $1.44 \log n$. How do we prove that? I read somewhere about Fibonacci quicks but did not understand it.

Answer 1

We want to show that the number of nodes $n$ in a height-balanced binary tree with height $h$ grows exponentially with $h$ and at least as fast as the Fibonacci sequence.

Let $N_h$ denote the minimum number of nodes in a height-balanced binary tree having height $h$. Recall that in a height-balanced binary tree of height $h$, the subtree rooted at one of the children of the root has height $h-1$, and the subtree rooted at the other child of the root has height $h-1$ or $h-2$. Thus, $N_h > N_{h-1} + N_{h-2}$. Thus, $N_h$ is at least $f_h$, the $h$th term of the Fibonacci sequence, where $f_h \approx \phi^h / \sqrt{5}$ and $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$.

So, if $n$ is the number of nodes in an AVL tree of height $h$, we have $n \ge \phi^h / \sqrt{5}$. Taking $\log_2$ of both sides, we get $h \le \frac{\log_2 n}{\log_2 \phi} + c = 1.4404 \log_2 n + c$, for some constant $c$. Thus, an AVL tree has height $h = O(\log n)$

An easier proof, if you don't care about the constants as much, is to observe that $N_h > N_{h-1}+N_{h-2} > 2N_{h-2}$. Hence, $N_h$ grows at least as fast as $\sqrt{2}^h$. So the number of nodes $n$ in a height-balanced binary tree of height $h$ satisfies $n > \sqrt{2}^h$. So $h \log_2 \sqrt{2} < \log n$, which implies $h < 2 \log n$.

Answer 2

Try and create the "worst" AVL tree, that is, the AVL tree in which the height is as large as possible, with as least nodes as possible.

Once you get to the Fibonacci sequence (the answer to the question above), you can use the fact the the $n$-th Fibonacci number is $O(\phi ^n)$ (where $\phi = 1.618\ldots$), it should be easy to conclude that the worst case height of the tree is $\log_\phi n = O(\log n)$.