4.2. General Insertion Algorithm

  1. Do a normal BST insert

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

  3. 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.

  4. 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.