For this micro assignment, must implement the following AVL tree functions found inside AvlTree.java:
Balance
This function determines where the imbalance at root exists (either right child or left child) and calls the appropriate rotation function (rotateLeft / rotateRight). The AvlNode class contains a getBalanceFactor() function that returns the balance factor for the node.
RotateLeft / RotateRight
These functions rotate the supplied root pointer either left (rotateLeft) or right (rotateRight). Be sure to use the following rotation algorithms:
Left (counter-clockwise) Rotation
- Let CurrentRoot = the original root
- Let NewRoot = CurrentRoot's right child
- Set CurrentRoot's right child = NewRoot's left child
- Set NewRoot's left child = CurrentRoot
Right (clockwise) Rotation
- Let CurrentRoot = the original root
- Let NewRoot = CurrentRoot's left child
- Set CurrentRoot's left child = NewRoot's right child
- Set NewRoot's right child = CurrentRoot
Write Code where is "MA4 TOdO"
--------------------------->
public class AvlTree> extends Collection { //keeps track of the remove direction (left or right) private int _remove_counter = 0; //keeps track of BST size private int _size_counter = 0; protected AvlNode _root = null; //removes the largest element from the subtree starting at root protected AvlNode removeLargest(AvlNode root) { if (root == null) return root; //BASE CASE: root is largest (has no right node) if (root.getRightChild() == null) { AvlNode left = root.getLeftChild(); //return left node to parent return left; } else { //RECURSIVE CASE: AvlNode new_right = removeLargest(root.getRightChild()); root.setRightChild(new_right); return root; } } //removes the smallest element in the subtree starting at root //Updated: DIFFERENT from MA3. Now written with recursion too protected AvlNode removeSmallest(AvlNode root) { if (root == null) return root; //BASE CASE: root is smallest (has no left node) if (root.getLeftChild() == null) { AvlNode right = root.getRightChild(); //return right node to parent return right; } else { //RECURSIVE CASE: AvlNode new_left = removeSmallest(root.getLeftChild()); root.setLeftChild(new_left); return root; } } //MA4 TOdO: Implement me THIRD! ////The purpose of this function is to figure out where the imbalance occurs within root (left or right) //and return the result of the appropriate rotation (left or right) on root's child. protected AvlNode balance(AvlNode root) { //check for null roots first if (root == null) return root; AvlNode left = root.getLeftChild(); AvlNode right = root.getRightChild(); //MA4 TODO remove this return statement and fully implement! //Once you find the imbalance, you will need to either //return the result of rotateLeft or rotateRight return root; } //MA4 TOdO: Implement me SECOND! protected AvlNode rotateLeft(AvlNode root) { //check for null roots if (root == null) return root; //new root comes from right side AvlNode new_root = root.getRightChild(); //MA4 TODO: rotate left and return "new_root" return setHeight(new_root); } //MA4 TOdO: Implement me FIRST! protected AvlNode rotateRight(AvlNode root) { //check for null roots if (root == null) return root; //new root comes from left side AvlNode new_root = root.getLeftChild(); //MA4 TODO: rotate right and return "new_root" return setHeight(new_root); } protected AvlNode setHeight(AvlNode root) { //check for null roots if (root == null) return root; AvlNode left = root.getLeftChild(); AvlNode right = root.getRightChild(); //start at 1 because we assume null trees have height of -1 int height = 1; //add in larger of left or right heights int left_height = (left == null) ? -1 : left.getHeight(); int right_height = (right == null) ? -1 : right.getHeight(); height += (left_height < right_height) ? right_height: left_height; //reassign new height to root root.setHeight(height); //check to see if balance factor is out of balance int balance_factor = root.getBalanceFactor(); if (balance_factor < -1 || balance_factor > 1) { return balance(root); } return root; } protected AvlNode addElementHelper(AvlNode root, T item) { //BASE CASE: create new node if (root == null) { root = new AvlNode(); root.setValue(item); return root; } //else, use the same helper as in BST //RECURSIVE CASE: figure out which child to call //is "item" larger than us? if (item.compareTo(root.getValue()) > 0){ AvlNode right_child = root.getRightChild(); AvlNode result = addElementHelper(right_child, item); root.setRightChild(result); } else if (item.compareTo(root.getValue()) < 0) { //same as above, except switching from right to left AvlNode left_child = root.getLeftChild(); AvlNode result = addElementHelper(left_child, item); root.setLeftChild(result); } else { //duplicates, do nothing return root; } //For BST, this process would end //return root; //For AVL though, we need to return a balanced node return setHeight(root); } protected AvlNode removeElementHelper(AvlNode root, T item) { //use the same helper as in BST //null check if (root == null) return null; //three possibilities: // we found the item (root value == item) // item is less than root (item < root) // item is greater than root (item > root) if (item.equals(root.getValue())) { //increment removal counter _remove_counter++; //we found the item //do we remove from the left or right? if (_remove_counter % 2 == 0) { //check to see if left is not null if (root.getLeftChild() != null) { //left subtree remove //we need the largest from the left side AvlNode largest = findLargest(root.getLeftChild()); //take the largest's value, put inside root root.setValue(largest.getValue()); //having gotten the value, we can now remove the node from the tree AvlNode result = removeLargest(root.getLeftChild()); root.setLeftChild(result); return setHeight(root); } else { //else, delete the current root, return the result return setHeight(removeSmallest(root)); } } else { //right subtree remove if (root.getRightChild() != null) { AvlNode smallest = findSmallest(root.getRightChild()); root.setValue(smallest.getValue()); AvlNode result = removeSmallest(root.getRightChild()); root.setRightChild(result); return setHeight(root); } else { return setHeight(removeLargest(root)); } } } else if (item.compareTo(root.getValue()) < 0) { //item is less than root AvlNode result = removeElementHelper( root.getLeftChild(), //send along our left child item //and the same item ); root.setLeftChild(result); } else { //item is greater than root AvlNode result = removeElementHelper( root.getRightChild(), item ); root.setRightChild(result); } //similar to addElementHelper, need to balance the root return setHeight(root); } protected AvlNode findLargest(AvlNode root) { while(root != null && root.getRightChild() != null) root = root.getRightChild(); return root; } protected AvlNode findSmallest(AvlNode root) { while(root != null && root.getLeftChild() != null) root = root.getLeftChild(); return root; } //provide traverse method for the AVL tree public void traverse(AvlTreeTraversal traversal) { traversal.traverse(_root); }
@Override public void addElement(T item) { // TODO Auto-generated method stub _root = addElementHelper(_root, item); _size_counter++; } public void removeElement(T item) { _root = removeElementHelper(_root, item); _size_counter--; }
@Override public boolean isEmpty() { // TODO Auto-generated method stub return _root == null; }
@Override public int getSize() { // TODO Auto-generated method stub return _size_counter; } }
------------>
class AvlNodeextends Comparable>
{
// Constructors
AvlNode()
{
}
AvlNode(T v)
{
this(v, null, null);
}
AvlNode(T v, AvlNode lt, AvlNode rt)
{
value = v;
left = lt;
right = rt;
height = 0;
}
private T value; // The data in the node
private AvlNode left; // Left child
private AvlNode right; // Right child
private int height = 0; // Height
//As a habit, we are going to keep using getter/setter functions instead of accessing the property directly
public void setValue(T v)
{
value = v;
}
public T getValue()
{
return value;
}
public void setLeftChild(AvlNode l)
{
left = l;
}
public AvlNode getLeftChild()
{
return left;
}
public void setRightChild(AvlNode r)
{
right = r;
}
public AvlNode getRightChild()
{
return right;
}
public void setHeight(int h)
{
height = h;
}
public int getHeight()
{
return height;
}
//Balance factor that helps determines if the current node is balanced
public int getBalanceFactor()
{
int left_height = (left == null) ? -1 : left.getHeight();
int right_height = (right == null) ? -1 : right.getHeight();
return right_height - left_height;
}
}
