Hello guys i seem to be having trouble rebalancing the AVL tree. It balances everything else except the root node. I don't know why it doesn't balance the root node. When i pass values such as 50, 40, 30, 20, and 10. I get 50,30, 20, 10 and 40. 50 should not be the root, the correct root value should be 40. Below is my code:
public void insert(T data){
AVLNode<T> newNode = new AVLNode<T>(data);
if(isEmpty()){
root = newNode;
}
else{
insert(root, newNode);
}
}
private void insert(AVLNode<T> root, AVLNode<T> newNode){
if(newNode.getData().compareTo(root.getData())<0){
if(root.getLeftChild()!=null){
AVLNode<T> leftNodes = root.getLeftChild();
insert(leftNodes, newNode);
root.setLeftChild(rebalance(leftNodes));
}
else{
root.setLeftChild(newNode);
}
}
else if(newNode.getData().compareTo(root.getData())>0){
if(root.getRightChild()!=null){
AVLNode<T> rightNodes = root.getRightChild();
insert(rightNodes, newNode);
root.setRightChild(rebalance(rightNodes));
}
else{
root.setRightChild(newNode);
}
}
else{
root.setData(newNode.getData());
}
updateHeight(root);
}
//re-balances the tree.
private AVLNode<T> rebalance(AVLNode<T> root){
int difference = balance(root);
if (difference > 1){
if(balance(root.getLeftChild())>0){
root = rotateRight(root);
}
else{
root = rotateLeftRight(root);
}
}
else if(difference < -1){
if(balance(root.getRightChild())<0){
root = rotateLeft(root);
}
else{
root = rotateRightLeft(root);
}
}
return root;
}
//updates the height of the tree.
public void updateHeight(AVLNode<T> root){
if((root.getLeftChild()==null) && (root.getRightChild()!=null)){
root.setHeight(root.getRightChild().getHeight()+1);
}
else if((root.getLeftChild() !=null)&&(root.getRightChild()==null)){
root.setHeight(root.getLeftChild().getHeight()+1);
}
else
root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1);
}
private int balance(AVLNode<T> root) {
return getHeight(root.getLeftChild())-getHeight(root.getRightChild());
}
//single left left rotation of the tree
private AVLNode<T> rotateLeft(AVLNode<T> root){
AVLNode<T> NodeA = root.getRightChild();
root.setRightChild(NodeA.getLeftChild());
NodeA.setLeftChild(root);
root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); //updates the height
NodeA.setHeight(Math.max(getHeight(NodeA.getLeftChild()), getHeight(NodeA.getRightChild()))+1);
return NodeA;
}
//single right right rotation of the tree
private AVLNode<T> rotateRight(AVLNode<T> root){
AVLNode<T> NodeA = root.getLeftChild();
root.setLeftChild(NodeA.getRightChild());
NodeA.setRightChild(root);
root.setHeight(Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()))+1); //updates the height of the AVL tree
NodeA.setHeight(Math.max(getHeight(NodeA.getLeftChild()), getHeight(NodeA.getRightChild()))+1);
return NodeA;
}
//a double rotation. Left right rotation
private AVLNode<T> rotateLeftRight(AVLNode<T> root){
AVLNode<T> nodeA = root.getLeftChild();
root.setLeftChild(rotateLeft(nodeA));
return rotateRight(root);
}
//a right left rotation
private AVLNode<T> rotateRightLeft(AVLNode<T> root){
AVLNode<T> nodeA = root.getRightChild();
root.setRightChild(rotateRight(nodeA));
return rotateLeft(root);
}
In your insert method, you should consider adding
Just before the call
at the end of the method. Then make sure to remove calls to rebalance before this. So, for example, change
to
Assuming the rest of your code works fine, this should be the fix. Then each of your nodes that is ever considered a local root will have the balancing method called on them.. including the absolute root of the tree.