Complete the implementation of the AVLTree class provided in the archive. These trees (which are described in Section 9.4 of the course notes and in this Wikipedia article) maintain the AVL Property: For any node, u, the difference in height between u.left and u.right is at most 1.
Finish the code for rotateRight(u) and rotateLeft(u) so that, after the rotation is performed, the values of u.h and u.parent.h are correctly recomputed.
Finish the code for fixup(u) so that it ensures that it restores the AVL property at every node on the path from u to the root, r. At any node on this path, the difference in height between its left and right subtree will be at most 2, this must be reduced to 1 or 0.
In your testing and debugging, you should use the checkHeights(u) method extensively to ensure that your tree is a valid AVL tree after every operation.
