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
