An AVL tree is a binary search tree that is height balanced: for each node x, the heights of the left and right subtrees of x differ by at most 1. To implement an AVL tree, we maintain an extra attribute in each node: x.h is the height of node x. As for any other binary search tree T, we assume that T.root points to the root node. a. Prove that an AVL tree with n nodes has height O(lg n). (Hint: Prove that an AVL tree of height h has at least Fh nodes, where F is the hth Fibonacci number.)