Balance procedure of AVL Tree

Question

As per my understanding of AVL tree, for every node, heights of left and right subtrees should differ by at most 1.

Here is the code, I came up with to balance the height while inserting a new node. The following method will be executed repeatedly starting from the new node propagating upwards till root

private Node balance(Node x) {
    if (Math.abs(height(x.left) - height(x.right)) <= 1) {
        return x;
    }
    // left sub tree is heavier than right sub tree
    if (height(x.left) > height(x.right)) {
        // right sub tree of left sub tree is heavier than left sub tree of left sub tree
        if (height(x.left.left) < height(x.left.right)) {
            leftRotate(x.left);
        }
        return rightRotate(x);
    }
    // right sub tree is heavier than left sub tree
    else {
        // left sub tree of right sub tree is heavier than right sub tree of right sub tree
        if (height(x.right.left) > height(x.right.right)) {
            rightRotate(x.right);
        }
        return leftRotate(x);
    }
}

When I looked at MIT solutions (Page 5) ,it seems that they are performing left rotate and then right rotate if node is inserted in the left sub tree of left sub tree of unbalanced node:

As per my understanding, if we insert a node in left sub tree of left sub tree of unbalanced node, we should me right rotation only, not left rotation and subsequent right rotation.

What am I missing here? Did I implemented it correctly?

trincot trincot · Accepted Answer · 2018-11-03T15:27:18

You indeed found a mistake in the referenced document on page 5.

The pictures on page 4 are correct, but the implementation on page 5 is wrong, probably a typo.

Logically lines lines 4-7 should mirror lines 8-11 in terms of left and right. With that in mind it is apparent there is a mistake there.

Line 5 should have left and right swapped -- or else use < instead of > which comes down to the same thing --, like this:

5 if height(left[y]) < height(right[y])

Your implementation is correct in that respect.

Balance procedure of AVL Tree

1 Answers