CS210 Project 4
Bob Wilson
Implementing an AVL Tree
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 23 slides. That material will not be repeated here.
A UML diagram for the AVLTree program is shown in this figure:
There is a Project4.zip file that you should download to get started on this project. Unzip it and create a Dr Java project file in the directory. Open all of the Java source files in the new Dr Java project. 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.
Overall:
You must write comments in your code to document the design of your program. For this assignment, these comments must be written using the Java style single line comment by beginning a comment line with // or putting // and a comment at the end of a line of code. Try to make these comments useful to the programmer who will be reading them and not just an English re-statement of the contents of the line(s) of code.
Report (memo.txt):
For this project and all projects in this course, the memo.txt file that you upload to the turn-in system MUST BE A PLAIN TEXT FILE - NOT A WORD (.DOC or .RTF) FILE. On a Windows PC, I recommend that you use Notepad to create this file. On a MAC, you must use a suitable editor to create a plain text file. In this text file, answer these questions:
Does your solution for updating the balance factors preserve the order log n behavior for the addElement and removeElement methods? If so, explain why. If not, what is the big-O order of those methods now?
Suppose that I had given you this project based on keeping an attribute for the height of its sub-tree in each node instead of a balance factor. Would it be possible to implement an AVL rebalancing strategy on this design? Explain what might have to be done differently. (You don’t need to write any code for this alternative solution – just explain the possible differences.)
Turning in your Assignment:
Use the secure file transfer program to upload your Project4 folder containing your .java files and memo.txt file to your UNIX file directory: “account/cs210/Project4” where “account” is your account ID.
You must upload the files to our UNIX system before the posted deadline. You will get no credit for late submissions. Plan your time carefully so that you have enough time to upload your files. If you have not finished, upload your files on time anyway - even if the program does not work correctly yet. That way you are eligible for part credit on the assignment. If you upload your files more than once, only the most recent copy will be saved.
Sample Printouts:
********************************************************************************************
> run
AVLTestTree1
-->Add in order
forcing a sequence of left rotations.
Perform left
rotation around: a
Perform left
rotation around: c
Perform left
rotation around: b
Perform left
rotation around: e
-------------------------
State of
Root Element: d
Balance Factor: 0
Parent: null
Left Element: b
Balance Factor: 0
Parent: d
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
c
Balance Factor: 0
Parent: b
Right Element: f
Balance Factor: 0
Parent: d
Right Left Element:
e
Balance Factor: 0
Parent: f
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
-->Remove in the
same order
Perform left
rotation around: d
-------------------------
State of
----------------------------
-->Add in reverse
order forcing a sequence of right rotations.
Perform right
rotation around: g
Perform right
rotation around: e
Perform right
rotation around: f
Perform right
rotation around: c
-------------------------
State of
Root Element: d
Balance Factor: 0
Parent: null
Left Element: b
Balance Factor: 0
Parent: d
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
c
Balance Factor: 0
Parent: b
Right Element: f
Balance Factor: 0
Parent: d
Right Left Element:
e
Balance Factor: 0
Parent: f
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
-->Remove in the
same order
Perform right
rotation around: d
-------------------------
State of
----------------------------
-->Add in
balanced order to avoid any rotations.
-------------------------
State of
Root Element: d
Balance Factor: 0
Parent: null
Left Element: b
Balance Factor: 0
Parent: d
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
c
Balance Factor: 0
Parent: b
Right Element: f
Balance Factor: 0
Parent: d
Right Left Element:
e
Balance Factor: 0
Parent: f
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
-->Remove the
root each time
Perform right
rotation around: g
-------------------------
State of
----------------------------
> ********************************************************************************************
> run
AVLTestTree2
Left-Right Case 1
-------------------------
State of
Root Element: e
Balance Factor: -1
Parent: null
Left Element: b
Balance Factor: 1
Parent: e
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
c
Balance Factor: 1
Parent: b
Right Element: f
Balance Factor: 1
Parent: e
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
Removing: f
Perform left-right
rotation around: e
-------------------------
State of
Root Element: c
Balance Factor: 0
Parent: null
Left Element: b
Balance Factor: -1
Parent: c
Left Left Element: a
Balance Factor: 0
Parent: b
Right Element: e
Balance Factor: 0
Parent: c
Right Left Element:
d
Balance Factor: 0
Parent: e
Right Right Element:
g
Balance Factor: 0
Parent: e
----------------------------
Left-Right Case 2
-------------------------
State of
Root Element: e
Balance Factor: -1
Parent: null
Left Element: b
Balance Factor: 1
Parent: e
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
d
Balance Factor: -1
Parent: b
Right Element: f
Balance Factor: 1
Parent: e
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
Removing: f
Perform left-right
rotation around: e
-------------------------
State of
Root Element: d
Balance Factor: 0
Parent: null
Left Element: b
Balance Factor: 0
Parent: d
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
c
Balance Factor: 0
Parent: b
Right Element: e
Balance Factor: 1
Parent: d
Right Right Element:
g
Balance Factor: 0
Parent: e
----------------------------
Left-Right Case 3
-------------------------
State of
Root Element: f
Balance Factor: -1
Parent: null
Left Element: b
Balance Factor: 1
Parent: f
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
d
Balance Factor: 0
Parent: b
Right Element: g
Balance Factor: 1
Parent: f
Right Right Element:
h
Balance Factor: 0
Parent: g
----------------------------
Removing: g
Perform left-right
rotation around: f
-------------------------
State of
Root Element: d
Balance Factor: 0
Parent: null
Left Element: b
Balance Factor: 0
Parent: d
Left Left Element: a
Balance Factor: 0
Parent: b
Left Right Element:
c
Balance Factor: 0
Parent: b
Right Element: f
Balance Factor: 0
Parent: d
Right Left Element:
e
Balance Factor: 0
Parent: f
Right Right Element:
h
Balance Factor: 0
Parent: f
----------------------------
Left-Right Case 4
-------------------------
State of
Root Element: e
Balance Factor: -1
Parent: null
Left Element: b
Balance Factor: 1
Parent: e
Left Right Element:
c
Balance Factor: 0
Parent: b
Right Element: f
Balance Factor: 0
Parent: e
----------------------------
Removing: f
Perform left-right
rotation around: e
-------------------------
State of
Root Element: c
Balance Factor: 0
Parent: null
Left Element: b
Balance Factor: 0
Parent: c
Right Element: e
Balance Factor: 0
Parent: c
----------------------------
Right-Left Case 1
-------------------------
State of
Root Element: c
Balance Factor: 1
Parent: null
Left Element: b
Balance Factor: -1
Parent: c
Left Left Element: a
Balance Factor: 0
Parent: b
Right Element: f
Balance Factor: -1
Parent: c
Right Left Element:
e
Balance Factor: -1
Parent: f
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
Removing: b
Perform right-left
rotation around: c
-------------------------
State of
Root Element: e
Balance Factor: 0
Parent: null
Left Element: c
Balance Factor: 0
Parent: e
Left Left Element: a
Balance Factor: 0
Parent: c
Left Right Element:
d
Balance Factor: 0
Parent: c
Right Element: f
Balance Factor: 1
Parent: e
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
Right-Left Case 2
-------------------------
State of
Root Element: c
Balance Factor: 1
Parent: null
Left Element: b
Balance Factor: -1
Parent: c
Left Left Element: a
Balance Factor: 0
Parent: b
Right Element: f
Balance Factor: -1
Parent: c
Right Left Element:
d
Balance Factor: 1
Parent: f
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
Removing: b
Perform right-left
rotation around: c
-------------------------
State of
Root Element: d
Balance Factor: 0
Parent: null
Left Element: c
Balance Factor: -1
Parent: d
Left Left Element: a
Balance Factor: 0
Parent: c
Right Element: f
Balance Factor: 0
Parent: d
Right Left Element:
e
Balance Factor: 0
Parent: f
Right Right Element:
g
Balance Factor: 0
Parent: f
----------------------------
Right-Left Case 3
-------------------------
State of
Root Element: c
Balance Factor: 1
Parent: null
Left Element: b
Balance Factor: -1
Parent: c
Left Left Element: a
Balance Factor: 0
Parent: b
Right Element: g
Balance Factor: -1
Parent: c
Right Left Element:
e
Balance Factor: 0
Parent: g
Right Right Element:
h
Balance Factor: 0
Parent: g
----------------------------
Removing: b
Perform right-left
rotation around: c
-------------------------
State of
Root Element: e
Balance Factor: 0
Parent: null
Left Element: c
Balance Factor: 0
Parent: e
Left Left Element: a
Balance Factor: 0
Parent: c
Left Right Element:
d
Balance Factor: 0
Parent: c
Right Element: g
Balance Factor: 0
Parent: e
Right Left Element:
f
Balance Factor: 0
Parent: g
Right Right Element:
h
Balance Factor: 0
Parent: g
----------------------------
Right-Left Case 4
-------------------------
State of
Root Element: e
Balance Factor: 1
Parent: null
Left Element: b
Balance Factor: 0
Parent: e
Right Element: g
Balance Factor: -1
Parent: e
Right Left Element:
f
Balance Factor: 0
Parent: g
----------------------------
Removing: b
Perform right-left
rotation around: e
-------------------------
State of
Root Element: f
Balance Factor: 0
Parent: null
Left Element: e
Balance Factor: 0
Parent: f
Right Element: g
Balance Factor: 0
Parent: f
----------------------------
> ********************************************************************************************