Rotations after inserting element in AVL-tree

660 Views Asked by At

We want to insert $58$ at the following AVL-tree and then we have to make rotations so that the tree is balanced. According to my notes, we are at the case RL (The first edge leads to the right and the second to the left), where two rotations are required, one right around the next of the critical node and a left one, around the critical node.

enter image description here

But why are we at the case RL, although the first edge from the critical point to the new-inserted element is a left one and the second a right one?

1

There are 1 best solutions below

7
On

You should take a look at the diagrams on Wikipedia which show you how the heights of the subtrees involved change, which will then tell you why you need to use the rotations for the RL case. If you use only one rotation, that middle subtree will stay at the same height and it will remain unbalanced. Don't simply memorize which case it is supposed to be based on some obscure rules like the one you mention. It is easy if you understand what the rotations really do. Also, you don't have to do rotations, but can simply take the subtrees and nodes and rearrange them so that their order is preserved. That way is in fact more intuitive than trying to imagine rotations of some sort.