AVL tree balance

Question

I have implemented an AVL tree, but I have a problem.

Suppose I have following tree:

And after adding another node:

Now I must rotate node5 to left:

But after rotation, it is still unbalanced.

Where am I making a mistake?

Answer 1

The presented scenario conforms to the Right-Left case from this Wikipedia description.

Your mistake is that you rotate the imbalanced node (5) at once, without first performing a rotation of its sub-tree.

In general having P as the unbalanced node, L as its left sub-tree and R as its right sub-tree the following rules should be followed at insertion:

balance(N) = Depth(Nleft) - Depth(Nright)

if (balance(P) > 1)  // P is node 5 in this scenario
{
    if (balance(L) < 0)
    {
        rotate_left(L);
    }

    rotate_right(P);
}
else if (balance(P) < -1) // P is node 5 in this scenario
{
    if (balance(R) > 0)  // R is node 11 in this scenario
    {
        rotate_right(R); // This case conforms to this scenario
    }

    rotate_left(P);      // ... and of course this, after the above
}

So sometimes two rotations need to be performed, and sometimes only one.

This is nicely visualized at Wikipedia:

The top row shows situations when two rotations are needed. The middle row presents possible scenarios when one rotation is sufficient. Additional rotations transform any top-row scenario to the middle-row scenario.

In particular, for this tree:

After 7 is added:

The balance of 5 is 2. This conforms to the scenario marked with a comment above in the pseudo-code and also to the top-row scenario (the one on the right) in the Wikipedia picture. So before 5 is left-rotated, its right sub-tree 11 needs to be right-rotated:

And it becomes:

Only now, it's the simple case (middle-row right scenario in the Wikipedia picture) to restore balance at 5 by one left-rotation:

And the tree becomes balanced again: