2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – John L. Mar 21 '19 at 13:05
  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Mar 21 '19 at 18:18
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.