A tree rotation rearranges a small group of nodes so an unbalanced binary search tree becomes more balanced. The nodes keep their ordering, while parent-child relationships change. section 8.5 section 8.4
A simple left rotation
Imagine three connected nodes, A, B, and another child. Starting with A as the root, rotate left so B becomes the root. Adding nodes can make an AVL tree unbalanced; rotating the appropriate subtree restores balance. In one walkthrough, nodes 20 and 30 are rotated at different points as the tree grows. section 8.5
In an AVL tree, rotation fits into a larger balancing process:
- Insert the new node and update the affected node’s height and balance factor. section 8.6
- Move upward through the tree, updating ancestors until the imbalance is corrected. section 8.6
- Rotate the required subtree; AVL trees generally need at most one rebalancing during this upward pass. section 8.6
