Red-Black Trees
Red-Black Trees use node coloring rules to maintain approximate balance, prioritizing faster insertions and deletions over strict height guarantees.
The Five Rules
A red-black tree is a binary search tree in which every node carries one extra bit of information — a colour, red or black — and five rules constrain how those colours may be arranged. Together they force the tree to stay approximately balanced without ever storing a height.
1. Every node is either red or black. 2. The root is black. 3. Every leaf — meaning the null child positions, usually treated as sentinel NIL nodes — is black. 4. A red node's children are both black, so no red node may have a red parent or a red child. 5. Every path from a given node down to any of its descendant NIL leaves contains the same number of black nodes.
Rules 4 and 5 are the ones doing the work; the others are conventions that make those two easier to enforce. Rule 5 introduces the key quantity, the black-height: the count of black nodes on any downward path from a node to a leaf, which rule 5 guarantees is well-defined.
Treating the null positions as actual NIL sentinel nodes rather than plain null pointers is a real implementation convenience, not pedantry. It gives every real node two genuine children, so the rebalancing code never has to test for null before reading a child's colour — the same simplification a sentinel provides in a linked list.
The invariant is deliberately weaker than AVL's. AVL constrains heights numerically at every node; red-black constrains a colouring pattern. That looseness is precisely the design goal — a weaker invariant is violated less often and repaired more cheaply.
- Root black, leaves black, no red node with a red child
- Every path from a node to its leaves has the same black count
- Black-height is the quantity rule 5 makes well-defined
- NIL sentinels give every real node two children to inspect
Why the Rules Bound the Height
The height bound is not obvious from the rules, and deriving it is what turns them from arbitrary constraints into something you can reason about.
Consider the shortest possible root-to-leaf path: it would be all black nodes, of length equal to the black-height, call it bh. Now consider the longest possible path. Rule 4 forbids two consecutive red nodes, so reds can at most alternate with blacks — a path can be no more than twice as long as one made purely of blacks, at length 2·bh.
So the longest path is at most twice the shortest. That is the whole balance guarantee, and it is why the tree is described as approximately balanced rather than strictly so — one branch may be twice the depth of another, which AVL would never permit.
Converting that into a bound on n: a tree with black-height bh must contain at least 2^bh − 1 nodes, so bh ≤ log₂(n+1), and the height is at most 2·log₂(n + 1). Search, insert and delete are therefore O(log n) in the worst case.
The practical reading is that a red-black tree may be up to twice as tall as a perfectly balanced tree, where an AVL tree is at most about 44% taller. Every lookup pays that difference in extra comparisons — which is the price paid for the cheaper modifications described next.
- The shortest path is all black; the longest alternates red and black
- No two reds in a row means the longest is at most twice the shortest
- Black-height ≤ log₂(n+1), so height ≤ 2·log₂(n+1)
- Up to twice the ideal height — AVL stays within 44%
Recolouring First, Rotating Second
New nodes are inserted red. This is deliberate: adding a red node cannot violate rule 5, since it changes no path's black count. It can only violate rule 4, by landing beneath a red parent — a much easier problem to fix.
If the parent is black, the insertion is already complete and no repair is needed at all. That is the common case.
If the parent is red, the fix depends on the uncle — the parent's sibling. When the uncle is red, the repair is pure recolouring: paint the parent and uncle black, paint the grandparent red, and then re-examine the grandparent, since it may now violate rule 4 against its own parent. No rotation occurs, and the problem moves two levels up the tree.
When the uncle is black, recolouring alone cannot work and a rotation is required — one if the new node is on the outside of its grandparent, two if it zigzags on the inside, exactly mirroring the AVL single and double cases. Crucially, once a rotation is performed the tree is fixed and the loop terminates.
That structure is the whole efficiency argument. The recolouring case may repeat up the tree at O(log n) total cost, but recolouring is just flipping bits — cheap, and it touches no pointers. The expensive operation, rotation, happens at most twice on insertion and at most three times on deletion, both constant.
Compare AVL, where deletion may require a rotation at every level, up to O(log n) of them. Red-black trades a slightly taller tree for a hard constant bound on the expensive operation, and that trade is the entire reason it exists.
Deletion is genuinely more involved, introducing the notion of a 'doubly black' node when removing a black one would break rule 5, and resolving it through several cases. It is the part most people do not implement from memory, and reaching for a library is usually the right call.
| Situation | Fix | Continues? |
|---|---|---|
| Parent is black | Nothing | Done immediately |
| Parent red, uncle red | Recolour parent, uncle, grandparent | Yes — recheck the grandparent |
| Parent red, uncle black, outside | One rotation plus recolour | No — terminates |
| Parent red, uncle black, zigzag | Two rotations plus recolour | No — terminates |
- Insert red — it can only break rule 4, never rule 5
- Red uncle means recolour and move up two levels
- Black uncle means rotate, and the repair then stops
- At most 2 rotations on insert, 3 on delete — both constant
Terms, operations, and practical uses
Color Properties
- Root PropertyThe root node of a Red-Black tree is always colored black.
- Red PropertyA red node cannot have a red child (no two consecutive red nodes on any path).
- Black Depth PropertyEvery path from a node to any of its descendant NIL leaves contains the exact same number of black nodes.
Modification Rules
- Insertion ColorNew nodes are always initially colored red to avoid violating the Black Depth property.
- RecoloringIf a red node is inserted under a red parent and the uncle is also red, we recolor the parent, uncle, and grandparent.
- RestructuringIf the uncle is black, we perform tree rotations (similar to AVL) to restore the Red Property.
Practical Use
- Approximate BalanceThe longest path (alternating red/black) is at most twice the shortest path (all black).
- Write EfficiencyBecause it requires fewer rotations than AVL trees on average, it is preferred for write-heavy workloads.
- Standard LibrariesThe underlying data structure for C++ std::map, Java TreeMap, and many database indexing systems.
Repair red-black tree properties after insertion
RED, BLACK = "Red", "Black"
class RBNode:
def __init__(self, val, color=RED):
self.val = val
self.color = color
self.left = None
self.right = None
class RedBlackTree:
def __init__(self):
self.root = None
def insert(self, val):
node = RBNode(val) # every new node starts Red
if not self.root:
self.root = node
else:
current = self.root
while True:
if val < current.val:
if not current.left:
current.left = node
break
current = current.left
else:
if not current.right:
current.right = node
break
current = current.right
self.root.color = BLACK # the root is always recoloured Black
return node
tree = RedBlackTree()
tree.insert(10)
child = tree.insert(20)
print('Root is', tree.root.color)#include <iostream>
#include <string>
using namespace std;
const string RED = "Red", BLACK = "Black";
struct RBNode {
int val;
string color;
RBNode *left, *right;
RBNode(int val) : val(val), color(RED), left(nullptr), right(nullptr) {
}
};
class RedBlackTree {
public:
RBNode* root = nullptr;
RBNode* insert(int val) {
RBNode* node = new RBNode(val); // every new node starts Red
if (!root) {
root = node;
} else {
RBNode* current = root;
while (true) {
if (val < current->val) {
if(!current->left) {
current->left = node;
break;
}
current = current->left;
} else {
if(!current->right) {
current->right = node;
break;
}
current = current->right;
}
}
}
root->color = BLACK; // the root is always recoloured Black
return node;
}
};
int main() {
RedBlackTree tree;
tree.insert(10);
tree.insert(20);
cout << "Root is " << tree.root->color << '\n';
}public class Main {
static final String RED = "Red", BLACK = "Black";
static class RBNode {
int val;
String color = RED;
RBNode left, right;
RBNode(int val) {
this.val = val;
}
}
static class RedBlackTree {
RBNode root;
RBNode insert(int val) {
RBNode node = new RBNode(val); // every new node starts Red
if (root == null) {
root = node;
} else {
RBNode current = root;
while (true) {
if (val < current.val) {
if(current.left == null) {
current.left = node;
break;
}
current = current.left;
} else {
if(current.right == null) {
current.right = node;
break;
}
current = current.right;
}
}
}
root.color = BLACK; // the root is always recoloured Black
return node;
}
}
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree();
tree.insert(10);
tree.insert(20);
System.out.println("Root is " + tree.root.color);
}
}Step through it
Running on insert a red node beneath a red parent
Read all 11 Steps
- Insert 10 New nodes always arrive red. As the root it must be black, so recolour immediately.
- Insert 5 5 < 10 goes left, coloured red. A red child under a black parent breaks no rule.
- Insert 15 15 goes right, also red. Both children are red but they are siblings, not parent-child — still legal.
- Insert 1 1 < 10 then 1 < 5. It arrives red under the red node 5 — two reds in a row. Violation.
- Check the uncle The parent is 5 and its sibling — the uncle — is 15, which is red. Red uncle means no rotation is needed.
- Recolour Flip the parent and uncle to black and the grandparent to red. The red-red pair is gone and every path keeps its black count.
- Root stays black The grandparent here is the root, and the root is always black, so flip it back. Black height rose by one for every path at once.
- Insert 0 0 goes left of 5, left of 1. Red under the red node 1 — another violation.
- Black uncle This time the parent is 1 and the uncle is null, which counts as black. A black uncle cannot be fixed by recolouring alone.
- Rotate Rotate right around 5 and recolour: 1 rises to become black with 0 and 5 as red children.
- Terminates Unlike the recolour case, a rotation fixes the tree locally and never propagates further up. That is why insert is O(log n) with at most two rotations.
Why Libraries Choose It
Red-black trees back a remarkable amount of production software: std::map, std::set, std::multimap and std::multiset in C++; TreeMap and TreeSet in Java; the Linux kernel's completely fair scheduler, its virtual memory areas, and its high-resolution timers; and the fallback structure inside Java's HashMap once a bucket's chain grows past eight entries.
The reason is that a general-purpose container cannot assume its workload. If lookups dominate, AVL's shorter tree would be preferable; if modifications dominate, red-black's constant rotation bound wins. Faced with an unknown mix, the structure with the cheaper worst-case modification is the safer default — an unexpectedly write-heavy workload degrades gracefully rather than paying O(log n) rotations per deletion.
The kernel's use adds a second consideration: predictable worst-case latency. A scheduler cannot tolerate an operation that occasionally does far more work than usual, and the constant bound on rotations gives exactly that predictability.
There is also the question of what a red-black tree provides that a hash table does not, since a hash table offers O(1) average lookup. The answer is ordering: sorted iteration, range queries, and floor and ceiling lookups — 'the largest key not exceeding x' — none of which hashing can answer at any cost. That is why std::map and std::unordered_map both exist and are not interchangeable.
Two closely related structures are worth knowing. A 2-3-4 tree is a B-tree of order 4, and a red-black tree is precisely a binary encoding of one — a black node with its red children represents a single multi-key node. This equivalence is often the clearest way to understand why the rules take the form they do. Left-leaning red-black trees, introduced by Sedgewick, restrict reds to left children and roughly halve the number of cases, at some cost in performance.
For a memory footprint note: the colour is a single bit, and it typically fits in padding the node already has, so red-black balancing is effectively free in space — where AVL's stored height costs a full integer per node.
- Used by
std::map,TreeMap, and throughout the Linux kernel - Constant rotation bound gives predictable worst-case latency
- Chosen over hashing when sorted iteration or range queries are needed
- A red-black tree is a binary encoding of a 2-3-4 tree