### Height of an AVL-tree

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