AVL Tree Balancing

Question

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?

Answer 1

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.

Answer 2

You might try passing the parent pointer into the insert method, or you could convert insert into an iterative method and keep an explicit stack on which you record the path down the tree.

By the way, in order to choose which rotation to use, you can just know that a node is unbalanced, you have to know whether the deeper subtree is on the right or on the left. This means that your simple isBalanced method isn't quite enough. It's also inefficient, and will blow the AVL tree's O(log n) complexity, because you compute the heights each time.