Lecture 9 - General Insertion Algorithm

## 4.2. General Insertion Algorithm

- Do a normal BST insert

- If the tree is balanced, you are finished. otherwise do 3-4.

- Starting at the newly inserted node, work your way up the tree
until you find the first node whose subtrees' heights differ by
2. This node is the
*pivot*, the root of its taller
subtree is the *rotator*.

- It is necessarily the case that the new value was inserted in
one of the
*rotator*'s subtrees. If it was inserted in
the *rotator*'s *outside* subtree, then this
subtree will be taller than *inside*, and a single
rotation (of the *rotator*) will correct the imbalance.
Otherwise you must first rotate the root of the rotator's inside
subtree up into the rotator's position (the rotator does down
the other side), and then rotate the node that replaced the
rotator up into the pivot's position.

**Example:**
insert 2 into this tree:

First, we obtain:

The pivot is the lowest node whose subtrees' heights differ by 2. The
rotator is the root of the pivot's taller subtree (the one in which
the new value was inserted).
The new value is in the rotator's `inside' subtree. Therefore, we
must rotate this subtree before correcting the imbalance.

**Note:**
If the rotator's inside subtree was already shorter than its outside
subtree we would just skip the `setup' step that follows and go
straight to the last step.

This rotation does not change the imbalance at all; all it does it
make the rotator's outside subtree taller than its inside one. The
pivot node does not change and the rotator is the same node as before
(different value).
When the rotator's outside subtree is taller, a single rotation of
the rotator will correct the height imbalance in the whole tree.

**Exercise:**
add 4 or 7 to this tree.