There is a question one of my practice exams which ask the following: Given a binary search tree with 23 nodes, what is the maximum height of this binary search tree if it also has the AVL property.
The first thing that came up to me was that the height of an avl tree must b smaller than 1.45log2(n). So using this formula with n = 23 i got something like 6.5, 7 if rounded up. But the answer to this questions seems to be 5. Is 1.44log2(n) not the practical maximum height? Why could the answer be 5?
In an AVL tree the balance factor must be between -1 and 1. If we start with a tree that has height 5 and then minimize the number of nodes such that are required to make it a valid AVL tree, we get to 20 nodes:
________*_________
/ \
_____*____ ___*__
/ \ / \
___*__ * * *
/ \ / \ / \ /
* * * * * * *
/ \ / / /
* * * * *
/
*
Now adding three more nodes is not enough to increase the height. If we would add a root above this tree, we don't have enough nodes to populate the right subtree below that new root (and keep the balance requirement). So the only valid option is to add those three nodes somewhere below the leaves of the above tree, and we cannot make the height greater than it already is.
So 5 is the answer.
We can also note this invariant: the minimal number of nodes in an AVL tree of height ā (i.e. ā is the number of edges on longest path from root to leaf) is š¹ā+3ā1, where š¹ is the Fibonacci sequence with š¹1 = š¹2 = 1.
The greatest Fibonacci number which is not greater than 24 is š¹8, which is 21. And so the maximum height is 8ā3 = 5.