Insert with Rebalance

Insertion follows the search path as in a BST, attaching the node as a leaf and moving back up. At each ancestor, the balance factor is checked and rotations are performed if necessary.

Task: calculate the height of a node from the heights of its children.

Where used

Online indices: every mutation must repair the invariant. The same thought pattern applies to other self-organizing structures.

Depth

First, a leaf is inserted according to the normal search tree rule. Then the repair process runs backwards along the search path, updating heights and checking the local balance condition.

The case arises from the direction towards the heavy child and the direction within that child. If both directions are the same, a single rotation is sufficient; otherwise, a double rotation is performed.

After the rotation, the repaired subtree must be correctly reinserted into its parent context. In recursive implementations, it is therefore helpful to return the possibly new subtree root from each method.

Difficulty levels

1. Determine the search path and the new leaf position.
2. Derive the rotation case from two directional decisions.
3. Design a recursive method that returns the subtree root.

Pitfalls

Those who calculate heights before the structural change use outdated values. Equality keys also require a fixed rule; otherwise, the search invariant can become ambiguous.