Height of an AVL-tree

Posted on April 21, 2011 by phimuemue

I came across the following question lately: Show that the height of an AVL-tree is $$O(\log n)$$. To do so, we consider the following: An AVL-tree of height 1 resp. 2 has exactly 1 resp. 2 nodes.

Now, we argument as follows: An AVL-tree of height $$h$$ has a root, which must have two subtrees. These subtrees must have heights either $$h-1$$ and $$h-1$$ or $$h-1$$ and $$h-2$$ (w.l.o.g.). This is the basic property of AVL-trees.

Now we can argument as follows: We denote the number of nodes in an AVL-tree of height $$h$$ by $$N_h$$.

As seen before, we can establish the following recurrence formula: $$N_h\geq N_{h-1}+N_{h-2}$$, which is just a slightly modified version of the fibonacci sequence. We know that $$F_h \in \Omega(1.6^h)$$ ($$F_h$$ denotes the $$h$$-th fibonacci number), which implies that there is a $$c>0$$ such that for all sufficiently large values of $$h$$ we have $$F_h \geq c \cdot 1.6^h$$.

Up to now, we know that $$N_h \geq F_h \geq c \cdot 1.6^h$$ ($$c$$ specified as before). We can now compute the following by taking the logarithm (base 1.6) on both sides: $$\log_{1.6}(\frac{N_h}{c}) \geq h$$, which completes the proof.

Note that there are more accurate proofs concerning the height of an AVL-tree, but the simplicity of the above proof speaks for itself (in my opinion).