Remove from AVL tree example code [closed]

Question

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 1

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);
            }
        }
    }

Answer 2

The algorithm isn't that bad, once you have an implementation of balance()...

The first implementation that comes to mind is the implementation of TreeList in Apache Commons Collections, which is a list backed by an AVL tree. http://www.docjar.org/html/api/org/apache/commons/collections/list/TreeList.java.html has the source code.