Left-Right Double Rotation
What you'll learn: How to fix a Left-Right imbalance in an AVL tree by combining two rotations.
The Problem
Sometimes a simple single rotation isn't enough. Imagine your tree is left-heavy (left subtree is taller), but the extra height comes from the right child of the left subtree. This is the Left-Right case — the imbalance "zigzags" down.
A single right rotation won't fix this because the problem node isn't in a straight line from the root.
The Solution: Two-Step Fix
The Left-Right Double Rotation performs:
- Left rotation on the left child (straightening the zigzag into a straight left-left line)
- Right rotation on the original imbalanced node (fixing the now-straightened imbalance)
Analogy: Think of straightening a bent paperclip. You can't fix a zigzag bend with one twist — you first unbend the middle section, then straighten the whole thing.
When to Use It
You detect this pattern when:
- The balance factor at a node is +2 (left-heavy)
- The balance factor of its left child is -1 (right-heavy)
The child's right-heaviness creates the zigzag that requires two rotations.
Why It Works
The first rotation (left on the left child) converts the Left-Right case into a Left-Left case. Now the tree has a straight left spine. The second rotation (right on the root) then resolves this straightforward imbalance, restoring balance to the entire subtree.
Key Takeaway: The Left-Right Double Rotation fixes zigzag imbalances by first rotating left to straighten the path, then rotating right to restore balance — always apply rotations in sequence to handle complex imbalance patterns.