Data Structures
Balanced BST (AVL / Red-Black)
Difficulty: Advanced
Insert the keys 1, 2, 3, 4, 5 into a plain BST in that order and you do not get a tree at all; you get a right-leaning chain with O(n) search. The fix is to detect imbalance after every insert or delete and rotate the offending subtree...
Balanced BST (AVL / Red-Black)
Insert the keys 1, 2, 3, 4, 5 into a plain BST in that order and you do not get a tree at all; you get a right-leaning chain with O(n) search. The fix is to detect imbalance after every insert or delete and rotate the offending subtree back into shape, which is exactly what a Balanced BST does. AVL and Red-Black trees are the two most influential designs in this family.
This lesson covers the balance factor (height of left subtree minus height of right subtree), AVL's strict |bf| <= 1 invariant enforced by the four rotation cases (LL, RR, LR, RL), and Red-Black trees' five color and structural invariants enforced by recoloring plus rotations. You will trace insertions through both schemes, see why Red-Black trees do fewer rotations on average and so are preferred by C++ std::map and Java TreeMap, and analyze the height bound (<= 2 log n) that gives both their worst-case O(log n) guarantee.
In Binary Search Tree (BST), you implemented search, insert, and delete that respected the ordering invariant but said nothing about shape; the resulting O(n) worst case is precisely what self-balancing solves by maintaining a height invariant in addition to the ordering invariant.
Next, B-Trees and B+ Trees generalize the same balanced-tree idea to nodes that hold many keys at once, an essential design choice for disk-resident data.
Prerequisites:
Binary Search Tree (BST)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain why an unbalanced BST degenerates to O(n) and how balanced BSTs guarantee O(log n) height.
Define balance factor and implement AVL insertion with all four rotation cases (LL, RR, LR, RL).
Trace AVL rotations on paper given a sequence of insertions.
State the five Red-Black tree properties and explain why they guarantee O(log n) height.
Compare AVL vs Red-Black tree trade-offs and identify which is better for read-heavy vs write-heavy workloads.
Identify real-world applications of balanced BSTs including std::map, TreeMap, and database indices.
Why This Matters
01
An unbalanced BST degenerates into a linked list with O(n) operations -- balanced BSTs solve this by guaranteeing O(log n) worst-case height, which is why every production-grade ordered container uses one.
02
AVL and Red-Black trees are top-tier interview topics at companies like Google, Amazon, and Meta. You are expected to explain rotations, coloring rules, and trade-offs even if not asked to implement from scratch.
03
Understanding balanced BSTs is a prerequisite for advanced structures like B-Trees (databases), splay trees (caches), and treaps (competitive programming).
04
The rotation patterns you learn here (left, right, left-right, right-left) appear in many self-balancing structures, making this one of the highest-leverage topics in all of data structures.
Key Terms
7 terms you'll encounter in this lesson
Balance Factor
For a node in a BST, the balance factor is height(left subtree) - height(right subtree). In an AVL tree, every node must have a balance factor of -1, 0, or +1.
AVL Tree
A self-balancing BST named after Adelson-Velsky and Landis. It maintains |balance factor| <= 1 at every node by performing rotations after insertions and deletions.
Red-Black Tree
A self-balancing BST that uses node coloring (red or black) and five invariants to ensure the tree height never exceeds 2 log(n+1), guaranteeing O(log n) operations.
Rotation (Left/Right)
A local tree restructuring operation that changes parent-child relationships while preserving BST ordering. Left rotation lifts the right child up; right rotation lifts the left child up.
Degenerate BST
A BST where every node has at most one child, forming a linked-list shape. This happens when keys are inserted in sorted order, causing all operations to become O(n).
Black-Height
The number of black nodes on any path from a node to a null leaf (not counting the node itself). In a valid Red-Black tree, all such paths from any node have equal black-height.
Double Rotation
A sequence of two single rotations (left-right or right-left) used to fix a zig-zag imbalance in an AVL tree. Also called LR or RL rotation.
Heads Up
Common misconceptions to watch out for
"A balanced BST must have all leaves at the same level"
That describes a perfect binary tree. A balanced BST only requires that the height difference between left and right subtrees is bounded (|BF| <= 1 for AVL). Leaves can be at different levels.
"AVL trees are always better than Red-Black trees because they are more strictly balanced"
Stricter balance means faster lookups, but AVL trees perform more rotations during inserts/deletes. Red-Black trees are preferred for write-heavy workloads because they guarantee at most 2 rotations per insert and 3 per delete.
"Red-Black trees have exactly O(log n) height like AVL trees"
AVL trees have height at most ~1.44 log n. Red-Black trees allow height up to 2 log(n+1), which is still O(log n) but with a larger constant. This is the price for fewer rotations.
"You need to implement rotations from scratch in interviews"
Most interviews test your understanding of when and why rotations happen, not a from-scratch implementation. Being able to trace rotations on a whiteboard and explain the four cases is usually sufficient.