Preserving search property while restructuring the tree
A rotation is a local restructuring that changes tree shape without violating the binary search tree property. In a left rotation, a node slides down to become the left child of its right child, which slides up. In a right rotation, the process reverses. The in-order traversal (left, node, right) remains unchanged because relative key ordering is preserved.
Rotations are O(1) operations if tree pointers are maintained: update parent pointers, relink children. This makes them the building block for self-balancing trees. Without rotations, rebalancing an unbalanced tree would require wholesale reconstruction.
Single and double rotation patterns
A left-left imbalance (right-heavy right subtree) is fixed by one left rotation. A right-right imbalance requires one right rotation. Left-right and right-left imbalances (heavier nodes in opposite directions) require two rotations: first a compensating rotation to convert to a single-rotation case, then the main rotation.
AVL and Red-Black trees use these patterns automatically on insert and delete to maintain balance. The rotation logic is deterministic and local: examine balance factors or color properties of a small region, apply the appropriate rotation(s), and the tree is rebalanced. This is why AVL trees guarantee O(log n) height and why Red-Black trees avoid quadratic degeneration.