I want to explain red-black trees the way I understood them while studying self-balancing binary search trees. A red-black tree is a binary search tree where each node is colored either red or black, and a specific set of rules about how colors are arranged keeps the tree approximately balanced. I find this data structure important because it guarantees $O(\log n)$ time for search, insert, and delete operations, no matter what order I insert elements in, which a plain binary search tree cannot guarantee.
History and Background
I learned that red-black trees originated from work by Rudolf Bayer in 1972 on what he called “symmetric binary B-trees.” The concept was later refined and renamed “red-black tree” by Leonidas Guibas and Robert Sedgewick in 1978, giving it the coloring scheme and rules used today. Because of their reliable balancing guarantees, red-black trees became one of the most widely used self-balancing trees in real-world software, including in the C++ Standard Template Library’s map and set, and in the Linux kernel’s process scheduler.
Problem Statement
The problem I need a red-black tree to solve is preventing a binary search tree from becoming unbalanced (essentially a linked list) when elements are inserted in sorted or adversarial order, which would degrade search performance to $O(n)$. I want a structure that keeps itself balanced automatically after every insertion and deletion, guaranteeing logarithmic height at all times.
Core Concepts
- Node color – every node is either red or black.
- Black height – the number of black nodes from a node down to any leaf, which must be equal along every path.
- Red-black properties – the five rules that define a valid red-black tree.
- Rotation – left or right rotation used to restructure the tree while fixing violations.
- Recoloring – changing a node’s color to restore red-black properties without necessarily rotating.
How It Works
A valid red-black tree must satisfy five properties:
- Every node is either red or black.
- The root is always black.
- Every leaf (NIL node) is considered black.
- If a node is red, both its children must be black (no two red nodes in a row).
- Every path from a given node to any of its descendant leaves contains the same number of black nodes.
When I insert or delete a node, these properties might be violated, so I fix them using a combination of recoloring and rotations, working up the tree from the point of insertion/deletion until all properties are restored.
Working Principle
The internal logic relies on property 5 (equal black height on every path), which is what actually guarantees the balance. Since red nodes can’t have red children, the longest possible path (alternating red and black) can be at most twice as long as the shortest possible path (all black), which bounds the tree’s height at $O(\log n)$ regardless of insertion order.
Mathematical Foundation
I rely on the proof that a red-black tree with $n$ internal nodes has height at most:
$$h \leq 2 \log_2(n+1)$$
This comes from the fact that any subtree rooted at a node has at least $2^{bh(x)} – 1$ internal nodes, where $bh(x)$ is the black-height of node $x$, and since red nodes can’t be adjacent, at least half the nodes on any path are black, bounding the overall height to twice the black-height bound.
Diagrams
flowchart TD
A["10 (Black)"] --> B["5 (Red)"]
A --> C["15 (Red)"]
B --> D["2 (Black)"]
B --> E["8 (Black)"]
C --> F["12 (Black)"]
C --> G["20 (Black)"]Pseudocode
function INSERT(tree, key):
node = NEW_NODE(key, color=RED)
BST_INSERT(tree, node)
FIX_INSERT(tree, node)
function FIX_INSERT(tree, node):
while node.parent.color == RED:
if node.parent == node.grandparent.left:
uncle = node.grandparent.right
if uncle.color == RED:
node.parent.color = BLACK
uncle.color = BLACK
node.grandparent.color = RED
node = node.grandparent
else:
if node == node.parent.right:
node = node.parent
ROTATE_LEFT(tree, node)
node.parent.color = BLACK
node.grandparent.color = RED
ROTATE_RIGHT(tree, node.grandparent)
else:
// mirror case for right side
...
tree.root.color = BLACK
Step-by-Step Example
Suppose I insert keys 10, 5, 15, 3 in order into an empty red-black tree.
- Insert 10: becomes the root, recolored black (property 2).
- Insert 5: added as red, child of 10. No violation since 10 is black.
- Insert 15: added as red, child of 10. No violation.
- Insert 3: added as red, child of 5. Now I check: 5 is red and 3 is red, violating property 4 (no two reds in a row).
- I check the uncle of 3, which is 15 (red). Since the uncle is red, I recolor: 5 becomes black, 15 becomes black, and 10 becomes red (but 10 is the root, so it’s forced back to black by property 2).
- Final tree: 10 (black) with children 5 (black) and 15 (black), and 5 has a red child 3, satisfying all red-black properties.
Time Complexity
Search, insert, and delete all run in $O(\log n)$ time in the worst case, since the tree height is guaranteed to be $O(\log n)$ due to the red-black balancing properties. Rotations used during fix-up take $O(1)$ time each, and at most $O(\log n)$ rotations/recolorings are needed per insertion or deletion.
Space Complexity
Space complexity is $O(n)$ to store $n$ nodes, with an additional constant amount of memory per node to store the color bit, making the overhead minimal compared to an unbalanced BST.
Correctness Analysis
I trust red-black trees are correct because the fix-up procedures after insertion and deletion are proven to always terminate in a state satisfying all five red-black properties, and because rotations preserve the binary search tree ordering invariant. The height bound $h \leq 2\log_2(n+1)$ follows directly from property 5 combined with property 4, guaranteeing logarithmic-time operations are always possible.
Advantages
- Guarantees $O(\log n)$ worst-case time for search, insert, and delete, unlike a plain BST.
- Requires fewer rotations on average than AVL trees, making insertions and deletions faster in practice.
- Widely implemented and battle-tested in standard libraries and operating system kernels.
- Balances well even under adversarial or sorted insertion order.
Disadvantages
- More complex to implement correctly compared to a plain BST, due to the multiple insertion/deletion fix-up cases.
- Slightly less strictly balanced than AVL trees, so lookups can be marginally slower than AVL in read-heavy workloads.
- Requires extra memory per node to store color information.
Applications
I’ve seen red-black trees used in the C++ STL’s map and set containers, Java’s TreeMap and TreeSet, the Linux kernel’s completely fair scheduler and virtual memory management, and database indexing structures where balanced search performance is critical.
Implementation in C
Here is a simplified red-black tree insertion implementation in C.
#include <stdio.h>
#include <stdlib.h>
typedef enum { RED, BLACK } Color;
typedef struct Node {
int key;
Color color;
struct Node *left, *right, *parent;
} Node;
Node* root = NULL;
Node* new_node(int key) {
Node* n = (Node*)malloc(sizeof(Node));
n->key = key;
n->color = RED;
n->left = n->right = n->parent = NULL;
return n;
}
void rotate_left(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left) y->left->parent = x;
y->parent = x->parent;
if (!x->parent) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
}
void rotate_right(Node* x) {
Node* y = x->left;
x->left = y->right;
if (y->right) y->right->parent = x;
y->parent = x->parent;
if (!x->parent) root = y;
else if (x == x->parent->right) x->parent->right = y;
else x->parent->left = y;
y->right = x;
x->parent = y;
}
// Fixes red-black violations after insertion
void fix_insert(Node* z) {
while (z->parent && z->parent->color == RED) {
Node* grandparent = z->parent->parent;
if (z->parent == grandparent->left) {
Node* uncle = grandparent->right;
if (uncle && uncle->color == RED) {
z->parent->color = BLACK;
uncle->color = BLACK;
grandparent->color = RED;
z = grandparent;
} else {
if (z == z->parent->right) {
z = z->parent;
rotate_left(z);
}
z->parent->color = BLACK;
grandparent->color = RED;
rotate_right(grandparent);
}
} else {
Node* uncle = grandparent->left;
if (uncle && uncle->color == RED) {
z->parent->color = BLACK;
uncle->color = BLACK;
grandparent->color = RED;
z = grandparent;
} else {
if (z == z->parent->left) {
z = z->parent;
rotate_right(z);
}
z->parent->color = BLACK;
grandparent->color = RED;
rotate_left(grandparent);
}
}
}
root->color = BLACK;
}
void insert(int key) {
Node* z = new_node(key);
Node* y = NULL;
Node* x = root;
while (x) {
y = x;
if (z->key < x->key) x = x->left;
else x = x->right;
}
z->parent = y;
if (!y) root = z;
else if (z->key < y->key) y->left = z;
else y->right = z;
fix_insert(z);
}
void inorder(Node* n) {
if (!n) return;
inorder(n->left);
printf("%d(%s) ", n->key, n->color == RED ? "R" : "B");
inorder(n->right);
}
int main() {
int values[] = {10, 5, 15, 3};
for (int i = 0; i < 4; i++) insert(values[i]);
printf("Inorder traversal with colors: ");
inorder(root);
printf("\n");
return 0;
}
Sample Input and Output
Input: Insert keys 10, 5, 15, 3 into an empty red-black tree.
Output:
Inorder traversal with colors: 3(R) 5(B) 10(B) 15(B)
Optimization Techniques
I improve red-black tree performance by using a sentinel NIL node to simplify boundary condition checks instead of using NULL pointers everywhere, minimizing rotations by preferring recoloring when possible, and using iterative rather than recursive traversal functions to avoid stack overhead on large trees.
Common Mistakes
I’ve noticed people forget to recolor the root back to black after fix-up, mishandle the uncle-node color check (forgetting that a NIL/missing uncle counts as black), confuse left and right rotation directions, and forget to update parent pointers correctly during rotations, which corrupts the tree structure.
Further Reading
- Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms” (Red-Black Trees chapter) – https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Guibas, L. & Sedgewick, R., “A Dichromatic Framework for Balanced Trees” – https://sedgewick.io/wp-content/themes/sedgewick/papers/1978Dichromatic.pdf
- Bayer, R., “Symmetric Binary B-Trees” – https://link.springer.com/article/10.1007/BF00289509
- Linux Kernel Documentation on rbtree – https://www.kernel.org/doc/html/latest/core-api/rbtree.html
