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:

Answer 2

Let me try to analyse more comprehensively, For a binary tree to be avl tree, the height difference of each node from any left-most leaf to any right-most leaf must lie within {-1, 0, 1}.

Insertion for AVL:

There are four cases for AVL insertion- L - L L - R R - R R - L

Now, case (a). [if balance > 1] L-L(left - left) A node X violates the {-1, 0, 1} constraint and has left height more than right - gives first left of L has a left sub child Y whose left height is greater than right .. again L Action - Rotate about Y clockwise. ie. one right rotation.

case (b) (L -R case)Suppose some Z node is to be inserted, for Z, it is first evaluated, at which leaf, left or right, it is placed. Right, if more weight, Left if less weight. say, Z', new node, wt(Z') > wt(Z), ie, Z' is inserted as right child of Z, case of L - R, the whole link ZZ' is rotated anti clockwise, now it is L-L case and hence solved using above case (a). ie. one Left and then one right rotation.

case (c) [if balance < -1] (R - R case) Similarly, R - R case, simply apply the binary search rule for adjustments and this case works. ie. one left rotation.

case (d) (R - L case) It is first converted to R-R case and hence solved using above case (c). ie. one right and then one left rotation.