CODEWITHSUNDEEP
data-structurestreerotationbinary-search-treeavl-tree
user1910524
user1910524

Reputation: 113

Balancing AVL Trees

I am having trouble balancing AVL Trees. I have searched high and low for steps to how to balance them and I just can't get anything useful.

I know there are 4 kinds:

But I just can't get how to choose which one of them and which node to apply it on!

Any help would be greatly appreciated!

Upvotes: 4

Views: 4140

Answers (2)

gtboy
gtboy

Reputation: 128

This is the java implementation and you will get the idea of the algorithm there:

private Node<T> rotate(Node<T> n) {
    if(n.getBf() < -1){
            if(n.getRight().getBf() <= 0){
                return left(n);         
            }
            if(n.getRight().getBf() > 0){
                return rightLeft(n);
            }
    }   
    if(n.getBf() > 1){
            if(n.getLeft().getBf() >= 0){
                return right(n);
            }
            if(n.getLeft().getBf() <  0){
                return leftRight(n);
            }
    }
    return n;
}

The separate methods for 4 rotations are here:

/**
 * Performs a left rotation on a node
 * 
 * @param n The node to have the left rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> left(Node<T> n) {
    if(n != null){
        Node<T> temp = n.getRight();
        n.setRight(temp.getLeft());
        temp.setLeft(n);
        return temp;
    }
    return n;   
}

/**
 * Performs a right rotation on a node
 * 
 * @param n The node to have the right rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> right(Node<T> n) {
    if(n != null){
        Node<T> temp = n.getLeft();
        n.setLeft(temp.getRight());
        temp.setRight(n);
        return temp;
    }
    return n;
}

/**
 * Performs a left right rotation on a node
 * 
 * @param n The node to have the left right rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> leftRight(Node<T> n) {
    n.setLeft(left(n.getLeft()));
    Node<T> temp = right(n);
    return temp;
}

/**
 * Performs a right left rotation on a node
 * 
 * @param n The node to have the right left rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> rightLeft(Node<T> n) {
    n.setRight(right(n.getRight()));
    Node<T> temp = left(n);
    return temp;
}

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372724

The key invariant in an AVL tree is that the balance factor of each node is either -1, 0, or +1. Here, the "balance factor" is the difference in the height between the left and right subtrees. +1 means the left subtree is one taller than the right subtree, -1 means the left subtree is one shorter than the right subtree, and 0 means the subtrees have the same size. This information is usually cached in each node.

When you get a node with a balance factor of -2 or +2, you will need to do a rotation. Here's one possible setup for when a rotation is necessary:

          u (-2)
         / \
        A   v (-1)
           / \
          B   C

If we fill in the heights of these trees, we get

          u h + 2
         / \
    h-1 A   v h + 1
           / \
      h-1 B   C h

If this happens, doing a single right rotation yields

         v h+1
        / \ 
     h u   C h
      / \
 h-1 A   B h-1

And hey! The tree is balanced. The mirror-image of this tree would also be fixable with a single left rotation.

All of the AVL tree rotations can be determined simply by enumerating the possible balance factors within a small range and then determining which rotations should be applied at each step. I'll leave this as an exercise to the reader. :-) If you just want to look up the answers, the Wikipedia article on AVL trees has a nice picture that summarizes all the rotations that might need to be applied.

Hope this helps!

Upvotes: 0

Related Questions