Description
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
- The balance factor of a node is the difference in heights of its two
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. All other specifications from homework #2 carry over.
To turn in: As before, you will turn in a well documented source listing via Blackboard.
Rubric for HW3 (10 points):
- Read in and populate BST: 2 points
- Properly save, so that the file may be re-read and processed: 2 points
- Professional looking code/comments: 2 points
- All other functionality: 4 points
