In this program you will convert the BST from homework #2 to an AVL tree as the basis for your address book. Your program will appear the same as Program 2 to the user except that the "displayAll()" operation will additionally display the height and balance factor of each node within the tree. • The height of a node is the number of edges from the node to the deepest leaf. • The balance factor of a node is the difference in heights of its two subtrees. Internals Again, you will write (among other classes) a class Table that will store entries comprised of (key/value) pairs of Strings. This class will have the same public methods as did Program 2, and will include (at a minimum) the following additional private methods: • private void rebalance(Node n) • private Node rotateLeft(Node n) • private Node rotateRight(Node n) • private Node rotateLeftThenRight(Node n) • private Node rotateRightThenLeft(Node n) Table will now be implemented as an AVL tree. Each node will have two String fields (for the name and address), along with an int height field and an int balance field. Optionally, you may include a Node parent field along with the Node left and Node right. Your code may be implemented either recursively, iteratively, or as a combination of the two
