in python

13-3 AVL trees 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 nodex. 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(Ign). (Hint: Prove that an AVL tree of height h has at least Fh nodes, where Fh is the hth Fibonacci number.) b. To insert into an AVL tree, we first place a node into the appropriate place in bi- nary search tree order. Afterward, the tree might no longer be height balanced. Specifically, the heights of the left and right children of some node might differ by 2. Describe a procedure BALANCE(X), which takes a subtree rooted at x whose left and right children are height balanced and have heights that differ by at most 2, i.e., 1x.right.h-x.left.hl