1 Q1: AVL trees (3 points) Assume you are given access to functions Left Rotate(T, 2), RightRotate(T, 1) which perform the rotations at the node r. (See Section 13.2 in CLRS for the pseudocode.) Write the pseudocode for a function Insert(T, k) which given the pointer to the root and a value k, inserts k and returns the pointer of the root. Augment the tree with an attribute v.h which stores the height of each node. (1 point) For a tree containing n elements, storing the height attribute takes O(log log n) bits. Suggest a simple modification to this attribute that uses just O(1) bits but suffices for AVL tree operations. 1 Q1: AVL trees (3 points) Assume you are given access to functions Left Rotate(T, 2), RightRotate(T, 1) which perform the rotations at the node r. (See Section 13.2 in CLRS for the pseudocode.) Write the pseudocode for a function Insert(T, k) which given the pointer to the root and a value k, inserts k and returns the pointer of the root. Augment the tree with an attribute v.h which stores the height of each node. (1 point) For a tree containing n elements, storing the height attribute takes O(log log n) bits. Suggest a simple modification to this attribute that uses just O(1) bits but suffices for AVL tree operations