Height of an AVL-tree

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