Height of an AVL-tree
I came across the following question lately: Show that the height of an AVL-tree is .
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 has a root, which must have two subtrees. These subtrees must have heights either and or and (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 by .
As seen before, we can establish the following recurrence formula: , which is just a slightly modified version of the fibonacci sequence. We know that ( denotes the -th fibonacci number), which implies that there is a such that for all sufficiently large values of we have .
Up to now, we know that ( specified as before). We can now compute the following by taking the logarithm (base 1.6) on both sides: , 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).