Java – AVL Tree Balancing

avl-treejavatree-balancing

I am working on an assignment that asks me to implement an AVL tree. I'm pretty sure I have the rotation methods correct, but I'm having trouble figuring out when to use them.

For example, the explanation in the book says that I should climb up the same path I went down to insert the node/element. However, I can't have any parent pointers.

Latest code:

public BinaryNode<T> insert(BinaryNode<T> node) {
    if (this.getElement().compareTo(node.getElement()) > 0) {
        if (this.getLeftChild() != null) {
            BinaryNode<T> b = this.getLeftChild().insert(node);

            if(!this.isBalanced()) {
                this.balance();
            }

            return b;
        } else {
            this.setLeftChild(node);
        }

    } else if (this.getElement().compareTo(node.getElement()) < 0) {
        if (this.getRightChild() != null) {
            return this.getRightChild().insert(node);
        } else {
            this.setRightChild(node);
        }
    }

    return this;
}

What I want to do here is climb back up the tree, but it can only check the balancing AFTER it inserts the node. Hence, this being in the else clause.

I also tried putting the balance code where R Samuel Klatchko suggested, but checked the balance on each insert. For example: If one inserts 7, 9, 5, 3, and 1 consecutively, I get a null pointer exception when trying to insert 1.

EDIT: One reason for the above may have something to do with the way I was doing the height. It works fine with a single right rotation if I calculate the height every time with height() but that breaks the O(log(n)) time of an AVL Tree.

Any thoughts on how to accomplish this?

Best Answer

You code is climbing up the same path you went down. Consider this code:

if (this.getLeftChild() != null) {
    return this.getLeftChild().insert(node);
}

and modify it slightly:

if (this.getLeftChild() != null) {
    boolean b = this.getLeftChild().insert(node);
    // do something here
    return b;
}

As the code returns from the recursive calls, each return brings you back to the parent. By not immediately returning the value of the recursive call, you have a chance to do your rebalancing.

Update for latest code

Don't forget to rebalance when you've inserted to the right.

Part 1 - height

As starblue says, height is just recursive. In pseudo-code:

height(node) = max(height(node.L), height(node.R)) + 1

Now height could be defined in two ways. It could be the number of nodes in the path from the root to that node, or it could be the number of links. According to the page you referenced, the most common definition is for the number of links. In which case the complete pseudo code would be:

height(node): 
   if node == null:
        return -1
   else:
        return max(height(node.L), height(node.R)) + 1

If you wanted the number of nodes the code would be:

height(node): 
   if node == null:
        return 0
   else:
        return max(height(node.L), height(node.R)) + 1

Either way, the rebalancing algorithm I think should work the same.

However, your tree will be much more efficient (O(ln(n))) if you store and update height information in the tree, rather than calculating it each time. (O(n))

Part 2 - balancing

When it says "If the balance factor of R is 1", it is talking about the balance factor of the right branch, when the balance factor at the top is 2. It is telling you how to choose whether to do a single rotation or a double rotation. In (python like) Pseudo-code:

if balance factor(top) = 2: // right is imbalanced
     if balance factor(R) = 1: // 
          do a left rotation
     else if balance factor(R) = -1:
          do a double rotation
else: // must be -2, left is imbalanced
     if balance factor(L) = 1: // 
          do a left rotation
     else if balance factor(L) = -1:
          do a double rotation

I hope this makes sense

C++ – balancing an AVL tree (C++)

You can measure the height of a branch at a given point to calculate the unbalance

(remember a difference in height (levels) >= 2 means your tree is not balanced)

int Tree::Height(TreeNode *node){
     int left, right;

     if(node==NULL)
         return 0;
     left = Height(node->left);
     right = Height(node->right);
  if(left > right)
            return left+1;
         else
            return right+1;
}

Depending on the unevenness then you can rotate as necessary

void Tree::rotateLeftOnce(TreeNode*& node){
     TreeNode *otherNode;

     otherNode = node->left;
     node->left = otherNode->right;
     otherNode->right = node;
     node = otherNode;
}


void Tree::rotateLeftTwice(TreeNode*& node){
     rotateRightOnce(node->left);
     rotateLeftOnce(node);
}


void Tree::rotateRightOnce(TreeNode*& node){
     TreeNode *otherNode;

     otherNode = node->right;
     node->right = otherNode->left;
     otherNode->left = node;
     node = otherNode;
}


void Tree::rotateRightTwice(TreeNode*& node){
     rotateLeftOnce(node->right);
     rotateRightOnce(node);
}

Now that we know how to rotate, lets say you want to insert a value in the tree... First we check whether the tree is empty or not

TreeNode* Tree::insert(int d){
     if(isEmpty()){
         return (root = new TreeNode(d));  //Is empty when root = null
     }
     else
         return insert(root, d);           //step-into the tree and place "d"
}

When the tree is not empty we use recursion to traverse the tree and get to where is needed

TreeNode* Tree::insert(TreeNode*& node, int d_IN){
     if(node == NULL)  // (1) If we are at the end of the tree place the value
         node = new TreeNode(d_IN);
     else if(d_IN < node->d_stored){  //(2) otherwise go left if smaller
         insert(node->left, d_IN);    
         if(Height(node->left) - Height(node->right) == 2){
            if(d_IN < node->left->d_stored)
                rotateLeftOnce(node);
            else
                rotateLeftTwice(node);
         }
     }
     else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger
        insert(node->right, d_IN);
        if(Height(node->right) - Height(node->left) == 2){
            if(d_IN > node->right->d_stored)
                rotateRightOnce(node);
            else
                rotateRightTwice(node);
        }
     }
     return node;
}

You should always check for balance (and do rotations if necessary) when modifying the tree, no point waiting until the end when the tree is a mess to balance it. That just complicates things...

UPDATE

There is a mistake in your implementation, in the code below you are not checking correctly whether the tree is unbalanced. You need to check whether the height is equals to 2 (therefore unbalance). As a result the code bellow...

if (height(current->lchild) - height(current->rchild)) { ...

if (height(current->rchild) - height(current->lchild)) {...

Should become...

if (height(current->lchild) - height(current->rchild) == 2) { ...

if (height(current->rchild) - height(current->lchild) == 2) {...

Some Resources

Best Answer

Related Solutions

The best way to calculate the height in a binary search tree? (balancing an AVL-tree)

Part 1 - height

Part 2 - balancing

C++ – balancing an AVL tree (C++)

Related Topic