Part 4: Balanced tree The BSTSet does not keep the tree balanced, and we know that an unbalanced tree can make contains/add/remove operations take O(N) in the worst case instead of O(log N). To improve your Set implementation, you will complete a second class that uses a balanced binary search tree, AVLTreeSet. Notice that this class extends BSTSet, borrowing most of the functionality. We've provided implementations of add and remove that call a balancing method to fix the balance property after an insertion or removal. Your job will be to complete the balancing functionality by implementing two methods AVLTreeSet.rotateLeft AVLTreeSet.rotateRight See the comments above these methods to see a detailed description of what each method should do. Notice that the AVLTreeSet.balance method uses rotateLeft and rotateRight in combination to do the double rotation cases, so you don't have to directly implement double rotations. Tips: as in the remove implementation, you should use the updateParent method to change what node is at the top of the subtree. It will greatly simplify your code. Note that the rotation changes the height of the tree, so make sure to call updateHeight at the end. (Do not call updateHeightWholeTree) . . All of the tests in AVLTreeSetTest.java should pass when the rotate methods work