The goal of this assignment is to write and test a self-balancing search tree implementation. You may choose any implementation covered in the book (AVL, 2–3, 2–4, Red–Black) or any other published self-balancing search tree implementation that you can find. This assignment is optional, but you'll learn really deeply about AVL trees if you choose to do that implementation; they're pretty hard to understand if you don't take the time to code them up.
This is optionally a partner assignment.
SelfBalancingSearchTreeImplementation that implements this interface. (Yes, it would be better for the class name to explicitly specify which implementation you've written, but that makes it harder for me to test your code.)Write a main method in your class that extensively tests your implementation (which you will write later).
As part of this method, print out statistics about the balance of your tree after every meaningful sequence of operations, as well as its overall height and size. It will not always be straightforward to predict in advance the exact values of the balance properties of your tree, so there's no need to write tests that check them; just print them out so you can manually monitor that your tree is indeed staying balanced. Make sure to give it difficult input in this regard.
Fill in SelfBalancingSearchTreeImplementation with an implementation of your choice. Clearly specify in the class's docstring which implementation you're doing (AVL, 2–3, etc.).
You are not required to implement every method. Only the following are strictly required: contains(), add(), height(), size(), clear(), isEmpty(), and inOrderTraversal(). For any remaining methods in the interface, you're free to instead just throw an UnsupportedOperationException.
Zip up your SelfBalancingSearchTreeImplementation.java and any additional ADT or implementation files needed for your implementation into hw19.zip and submit it on Moodle.