The Story Behind Red-Black Trees
Now imagine a supervisor who paints each seat either Red or Black and enforces a strict rule: "No path from entrance to any empty seat may have more than twice as many steps as any other path." This forces the cinema to stay balanced — and that supervisor's rulebook is the Red-Black Tree.
A Red-Black Tree is a self-balancing Binary Search Tree where every node
carries a colour bit — red or black — and four invariants (rules) ensure the tree height
stays at most 2 log₂(n+1). This guarantees O(log n)
for search, insert, and delete — always, even in pathological insertion orders.
The C++ STL std::map and std::set, Java's
TreeMap and TreeSet, Python's
SortedDict (via sortedcontainers),
Linux kernel's completely fair scheduler (CFS), and the epoll
event system all rely on Red-Black Trees internally.
The Five Red-Black Properties
A valid Red-Black Tree must satisfy all five of these properties simultaneously. Violating even one means the tree is broken and may degrade to O(n).
P5 alone ensures every root-to-leaf path has the same black-node count bh. P4 means between any two black nodes there can be at most one red node. So the longest path is at most 2·bh and the shortest is bh. This bounds tree height at 2·log₂(n+1) — a 2× constant, never worse.
Anatomy of a Valid Red-Black Tree
The diagram below shows a valid RBT with black-height = 2 on every path. Hover nodes to inspect their properties.
The black-height of a node is the number of black nodes on any path from that node down to a NIL leaf (not counting the node itself). P5 says all paths from the same node must have the same black-height. A tree with black-height bh has at least 2bh − 1 internal nodes.
Rotations — The Building Block
Before understanding insertion/deletion, you must understand rotations. They are local pointer rearrangements — O(1) — that change tree structure without violating BST ordering. There are two: Left-Rotate and Right-Rotate.
def left_rotate(T, x):
y = x.right # y is x's right child
x.right = y.left # β becomes x's right
if y.left != T.nil: y.left.parent = x
y.parent = x.parent # link y to x's parent
if x.parent == T.nil: T.root = y
elif x == x.parent.left: x.parent.left = y
else: x.parent.right = y
y.left = x # x becomes y's left
x.parent = yInsertion — Step-by-Step with Fix-Up Animation
Insertion follows normal BST insertion, then colours the new node Red, then calls RB-Insert-Fixup to restore Properties P2 and P4 if violated. There are three fixup cases based on the uncle's colour.
Python Implementation — Full Red-Black Tree
A complete RBT with insert(), search(),
inorder(), and all three fix-up cases. Deletion is shown in Section 08.
Uses a sentinel NIL node to simplify boundary conditions — the standard CLRS approach.
# ── Red-Black Tree Node ─────────────────────────────────────
class RBNode:
def __init__(self, key):
self.key = key
self.color = "RED" # new nodes always start RED
self.left = None
self.right = None
self.parent = None
# ── Red-Black Tree ───────────────────────────────────────────
class RedBlackTree:
def __init__(self):
self.NIL = RBNode(0) # sentinel: BLACK, shared leaf
self.NIL.color = "BLACK"
self.root = self.NIL
# ── Rotations (O(1)) ─────────────────────────────────────
def _left_rotate(self, x):
y = x.right
x.right = y.left
if y.left != self.NIL:
y.left.parent = x
y.parent = x.parent
if x.parent == self.NIL: self.root = y
elif x == x.parent.left: x.parent.left = y
else: x.parent.right = y
y.left = x
x.parent = y
def _right_rotate(self, y):
x = y.left
y.left = x.right
if x.right != self.NIL:
x.right.parent = y
x.parent = y.parent
if y.parent == self.NIL: self.root = x
elif y == y.parent.right: y.parent.right = x
else: y.parent.left = x
x.right = y
y.parent = x
# ── Insert public API ────────────────────────────────────
def insert(self, key):
z = RBNode(key)
z.left = self.NIL
z.right = self.NIL
z.parent = self.NIL
y = self.NIL
x = self.root
while x != self.NIL: # standard BST walk
y = x
x = x.left if z.key < x.key else x.right
z.parent = y
if y == self.NIL: self.root = z
elif z.key < y.key: y.left = z
else: y.right = z
self._insert_fixup(z)
# ── Insert Fix-Up (Cases 1-3, mirrored for left/right) ──
def _insert_fixup(self, z):
while z.parent.color == "RED": # P4 violated
if z.parent == z.parent.parent.left:
uncle = z.parent.parent.right
if uncle.color == "RED": # Case 1
z.parent.color = "BLACK"
uncle.color = "BLACK"
z.parent.parent.color = "RED"
z = z.parent.parent
else:
if z == z.parent.right: # Case 2
z = z.parent
self._left_rotate(z)
z.parent.color = "BLACK" # Case 3
z.parent.parent.color = "RED"
self._right_rotate(z.parent.parent)
else: # mirror: parent is right child
uncle = z.parent.parent.left
if uncle.color == "RED":
z.parent.color = "BLACK"
uncle.color = "BLACK"
z.parent.parent.color = "RED"
z = z.parent.parent
else:
if z == z.parent.left:
z = z.parent
self._right_rotate(z)
z.parent.color = "BLACK"
z.parent.parent.color = "RED"
self._left_rotate(z.parent.parent)
self.root.color = "BLACK" # P2: root always black
# ── Search O(log n) ──────────────────────────────────────
def search(self, key, node=None):
if node is None: node = self.root
if node == self.NIL or node.key == key:
return node
return self.search(key, node.left) if key < node.key \
else self.search(key, node.right)
# ── In-order traversal → sorted output ─────────────────
def inorder(self, node=None):
if node is None: node = self.root
result = []
stack, cur = [], node
while cur != self.NIL or stack:
while cur != self.NIL:
stack.append(cur); cur = cur.left
cur = stack.pop()
result.append((cur.key, cur.color[0])) # (key, 'R'/'B')
cur = cur.right
return result
# ── Demo ─────────────────────────────────────────────────────
if __name__ == "__main__":
rbt = RedBlackTree()
for k in [7, 3, 18, 10, 22, 8, 11, 26]:
rbt.insert(k)
print("In-order (sorted):")
for key, col in rbt.inorder():
print(f" {key:3d} [{col}]")
found = rbt.search(10)
print(f"\nSearch 10: found={found.key != 0}, color={found.color}")
miss = rbt.search(99)
print(f"Search 99: found={miss != rbt.NIL}")In-order output is sorted — BST property preserved. Colours alternate red/black in a valid pattern. The root (not shown but always 10 after these insertions) is Black. No two consecutive red nodes appear in any path. Black-height is uniform at 2.
Deletion — The Harder Operation
Deletion is more complex: removing a Black node reduces the black-height on that path. The fix-up loop handles 4 cases, with symmetry between left and right. The key concept is a "double-black" phantom colour to track the deficit.
# ── Delete (adds to RedBlackTree class) ─────────────────────
def delete(self, key):
z = self.search(key)
if z == self.NIL: return # key not found
y, y_orig_color = z, z.color
if z.left == self.NIL: x = z.right; self._transplant(z, z.right)
elif z.right == self.NIL: x = z.left; self._transplant(z, z.left)
else:
y = self._minimum(z.right) # in-order successor
y_orig_color = y.color
x = y.right
if y.parent == z: x.parent = y
else:
self._transplant(y, y.right)
y.right = z.right; y.right.parent = y
self._transplant(z, y)
y.left = z.left; y.left.parent = y
y.color = z.color
if y_orig_color == "BLACK":
self._delete_fixup(x) # only needed if black node removed
def _transplant(self, u, v):
if u.parent == self.NIL: self.root = v
elif u == u.parent.left: u.parent.left = v
else: u.parent.right = v
v.parent = u.parent
def _minimum(self, node):
while node.left != self.NIL: node = node.left
return nodeTime & Space Complexity
| Operation | Average | Worst Case | Notes | Guaranteed? |
|---|---|---|---|---|
| Search | O(log n) | O(log n) | Height ≤ 2·log₂(n+1) | ✓ Always |
| Insert | O(log n) | O(log n) | ≤ 2 rotations per insert | ✓ Always |
| Delete | O(log n) | O(log n) | ≤ 3 rotations per delete | ✓ Always |
| Min / Max | O(log n) | O(log n) | Leftmost / rightmost node | ✓ Always |
| In-order traversal | O(n) | O(n) | Visits every node once | ✓ Always |
| BST search (unbalanced) | O(log n) | O(n) | Degrades on sorted input | ✗ Not guaranteed |
| AVL search | O(log n) | O(log n) | Stricter balance (height diff ≤1) | ✓ Faster lookup |
| AVL insert | O(log n) | O(log n) | Up to O(log n) rotations | ⚠ More rotations |
| Space (per node) | O(n) + 1 bit | O(n) | 1 extra colour bit vs plain BST | ✓ Minimal overhead |
AVL trees are more strictly balanced (height ≤ 1.44·log n vs RBT's 2·log n), so they offer faster lookups. But RBTs do fewer rotations on insert/delete (max 2 vs O(log n) for AVL). Prefer RBT for write-heavy workloads (databases, schedulers). Prefer AVL for read-heavy, static data.
Real-World Use Cases
TreeMap is a textbook RBT implementation. It provides
floorKey(), ceilingKey(), subMap()
— all in O(log n) — used in interval scheduling, event queues, and range queries.
epoll uses an RBT to manage file descriptor sets.
Adding/removing socket FDs during high-throughput networking (10K+ connections)
stays O(log n) regardless of connection count.
std::map and
std::set with Red-Black Trees, providing deterministic O(log n)
for all ordered-map operations.
Live Insertion Sequence — Watch the Tree Balance Itself
Insert keys 1 through 7 in order — the worst case for a plain BST (degrades to a linked list). Watch the RBT keep itself balanced through rotations and recolouring.
RBT vs Alternatives — Quick Comparison
| Property | Plain BST | AVL Tree | Red-Black Tree | B-Tree |
|---|---|---|---|---|
| Worst-case search | O(n) | O(log n) | O(log n) | O(log n) |
| Insert rotations max | 0 | O(log n) | 2 | O(log n) splits |
| Delete rotations max | 0 | O(log n) | 3 | O(log n) merges |
| Balance strictness | None | Strict (Δh ≤ 1) | Relaxed (2× log n) | Disk-optimal pages |
| Implementation complexity | Simple | Moderate | Moderate | Complex |
| Best use case | Sorted input known-small | Read-heavy lookups | Balanced read/write | Disk/DB storage |
| Used in | Teaching | AVL databases, gaming | Linux, Java, C++ STL | MySQL, SQLite, NTFS |
The Full Insertion Pipeline
Golden Rules — Red-Black Trees
y_original_color == BLACK do you call delete_fixup.
This is the most commonly misunderstood point in RBT deletion.
You understand the 5 properties, both rotations, all 3 insertion fix-up cases, the 4 deletion fix-up cases, and the time complexity guarantees. The pattern to remember: insert RED → at most 2 rotations → O(log n) always. Every balanced BST in every production system you use is built on these exact ideas.