AVL Trees are yet another self balancing binary search tree (BST) that are sometimes used in the place of red black trees. The key property of an AVL tree is that

for all nodes n in the tree, || height(.left)height(.right)||1| height(n.left)height(n.right)|1

In words, the height of the left subtree and right subtree at any node can differ by at most 11. Let h be the height of an AVL tree and n be the number of nodes.

(A) Prove that nFh, where Fh is the hth Fibonacci number. (0=1,1=1,2=2,F0=1,F1=1,F2=2,) (Hint Use strong induction with two base cases. First establish the property for all AVL trees of heights 0 and 1. Next, assuming it holds for trees of height h, prove it for trees of height +1h+1 ).

(B) Using the fact that 1.5Fk1.5k for 30k30, show that =(log())