What is a Red-Black Tree?
Learn how red-black trees self-balance via coloring rules and rotations, guaranteeing O(log n) operations for interviews.
Expected Interview Answer
A red-black tree is a self-balancing binary search tree that colors each node red or black and enforces balancing rules so the longest root-to-leaf path is never more than twice the shortest, guaranteeing O(log n) search, insert, and delete.
It maintains five invariants: every node is red or black, the root is black, red nodes cannot have red children, every path from a node to its descendant leaves has the same number of black nodes, and null leaves count as black. When an insertion or deletion violates these rules, the tree fixes itself through recoloring and a bounded number of rotations rather than a full rebalance. This keeps the tree "approximately balanced" with less strict height bounds than an AVL tree, trading slightly slower lookups for cheaper insert/delete, which is why it backs many standard-library ordered maps.
- Guarantees O(log n) search, insert, and delete
- Fewer rotations on insert/delete than AVL trees
- Powers language standard libraries (e.g. C++ map, Java TreeMap)
- Predictable worst-case performance, unlike a plain unbalanced BST
AI Mentor Explanation
A cricket academy seeds players into a bracket where every branch must have a similar number of "senior" checkpoints so no player’s development path is wildly longer than another’s. When a promising junior is added and creates an imbalance — two seniors in a row on one branch — the academy reshuffles the bracket locally through a swap or two, not a full re-seed. This keeps every player’s path from the academy head to any leaf roughly the same length, so scouting any player takes about the same, logarithmic, amount of effort.
Step-by-Step Explanation
Step 1
Insert as in a BST
Insert the new node using standard binary search tree rules and color it red.
Step 2
Check for violations
If the new red node’s parent is also red, a red-red violation exists and must be fixed.
Step 3
Recolor or rotate
Depending on the uncle node’s color, either recolor ancestors or perform a rotation (single or double) to restore balance.
Step 4
Fix the root
After fixups, ensure the root is colored black, since the root-black invariant must always hold.
What Interviewer Expects
- All five red-black invariants stated correctly
- Understanding that rotations are O(1) and bounded per insert/delete
- Comparison against AVL trees (stricter balance vs. cheaper updates)
- Awareness of real-world usage in standard library ordered containers
Common Mistakes
- Forgetting that null leaves are implicitly black
- Confusing red-black trees with AVL trees’ balance guarantees
- Assuming red-black trees keep the tree perfectly height-balanced
- Not knowing that lookups are still O(log n) but slightly slower than AVL
Best Answer (HR Friendly)
“A red-black tree is a self-balancing search tree that colors nodes red or black and follows a few simple coloring rules to stay roughly balanced. That balance guarantees fast, predictable search and update times, which is why it’s used inside many programming languages’ built-in sorted data structures.”
Code Example
RED, BLACK = 'RED', 'BLACK'
class Node:
def __init__(self, key, color=RED, left=None, right=None, parent=None):
self.key = key
self.color = color
self.left = left
self.right = right
self.parent = parent
def left_rotate(tree, x):
y = x.right
x.right = y.left
if y.left is not None:
y.left.parent = x
y.parent = x.parent
if x.parent is None:
tree.root = y
elif x is x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = yFollow-up Questions
- How does a red-black tree differ from an AVL tree in balance strictness?
- What are the four red-black tree invariants that fixups must preserve?
- Why do standard libraries prefer red-black trees over AVL trees for maps?
- How many rotations, at most, are needed to fix an insertion violation?
MCQ Practice
1. Which of these is NOT a red-black tree invariant?
Leaves (null nodes) are always considered black, not red, in a red-black tree.
2. What is the worst-case time complexity for search in a red-black tree?
The balancing invariants bound the tree height at O(log n), so search is always logarithmic.
3. Compared to AVL trees, red-black trees generally offer:
Red-black trees allow looser balance than AVL trees, trading slightly slower lookups for fewer rotations on updates.
Flash Cards
What color must the root of a red-black tree always be? — Black.
Can a red node have a red child? — No — that is a red-red violation that must be fixed via recoloring or rotation.
What color are null leaf nodes considered? — Black, by convention, for invariant-counting purposes.
Name one real-world use of red-black trees. — C++ std::map and Java’s TreeMap are commonly implemented with red-black trees.