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