Single Left Rotation
You'll learn how to fix a Right-Right imbalance in an AVL tree by rotating nodes left while preserving BST ordering.
What's the Problem?
When you insert into the right subtree of a right child, your AVL tree becomes unbalanced with a Right-Right (RR) imbalance. The balance factor of some node becomes -2 (right-heavy), and its right child has a balance factor of -1 or 0. A single left rotation restores balance.
How It Works
Imagine three people standing in a line leaning too far right. You need to "promote" the middle person upward while keeping everyone in order.
In tree terms:
- Identify the unbalanced node (let's call it
A) with balance factor -2 - Its right child
Bwill become the new root of this subtree AbecomesB's left childB's original left subtree becomesA's new right subtree
The key insight: This rotation preserves BST ordering because:
- Everything originally less than
Astays to its left - Everything originally greater than
Bstays to its right B's left subtree (values betweenAandB) moves fromB's left toA's right—still maintaining order
Visual Pattern
A (-2) B
\ / \
B (-1) → A C
\
C
The rotation "lifts" B up and "drops" A down-left, fixing the imbalance in O(1) time.
Key Takeaway: A single left rotation fixes Right-Right imbalances by promoting the right child to the root position while carefully reassigning subtrees to maintain BST ordering—restoring the AVL height-balance property.