A binary search tree with automatic detection of imbalances and rotations to keep it balanced can be implemented using the AVL Strategy. The AVL strategy includes a balance factor attribute in the AVLBinarySearchTreeNode class. The balance factor is used as described in the textbook and CS210 lecture slides. That material will not be repeated here.

A UML diagram for the AVLTree program is shown in this figure:

There is a ZIP file (linked above) that you should download to get started on this project. Unzip it and open all of the Java source files. Study the code and comments to understand the framework of this AVL tree implementation. Some critical pieces of the solution have been omitted. In particular, the code that detects which rotation(s) to perform and the code that updates the balance factors after a rotation are missing. You need to figure out the design for these missing pieces and write your own code to complete this project. This is a tricky project! Do not wait too long to get started or you will not be able to finish on time!

In the AVLBinarySearchTreeNode class, the balanceFactor and parent attributes have already been added. All attributes have protected visibility so that they can be directly accessed by code in the other project classes without needing to use any accessor or mutator methods. You do not need to make any changes here.

In the AVLLinkedBinarySearchTree class:

The addElement and removeElement methods already have the additional code needed to update the balance factors during an add or a remove operation and return up the tree rebalancing. These methods stop returning up the tree to continue rebalancing in two situations:

1. If a rotation is performed because no more than one rotation should ever be needed.

2. If the add or remove operation did not change the height of the affected node's subtree because it can not affect the balance factor of its parent's node or any other ancestor's node. For example, adding a left child to a node that already has a right child changes its balance factor, but does not change the balance factor of its parent or of any ancestor.

You should study this code to see how it works. You do not need to make any changes here.

Note that the removeElement method is implemented quite differently from the equivalent code in the text book and lecture notes. The element reference from the replacement node is copied into the node that originally contained the element reference being removed. This continues down to a leaf node. The leaf node object is removed but that node's ancestor node objects are not re-linked in the tree structure. You should compare this strategy with the one in the textbook and the lecture notes to understand how it works. It is not necessarily better, but it is instructive to see a different way to accomplish the same result.

In the rebalance method, most of the code is missing. The existing code is only a debug stub. Your code must look at the balance factors of the node provided as a parameter and of that node's left or right child as appropriate, decide if a rotation is required or not, and call the correct sequence of rotateLeft and/or rotateRight methods for one of the node's child nodes and/or for the node itself. Your code should return true if it decides to perform a rotation otherwise return false.

Note: In order to match the sample outputs, you need to include the following diagnostic code for each of the four cases of rotations:

System.out.println("Perform ******* rotation around: " + node);

Fill in the "*******" with the type of rotation being performed, e.g. left-right.

In the rotateLeft and rotateRight methods, the code for performing the rotation itself is provided, but the code for updating the balance factors after the rotation is missing. Due to the nature of the rotation process, only the pivot node's and the newPivot node's balance factors need to be updated based on the previous values of their balance factors. The balance factors for all other nodes will remain the same after the rotation. You need to analyze all the possible cases and develop the logic required. (Note that either of these methods could be called on a node that is a child of the original unbalanced node, e.g. the first part of a left-right or right-left rotation. Therefore, the balance factor of the pivot may not be +2 or -2. Your code must handle the balance factor update for a left or right child as the pivot with one of its child nodes as the newPivot as well as the balance factor update for the original unbalanced node as the pivot with its left or right child node as the newPivot.)

Some Tips:

Two JUnit test case files have been provided to help you test the overall code while you are developing your solution for the missing pieces. AVLTestTree1 tests left and right rotations. AVLTestTree2 tests left-right and right-left rotations. You may want to study this test case code to help you figure out the correct design for the missing pieces. Each JUnit test case file has multiple test methods that check for the correct behavior and a main method that can be run to get a more detailed blow by blow printout of the behavior of your solution for the same test cases. Correct sample printouts from these main methods are shown at the end of this document. Once completed, your solution should obtain these same results.

Work on the logic for the single left and single right rotations first. You can test those with AVLTestTree1. Then, add the logic for the left-right and right-left rotations and test with AVLTestTree2.