patternMinor
AVL tree worst case height proof
Viewed 0 times
caseheightproofavlworsttree
Problem
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.
I read somewhere about Fibonacci quicks but did not understand it.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#105871, answer score: 3
Revisions (0)
No revisions yet.