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

Step 5: Join the

Step 6: Join the rotator to the

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:

- Add the new value in the tree where it belongs (normal BST
insertion).
- Check if all subtrees are still height-balanced. If they are not, re-balance the tree by changing its shape.

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:

*On the blackboard, exaggerate the Left-Right sides*

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):