Question & Answer: Let M(h) be the minimum number of nodes in an AVL tree of height h. In such a tree it can be shown that M(h) = M(h-1) + M(…..

Let M(h) be the minimum number of nodes in an AVL tree of height h. In such a tree it can be shown that M(h) = M(h-1) + M(h-2) + 1. [You don’t need to know why to answer this question but it is based on the minimum nodes in the left subtree and right subtree plus the root.] Now using this fact, prove using mathematical induction that M(h) = F(h+3) – 1 where F(0) = 0, F(1) = 1, F(x) = F(x-1) + F(x-2) for x>1.

Expert Answer

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

We need to prove by induction
M(h) = F(h+3) – 1 Where F{0} = 0, F(1) = 1, F(x) = F(x-1) + F(x-2)

The basic step h = 0 , we get M(h) as follows:

M(0) = F(3) -1
= F(2) + F(1) -1
= F(1) + F(0) + F(1) -1
= 1 + 0 + 1 -1
= 1 (Which is true)

Let us assume this holds for h = k then we need to prove for k+ 1 that

M(k+1) = F(k+4) – 1

Proof:
M(k+1) = M(k) + M(k-1) + 1   // As per the fact
= F(k+3) -1 + F(k+2) -1 + 1   As per the assumption which is true up to h=k
= F(k+3) + F(k+2) – 1
= F(k+4) -1             // As F(x) = F(x-1) + F(x-2)

Hence proved

Still stressed from student homework?

Get quality assistance from academic writers!

Order now