Identifying Imbalance Cases
What you'll learn: You'll learn to recognize the four distinct patterns of imbalance that can occur in AVL trees, which is essential for knowing how to fix them.
The Four Imbalance Patterns
When an AVL tree becomes imbalanced (balance factor > 1 or < -1), the imbalance always falls into one of four specific patterns. These patterns are named based on the path from the imbalanced node down to the problem area:
Left-Left (LL)
The imbalance is in the left subtree of the left child. Imagine a tree leaning heavily to the left, and the weight is all on the outer left side.
Left-Right (LR)
The imbalance is in the right subtree of the left child. The tree leans left overall, but the problem is on the inner right side of that left subtree—like a zigzag pattern.
Right-Right (RR)
The imbalance is in the right subtree of the right child. This mirrors LL—the tree leans right, with weight on the outer right side.
Right-Left (RL)
The imbalance is in the left subtree of the right child. This mirrors LR—the tree leans right, but the problem is on the inner left side, creating a zigzag.
How to Identify the Case
When you detect an imbalance at a node (balance factor of +2 or -2), look at its taller child's balance factor:
- Balance factor -2, left child has balance ≤ 0: Left-Left
- Balance factor -2, left child has balance > 0: Left-Right
- Balance factor +2, right child has balance ≥ 0: Right-Right
- Balance factor +2, right child has balance < 0: Right-Left
Think of it like diagnosing which way a tree is "falling over"—you need to know the exact pattern to apply the correct fix.
Key Takeaway: The four imbalance cases (LL, LR, RR, RL) describe where the excess height occurs relative to the imbalanced node, and identifying the correct case is the first step in rebalancing an AVL tree.