Single Right Rotation
What you'll learn: You'll discover how to fix a Left-Left imbalance in an AVL tree using a single right rotation that restores balance while preserving the BST property.
The Problem
When you insert a node into an AVL tree, you might create a Left-Left case: a node becomes unbalanced (balance factor = +2) because its left child's left subtree is too tall. Picture a tree leaning heavily to the left like the Leaning Tower of Pisa.
The Solution: Right Rotation
A right rotation is like grabbing the left child and promoting it upward, making the original parent "rotate" down to become the right child. Think of it as straightening a bent elbow by pivoting at the joint.
Here's what happens step-by-step:
- Identify the unbalanced node (let's call it
z) - Its left child (call it
y) becomes the new root of this subtree zbecomesy's right childy's right subtree (if any) becomesz's new left subtree
Why It Works
The rotation maintains the BST property because:
- Everything in
y's left subtree stays smaller thany - Everything in
y's original right subtree fits betweenyandz - Everything in
z's right subtree stays larger thanz
The heights change: z drops one level, y rises one level, and balance is restored. The balance factors after rotation become 0 for both nodes in the typical case.
The Analogy
Imagine three people standing in a line: small, medium, tall. They're leaning left. You pivot around the middle person, moving them to the center position—now everyone stands balanced!
Key Takeaway: A single right rotation fixes Left-Left imbalances by promoting the left child upward while preserving BST order—it's a local restructuring that costs O(1) time.