The pivot node is the deepest node at which there is an imbalance. The rotator node is the root of the pivot's taller subtree.
There may be more nodes above the pivot's parent. Step 3 prunes the rotator's `inside' subtree, i.e. the one on the pivot's side.
Which of the rotator's subtrees is the inside subtree, which is the outside? It depends on whether the rotator is the left or right child of the pivot. If the rotator is the right child (as in this picture), the inside subtree is its left subtree and the outside subtree is its right subtree. On the other hand, if the rotator is the left child the inside subtree is its right subtree and the outside subtree is its left subtree.
Step 4: Join the pruned inside subtree to the pivot (in the place where the rotator had been).
Step 5: Join the pivot to the rotator (in the place where inside had been).
Step 6: Join the rotator to the pivot's (original) parent (in the place where the pivot had been).
Following these steps, the result of the rotation is this: the rotator has rotated up, the pivot has rotated down on the other side, and the inside subtree has jumped across to join the pivot:
Example:
After steps 1-3, the tree is the same but the parts that will be re-arranged have been pruned from the main tree and from one another:
Step 4: Join the pruned inside subtree to the pivot:
Step 5: Join the pivot to the rotator (in the place where inside had been):
Step 6: Join the rotator to the pivot's (original) parent:
The result of the rotation in this example is: `1' rotates up, `5' rotates down on the other side, and `2' jumps across to join `5'.
Returning to the INSERTION operation, recall our strategy:
In the examples we've seen so far, all we needed was one rotation to re-balance the whole tree. Sometimes this doesn't work... Suppose I insert 3 into the following tree:
First add 3 as 1's right subtree:
But this is unbalanced at `5'. With a single rotation: 1 goes up, 5 goes down, 3 jumps across, and we get:
Which is just as bad as what we started with! What has gone wrong?
Let's look closely at how a rotation changes the level of two subtrees - the inside and outside subtrees in the general algorithm (in our example `3' is the inside subtree, outside is empty). A rotation causes inside to jump across to the other side - but it stays at the same level. Outside stays on the same side, but it goes up one level.
If there is a height-imbalance and outside is taller than inside then a rotation will correct the imbalance. But if inside is taller than outside, the rotation will not fix the imbalance, it will just move it to the other side!
So, before doing the rotation we need to do something to ensure that the outside subtree is taller than the inside one. What can we do?
Answer: If inside is taller then rotate its root to the outside!
Going back to our example, `1' is the rotator, `3' is the inside subtree. It is taller than the outside subtree (which is empty), so we rotate `3' up, and `1' down (to the outside) etc. giving:
And now we do the main rotation (3 up, 5 down):
