Remove from AVL tree example code

Cratylus picture Cratylus · May 27, 2012 · Viewed 9.6k times · Source

I am looking into AVL trees and can not seem to find a reference code about removal (either by Googling or from a couple of textbooks I have handy).
I am not sure why is this, but do you know of any reference/example of deletion of AVL in java?
(I only found this:avl tree removal which it states in the link that it failed under testing)

Answer

Justin picture Justin · May 27, 2012

I have an implementation of an AVL Tree in Java which has been well tested, if you'd like to use it for reference. It is based on the wikipedia description and it is commented pretty well.

Just like when you have to balance after a regular BST insert. You remove the node like a BST and then balance according to the below algorithm.

The cases for balancing after a BST remove are (node is the parent of the node which was used to replace the removed node):

    ... remove code ...
    // Re-balance the tree all the way up the tree
    while (nodeToRefactor != null) {
        nodeToRefactor.updateHeight();
        balanceAfterDelete(nodeToRefactor);
        nodeToRefactor = (AVLNode<T>) nodeToRefactor.parent;
    }
    ... remove code ...

    ... balance code ...
    int balanceFactor = node.getBalanceFactor();
    if (balanceFactor==-2 || balanceFactor==2) {
        if (balanceFactor==-2) {
            AVLNode<T> ll = (AVLNode<T>) node.lesser.lesser;
            int lesser = ll.height;
            AVLNode<T> lr = (AVLNode<T>) node.lesser.greater;
            int greater = lr.height;
            if (lesser>=greater) {
                rightRotation(node);
            } else {
                leftRotation(node.lesser);
                rightRotation(node);
            }
        } else if (balanceFactor==2) {
            AVLNode<T> rr = (AVLNode<T>) node.greater.greater;
            int greater = rr.height;
            AVLNode<T> rl = (AVLNode<T>) node.greater.lesser;
            int lesser = rl.height;
            if (greater>=lesser) {
                leftRotation(node);
            } else {
                rightRotation(node.greater);
                leftRotation(node);
            }
        }
    }