Right-Left Double Rotation
What you'll learn: How to fix a Right-Left imbalance in an AVL tree by performing a right rotation followed by a left rotation.
The Problem
When you insert a node into an AVL tree, you might create a Right-Left imbalance: the tree leans too far right (right child is taller), but within that right subtree, the problem is on the left side. This creates a "zig-zag" shape that a single rotation can't fix.
The Solution
The Right-Left double rotation straightens out this zig-zag in two steps:
- Right rotation on the right child – This converts the zig-zag into a straight line (all leaning right)
- Left rotation on the root – This balances the entire subtree
Think of it like untangling a kinked chain: first you straighten the kink locally, then you can easily fix the whole thing.
When to Apply
You detect this case when:
- The root node has a balance factor of -2 (right-heavy)
- The right child has a balance factor of +1 (left-heavy within the right subtree)
Visual Intuition
A (balance: -2) A C
\ \ / \
C (balance: +1) → B → A C
/ \
B C
The middle node B ends up as the new root of the balanced subtree after both rotations complete.
Why Two Rotations?
A single left rotation on A would make C the root, but B would still dangle incorrectly. The right rotation on C first moves B into position where the subsequent left rotation can properly balance everything.
Key Takeaway: The Right-Left double rotation fixes zig-zag imbalances by first rotating right on the problem child, then rotating left on the original root, restoring AVL balance.