Next:5.1.2
AVL Trees: Insertions and DeletionsUp:5.1
AVL TreesPrevious:5.1
AVL Trees
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 h2.

Suppose F_{l} has height h1 so that F_{r}
has height h2. Note that F_{r} has to be an AVL tree having
the minimum number of nodes among all AVL trees with height of h1. Similarly,
F_{r} will have the minimum number of nodes among all AVL
trees of height h2. 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_{0}
= 1 and  F_{1} = 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


h
1.44log F_{n}


The sparsest possible AVL tree with n nodes has height


h
1.44log n


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

Next:5.1.2
AVL Trees: Insertions and DeletionsUp:5.1
AVL TreesPrevious:5.1
AVL Trees
eEL,CSA_Dept,IISc,Bangalore