Self-Balancing Trees: AVL Rotations and Red-Black Rebalancing Invariants
Analyze the mathematics of self-balancing binary search trees: AVL height-balance factors, single and double rotations, and Red-Black coloring invariants.
By the end, you’ll be able to…
- Calculate AVL balance factors and perform Left, Right, Left-Right, and Right-Left rotations
- Compare AVL strict height balance (|BF| <= 1) with Red-Black tree relaxed color invariants
- Explain why standard library collections (java.util.TreeMap, C++ std::map) favor Red-Black trees over AVL
01The Degeneracy Problem in Unbalanced BSTs
A standard Binary Search Tree provides O(log n) search, insertion, and deletion on average. However, if keys are inserted in sorted order (e.g., 1, 2, 3, 4, 5), the tree degrades into a linked list. Search operations degenerate from logarithmic time to linear O(n) time.
Self-balancing trees restore O(log n) worst-case performance by performing tree rotations during insertions and deletions. A tree rotation re-links child pointers to adjust tree height while strictly preserving the BST in-order sorting invariant (left < root < right).
The two premier self-balancing architectures are AVL Trees (introduced by Adelson-Velsky and Landis in 1962) and Red-Black Trees (formalized by Guibas and Sedgewick in 1978).
02AVL Trees: Strict Balance Factors and Rotations
In an AVL tree, every node maintains a balance factor: BF(node) = height(leftSubtree) - height(rightSubtree). The strict AVL invariant requires that for every node, |BF(node)| <= 1. If an insertion or deletion causes BF to become +2 or -2, a rotation is triggered immediately.
There are four rotation cases: 1. Left-Left (LL): Heavy on left child's left. Fixed by a Single Right Rotation. 2. Right-Right (RR): Heavy on right child's right. Fixed by a Single Left Rotation.
3. Left-Right (LR): Heavy on left child's right. Fixed by a Left Rotation on the left child, followed by a Right Rotation on the node itself. 4. Right-Left (RL): Heavy on right child's left. Fixed by a Right Rotation on the right child, followed by a Left Rotation on the node itself.
03Red-Black Trees: Relaxed Color Invariants
While AVL trees are strictly balanced, maintaining |BF| <= 1 requires frequent rotations during write workloads. Red-Black trees relax height constraints by coloring every node either RED or BLACK and enforcing five structural rules:
1. Every node is either red or black. 2. The root is always black. 3. Every leaf (NIL null pointer) is black. 4. If a node is red, both its children must be black (no two consecutive red nodes). 5. For each node, all simple paths from the node to descendant leaves contain the exact same number of black nodes (the black-height).
These rules guarantee that the longest path from the root to any leaf is at most twice as long as the shortest path. Thus, tree height is strictly bounded by 2 * log2(n + 1), guaranteeing O(log n) operations with significantly fewer rotations on insertion.
04Architectural Comparison: AVL vs Red-Black
Standard libraries make deliberate trade-offs when selecting between AVL and Red-Black implementations:
Java's java.util.TreeMap, java.util.TreeSet, and HashMap collision bins (Java 8+) all utilize Red-Black trees because general enterprise workloads feature mixed reads and writes where Red-Black trees outperform.
+-----------------------+-------------------------+-------------------------+| Characteristic | AVL Tree | Red-Black Tree |+-----------------------+-------------------------+-------------------------+| Height Bound | ~1.44 * log2(n) | ~2.0 * log2(n) || Lookup Speed | Faster (Stricter height)| Slightly slower || Rotations on Insert | At most 2 rotations | At most 2 rotations || Rotations on Delete | Up to O(log n) rotations| At most 3 rotations! || Standard Library Use | Read-intensive DB lookup| TreeMap, Linux CFS, STL |+-----------------------+-------------------------+-------------------------+The ideas worth keeping.
- AVL trees enforce strict height balance (|BF| <= 1) via single and double rotations.
- Red-Black trees relax height bounds to achieve faster insertions and deletions with bounded rotations.
- Standard libraries favor Red-Black trees for general-purpose maps and sets due to write efficiency.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Given an AVL node with Balance Factor 2 whos
Given an AVL node with Balance Factor +2 whose left child has Balance Factor -1, which rotation sequence must be performed?
Explore a worked solution
// This is a Left-Right (LR) imbalance case.// Fix: 1. Perform a Left Rotation on the left child.// 2. Perform a Right Rotation on the unbalanced node itself.When signs of the parent BF and child BF differ, a double rotation is required.
Exercise 2: Explain why no path in a Red Black tree can b
Explain why no path in a Red-Black tree can be more than twice as long as any other path.
Explore a worked solution
// Rule 5 requires every path to have the exact same number of black nodes (black-height B).// Rule 4 forbids consecutive red nodes, so red nodes can at most alternate with black nodes.// Therefore: Shortest possible path has B black nodes (length B).// Longest possible path alternates: Red-Black-Red-Black (length 2B).// Hence, the longest path is at most twice the length of the shortest path.Consider the shortest path (all black) versus the longest alternating path.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Given an AVL node with Balance Factor 2 whos
Given an AVL node with Balance Factor +2 whose left child has Balance Factor -1, which rotation sequence must be performed?
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.