give a precise expression for the minimum number of nodes in

give a precise expression for the minimum number of nodes in an AVL tree of height h. b. what is the minimum number of nodes in an AVL tree of height 15?

2. write the remaning procedures to implement AVL single and double rotations

Solution

1.a)

concept and explanation

Let S(h) be the minimum number of nodes in an AVL tree T of height h. The subtrees of an AVL tree with mimimum number of nodes must also have minimum number of nodes. Also, at least one of the left and right subtrees of T is an AVL tree of height h 1. Since the height of left and right subtrees can differ by at most 1, the other subtree must have height h 2.

//recurrence relation

so we have the following recurrence relation: S(h) = S(h 1) + S(h 2) + 1.

(1) We also know the base cases: S(0) = 1 and S(1) = 2. by substituting 0 and 1 in above recurrence relation

//methods of solving recurrence relatio

Guess the solution and prove it by induction.

Observe that the recurrence relation in (1) is very similar to the recurrence relation of Fibonacci numbers. When we look at the first a few numbers of the sequence S(h), it is not difficult to guess S(h) = F(h + 3) 1.So Now, lwe have to prove that S(h) = F(h + 3) 1.we do this by induction.

Base cases:

S(0) = 1, F(3) = 2. So S(0) = F(3) 1.

S(1) = 2, F(4) = 3. So S(1) = F(4) 1.

Induction hyprothesis: Assume that the hypothesis S(h) = F(h + 3) 1 is true for h = 1, · · · , k.

Inductive step: Prove that it is also true for h = k + 1. S(k + 1) = S(k) + S(k 1) + 1 = F(k + 3) 1 + F(k + 2) 1 + 1 = F(k + 4) 1. We replace S(k) and S(k 1) with their equivalence according to the hypothesis. Then, we get S(k + 1) = F(k + 4) 1. Hypothesis is also true for h = k + 1. Thus, it is true for all h.

b) S(15) = F(18) 1. //solve and substitute in the above relation