For this micro assignment, must implement the following AVL tree functions found inside AvlTree.java: Balance This function
Question:
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
@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 AvlNode
{
// Constructors
AvlNode()
{
}
AvlNode(T v)
{
this(v, null, null);
}
AvlNode(T v, AvlNode
{
value = v;
left = lt;
right = rt;
height = 0;
}
private T value; // The data in the node
private AvlNode
private AvlNode
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
{
left = l;
}
public AvlNode
{
return left;
}
public void setRightChild(AvlNode
{
right = r;
}
public AvlNode
{
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;
}
}
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill