Choosing the Rotation
We now have four rotations, one for each unbalanced shape. So far we picked the rotation by looking at the shape. To write the code, we need a rule. The rule looks at two balance factors. The unbalanced node has a balance factor of when it is left-heavy and when it is right-heavy. Its heavy child is the child on that side, and the heavy child’s own balance factor says which side it is heavy on. Together, the two balance factors tell you which rotation to use:
| heavy child is left-heavy | heavy child is right-heavy | |
|---|---|---|
| node is left-heavy | single right | double left-right |
| node is right-heavy | double right-left | single left |
When the node and its heavy child are heavy on the same side, the extra height is on a straight spine, and a single rotation fixes it. When they are heavy on opposite sides, the shape bends in the middle, and you need a double rotation. A single rotation always goes in the direction opposite to the node’s heavy side: a left-heavy node is fixed by a right rotation.