AVL Tree Balance

Question

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

Suppose I have the following tree:

And after adding another node:

Now I have to turn node 5 to the left:

But after rotation it is still unbalanced.

Where am I making a mistake?

Answer 1

The presented scenario corresponds to the case of Right-Left from this description.

Your mistake is that you rotate the unbalanced node ( 5 ) right away, without first rotating your subtree.

In the general case, P as an unbalanced node, L as its left sub-tree and R as its right subtree, the following rules should be observed when inserting:

 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 you need to perform two turns , and sometimes only one.

This is beautifully visualized on Wikipedia :

The top line shows situations when two rotations are needed. The middle row represents possible scenarios when one turn is enough. Extra spins convert any top-line script to a middle-line script.

In particular, for this tree:

After adding 7 :

Balance 5 is 2 . This corresponds to the scenario noted by the comment above in the pseudo-code, as well as the scenario with the top line (on the right) in the Wikipedia image. Therefore, before 5 is rotated to the left, its right subtree 11 must be rotated to the right:

And it will be:

Only now is this a simple case (a script with a middle line in the Wikipedia image) to restore balance with 5 one rotation to the left:

And the tree is balanced again:

Answer 2

Let me try to analyze more comprehensively, For a binary tree that is an avl tree, the height difference of each node from any leaf on the left to any rightmost leaf should be within {-1, 0, 1}.

Insert for AVL:

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

Now, case (a). [if balances> 1] LL (left – left) A node X violates the {-1, 0, 1} constraint and leaves the height greater than the right - gives the first to the left of L has a left child south Y whose left height is greater than the right. again L Action. Rotate around Y clockwise. i.e. one right turn.

case (b) (case LR) Suppose that some Z node must be inserted, for Z it is first evaluated at which the sheet, left or right, is placed. Right if more weight, if less weight. let's say Z ', the new node, wt (Z')> wt (Z), i.e. Z 'is inserted as the right child from Z, case L is R, the whole link ZZ' is rotated counterclockwise, now this is case LL and, therefore, is solved using the above case (a). i.e. one left and one right turn.

(c) [if balance <-1] (case R - R) Similarly, case R - R, just apply the binary search rule for the settings, and this case works. i.e. one left turn.

case (d) (case R - L) It is first converted to the case RR and, therefore, is solved using the above case (c). i.e. one right and then one left.