A red-black tree is a self-balancing BST where each node is colored red or black and a small set of color invariants keep the tree height ≤ 2 log(n+1). Used in C++ std::map/std::set, Java TreeMap, the Linux kernel scheduler (CFS), and the Linux epoll ready-list.
A red-black tree is a binary search tree in which every node carries one extra bit, a colour, and the colours obey rules that prevent the tree from becoming lopsided. The rules are: every node is red or black; the root is black; the NIL leaves are black; a red node never has a red child; and every path from a node down to its NIL leaves contains the same number of black nodes (the black height). Together these imply that the longest root-to-leaf path is at most twice the shortest, so the height is at most 2 log2(n + 1). Search, insert and delete therefore all run in O(log n) in the worst case.
The diagram shows the exact tree produced by the Python code on this page. Red nodes are drawn in red. You can check the invariants by eye: no red node has a red child, and every path from the root to a missing child passes exactly two black nodes.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
Θ(log n) |
Θ(log n) |
Θ(log n) |
Θ(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
Invariants: (1) root is black; (2) red nodes have black children; (3) every root-to-leaf path has the same number of black nodes. After a normal BST insert (new node colored red), restore the invariants with rotations and recoloring — at most O(log n) work.
# Red-black trees are intricate; this is a working but compact insert.
# In production use sortedcontainers.SortedList or sortedcontainers.SortedDict.
RED, BLACK = True, False
class Node:
__slots__ = ("key", "color", "left", "right", "parent")
def __init__(self, key, color=RED):
self.key, self.color = key, color
self.left = self.right = self.parent = None
class RBTree:
def __init__(self):
self.NIL = Node(None, BLACK)
self.root = self.NIL
def _rotate_left(self, x):
y = x.right
x.right = y.left
if y.left is not self.NIL: y.left.parent = x
y.parent = x.parent
if x.parent is None: self.root = y
elif x is x.parent.left: x.parent.left = y
else: x.parent.right = y
y.left = x; x.parent = y
def _rotate_right(self, x):
y = x.left
x.left = y.right
if y.right is not self.NIL: y.right.parent = x
y.parent = x.parent
if x.parent is None: self.root = y
elif x is x.parent.right: x.parent.right = y
else: x.parent.left = y
y.right = x; x.parent = y
def insert(self, key):
z = Node(key); z.left = z.right = self.NIL
y, x = None, self.root
while x is not self.NIL:
y = x
x = x.left if z.key < x.key else x.right
z.parent = y
if y is None: self.root = z
elif z.key < y.key: y.left = z
else: y.right = z
self._insert_fixup(z)
def _insert_fixup(self, z):
while z.parent and z.parent.color == RED:
gp = z.parent.parent
if z.parent is gp.left:
y = gp.right
if y.color == RED:
z.parent.color = y.color = BLACK
gp.color = RED; z = gp
else:
if z is z.parent.right:
z = z.parent; self._rotate_left(z)
z.parent.color = BLACK; gp.color = RED
self._rotate_right(gp)
else:
y = gp.left
if y.color == RED:
z.parent.color = y.color = BLACK
gp.color = RED; z = gp
else:
if z is z.parent.left:
z = z.parent; self._rotate_right(z)
z.parent.color = BLACK; gp.color = RED
self._rotate_left(gp)
self.root.color = BLACK
t = RBTree()
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
t.insert(k)
print(t.root.key)std::map, Java TreeMap, Linux CFS scheduler.A new key is inserted exactly as in an ordinary BST and coloured red, which never changes black heights. The only rule that can break is "no red child of a red parent". The fix-up loop looks at the new node's uncle (the parent's sibling). If the uncle is red, the parent and uncle become black, the grandparent becomes red, and the problem moves two levels up; this may repeat to the root. If the uncle is black, one or two rotations around the parent and grandparent restructure the local subtree and the loop ends. Finally the root is forced black. Inserting 6 into the subtree 5 then 10 is the zig-zag case: a left rotation at 5 turns it into a straight line, and a right rotation at 10 balances it.
Deletion is more involved because removing a black node reduces the black height on one side. It has four main cases (and their mirrors) built from the same recolour and rotate primitives, and it also needs at most three rotations.
When implementing or testing a red-black tree, write a checker that recomputes the invariants. It catches bugs that ordinary lookups would not reveal:
def check(t, node=None):
"""Return black height of subtree; raise if an invariant fails."""
if node is None:
node = t.root
assert node.color == BLACK, "root must be black"
if node is t.NIL:
return 1
if node.color == RED:
assert node.left.color == BLACK and node.right.color == BLACK, \
f"red node {node.key} has a red child"
if node.left is not t.NIL:
assert node.left.key < node.key
if node.right is not t.NIL:
assert node.right.key >= node.key
lh, rh = check(t, node.left), check(t, node.right)
assert lh == rh, f"black height mismatch at {node.key}"
return lh + (node.color == BLACK)
print(check(t)) # 3 (two black nodes plus the NIL leaf)
Running it after every insert in a randomised test is a simple, effective way to validate an implementation.
| Structure | Height bound | Rebalancing cost | Best for |
|---|---|---|---|
| Red-black tree | 2 log2(n+1) | At most 2 rotations per insert, 3 per delete | Write-heavy in-memory ordered maps |
| AVL tree | About 1.44 log2 n | More rotations, stricter balance | Read-heavy workloads, faster lookups |
| B-tree / B+ tree | log base B of n | Node splits and merges | Disk and SSD indexes, databases |
| Skip list | O(log n) expected | Randomised, no rotations | Concurrent ordered sets (Redis sorted sets) |
Red-black trees appear in C++ std::map and std::set implementations, Java TreeMap, and the Linux kernel's rbtree used by schedulers and memory management. Python has no built-in balanced tree; use sortedcontainers.