# AVL tree worst case height proof

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.

• Can you recall where you read about Fibonacci quick? Have you tried proving it by yourself? Please edit the question to show what research you have done and how much progrogress you have made. – John L. Mar 21 '19 at 13:05
• Possible duplicate of AVL trees are not weight-balanced?. Although the two questions are different, the answer to that question contains a nice explanation of the worst-case height of an AVL tree. – John L. Mar 21 '19 at 18:18

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$$.
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)$$.