AVL Trees are yet another self balancing binary search tree (BST) that are sometimes used in...

  

Transcribed Image Text:

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(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 1. Let h be the height of an AVL tree and n be the number of nodes in the tree. The goal of this problem is to prove a relationship between h and n. We've broken this into two steps: (A) Prove thatn> F, where F, is the hh Fibonacci number. (Fo = 1, Fj = 1, F, = 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 h +1). Next, it is a fact that for any k > 30, F > 1.5k. (B) Using the above fact and the result from part A, show that h = O(log(n)). 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(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 1. Let h be the height of an AVL tree and n be the number of nodes in the tree. The goal of this problem is to prove a relationship between h and n. We've broken this into two steps: (A) Prove thatn> F, where F, is the hh Fibonacci number. (Fo = 1, Fj = 1, F, = 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 h +1). Next, it is a fact that for any k > 30, F > 1.5k. (B) Using the above fact and the result from part A, show that h = O(log(n)).