Question: //Part 4: Balanced tree The BSTSet does not keep the tree balanced, and we know that an unbalanced tree can make contains/add/remove operations take O(N)
//Part 4: Balanced tree The BSTSet does not keep the tree balanced, and we know that an unbalanced tree can make contains/add/remove operations take O(N) in the worst case instead of O(log N). To improve your Set implementation, you will complete a second class that uses a balanced binary search tree, AVLTreeSet. Notice that this class extends BSTSet, borrowing most of the functionality. We've provided implementations of add and remove that call a balancing method to fix the balance property after an insertion or removal. Your job will be to complete the balancing functionality by implementing two methods AVLTreeSet.rotateLeft AVLTreeSet.rotateRight See the comments above these methods to see a detailed description of what each method should do. Notice that the AVLTreeSet.balance method uses rotateLeft and rotateRight in combination to do the double rotation cases, so you don't have to directly implement double rotations. Tips: as in the remove implementation, you should use the updateParent method to change what node is at the top of the subtree. It will greatly simplify your code. Note that the rotation changes the height of the tree, so make sure to call updateHeight at the end. (Do not call updateHeightWholeTree) All of the tests in AVLTreeSetTest.java should pass when the rotate methods work//
public class AVLTreeSet
public AVLTreeSet(){
super();
}
public void add(T data){
super.add(data);
super.updateHeight( data);
this.balance(data);
}
public boolean remove(T data) {
if (super.remove(data)) {
super.updateHeight(data);
this.balance(data);
return true;
} else {
return false;
}
}
protected void checkIsBalanced(){
if (!isBalanced(this.root)) throw new IllegalStateException("tree is not balanced");
}
private void balance(T data) {
balanceHelper(root, data);
}
private void balanceHelper(TreeNode current, T data) {
if (current == null) {
return;
}
if (current.data.compareTo(data) != 0) {
if (current.data.compareTo(data) > 0 && current.left != null) {
balanceHelper(current.left, data);
} else if (current.data.compareTo(data) < 0 && current.right != null) {
balanceHelper(current.right, data);
}
}
//if balanced, return;
if (isBalanced(current)) {
return;
}
//reach this point if not balanced only.
if (getHeight(current.right) > getHeight(current.left)) //right heavy
{
if (getHeight(current.right.left) > getHeight(current.right.right)) {
rotateRight(current.right);
rotateLeft(current);
} else {
rotateLeft(current);
}
} else { //left heavy
if (getHeight(current.left.right) > getHeight(current.left.left)) {
rotateLeft(current.left);
rotateRight(current);
} else {
rotateRight(current);
}
}
}
/*
Perform a tri-node restructuring with a single left rotation
and return the new root of the tri-node
e.g.
If the method is called on
b
/ \
c a
/ \
d e
then the tri-node is b,a,e so the result is
a
/ \
b e
/ \
c d
and the method makes sure the parent of b now is the parent of a
*/
private void rotateLeft(TreeNode
// PART 4
}
/*
Perform a tri-node restructuring with a single right rotation
and return the new root of the tri-node
e.g.
If the method is called on
a
/ \
b e
/ \
c d
then the tri-node is a,b,c, so the result is
b
/ \
c a
/ \
d e
and the method makes sure the parent of a now is the parent of b
*/
private void rotateRight(TreeNode
// PART 4
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help