5.1.1 Maximum Height of an AVL Tree

What is the maximum height of an AVL tree having exactly n nodes? To answer this question, we will pose the following question:

What is the minimum number of nodes (sparsest possible AVL tree) an AVL tree of height h can have ?

Let F_h be an AVL tree of height h, having the minimum number of nodes. F_h can be visualized as in Figure 5.2.

Let F_l and F_r be AVL trees which are the left subtree and right subtree, respectively, of F_h. Then F_l or F_r must have height h-2.

Suppose F_l has height h-1 so that F_r has height h-2. Note that F_r has to be an AVL tree having the minimum number of nodes among all AVL trees with height of h-1. Similarly, F_r will have the minimum number of nodes among all AVL trees of height h--2. Thus we have 

| F_h| = | F_{h - 1}| + | F_{h - 2}| + 1

where | F_r| denotes the number of nodes in F_r. Such trees are called Fibonacci trees. See Figure 5.3. Some Fibonacci trees are shown in Figure 4.20. Note that | F₀| = 1 and | F₁| = 2.

Adding 1 to both sides, we get 

| F_h| + 1 = (| F_{h - 1}| + 1) + (| F_{h - 2}| + 1)

Thus the numbers | F_h| + 1 are Fibonacci numbers. Using the approximate formula for Fibonacci numbers, we get 

| F_h| + 1 $$\approx$$$${\frac{1}{\sqrt{5}}}$$$$\left(\vphantom{\frac{1+\sqrt{5}}{2}}\right.$$$${\frac{1+\sqrt{5}}{2}}$$$$\left.\vphantom{\frac{1+\sqrt{5}}{2}}\right)^{h+3}_{}$$

$\Rightarrow$

h $\approx$ 1.44log| F_n|

$\Rightarrow$

The sparsest possible AVL tree with n nodes has height 

                                                                        h$$\approx$$ 1.44log n

$\Rightarrow$

The worst case height of an AVL tree with n nodes is 

                                                                                1.44log n

 

Figure 5.3: Fibonacci trees

 
 

Figure 5.4: Rotations in a binary search tree