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?

Solution

Answer:

Expression of the minimum number of nodes in an AVL tree :

N(h) = N(h - 1) + 1 + N(h - 2 )

   = 1 , h = 0

= 2 , h = 1

Now , when h = 3

N(3) = N(3 - 1) + 1 + N( 3-2)

   = N(2) + 1 + N(1)

   = 4 + 1 + 2 = 7

N(4 ) = N(3) + 1 + N(2)

= 7 + 1 + 4 = 12

N(5) = N(4) + 1 + N(3)

   = 12 + 1 + 7 = 20

N(6) = N(5) + 1 + N(4)

   = 20 + 1 + 12 = 33

N(7) = N(6) + 1 + N(5)

   = 33 + 1 + 20 = 54

N(8) = N(7) + 1 + N(6)

   = 54 + 1 + 33 = 88

N(9) = N(8) + 1 + N(7)

   = 88 + 1 + 54 = 143

N(10) = N(9) + 1 + N(8) = 143 + 88 + 1 = 232

N(11) = N(10) + N(9) + 1 = 232 + 1 + 143 = 376

N(12) = N(11) + N(10) +1 = 376 + 232 + 1 = 609

N(13) = N(12) + N(11) +1 = 609 + 376 + 1 = 986

N(14) = N(13) + N(12) +1 = 986 + 609 + 1 = 1596

N(15) = N(14) + 1 + N(13) = 1596 + 1 + 986 = 2583

Therefore number of nodes in an avl tree of height h = 2583