A red-black tree is a self-balancing binary search tree where each node stores an extra bit representing its color – either red or black. Invented by Rudolf Bayer in 1972 (originally called "symmetric binary B‑tree"), it was given its modern name by Guibas and Sedgewick in 1978. Red-black trees guarantee O(log n) time for search, insert, and delete operations, where n is the number of elements, making them suitable for associative arrays, real‑time systems, and as a foundation for other data structures.
Red-black trees are closely related to 2‑3‑4 trees: every red-black tree corresponds to at least one 2‑3‑4 tree, and the color flips and rotations in a red-black tree emulate the insert/delete operations of a 2‑3‑4 tree. Compared with AVL trees, red-black trees sacrifice some balance to reduce rotations during insertions and deletions, often resulting in better overall performance.
Properties
In addition to the standard binary search tree constraints, every valid red-black tree must satisfy the following:
- Every node is either red or black.
- The root is black.
- All leaves (NIL nodes) are black.
- If a node is red, both its children must be black (i.e., no two consecutive red nodes on any root-to-leaf path).
- Every simple path from a node to any of its descendant leaves contains the same number of black nodes.
These rules ensure that the longest possible path from root to leaf is at most twice the length of the shortest possible path, which guarantees approximate balance and thus O(log n) operation bounds.
Operations
Read-only operations are identical to those of an ordinary binary search tree. Insertions and deletions, however, may violate the properties above and require rebalancing through color changes (O(log n)) and a limited number of tree rotations (at most three for deletions, two for insertions).
Insertion
A new node is inserted as in a BST and initially colored red. If its parent is black, the tree remains valid. Otherwise, we examine the colors of nearby nodes, using the terms uncle (parent’s sibling), grandparent, etc. The procedure uses five cases, each illustrated below with C code. Let N be the newly inserted node, P its parent, G its grandparent, and U its uncle.
// Helper functions
node* grandparent(node *n) {
return n->parent->parent;
}
node* uncle(node *n) {
if (n->parent == grandparent(n)->left)
return grandparent(n)->right;
else
return grandparent(n)->left;
}
Case 1: N is the root. Color it black.
void insert_case1(node *n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n);
}
Case 2: P is black. The tree is valid.
void insert_case2(node *n) {
if (n->parent->color == BLACK)
return;
else
insert_case3(n);
}
Case 3: Both P and U are red. Repaint them black and G red, then recursively check G (starting from case 1).
void insert_case3(node *n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n));
} else
insert_case4(n);
}
Case 4: P is red, U is black (or NIL), and N is a right child while P is a left child (or the mirror image). Perform a left rotation to transform into case 5.
void insert_case4(node *n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n);
n = n->right;
}
insert_case5(n);
}
Case 5: P is red, U is black, and N is a left child while P is also a left child (or mirror). Rotate G right, swap colors of P and G.
void insert_case5(node *n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(n->parent);
} else {
rotate_left(n->parent);
}
}
All calls are tail‑recursive; insertion is in‑place.
Deletion
When the node to delete has two children, we replace its value with the successor (or predecessor) and then delete that successor, which can have at most one child. We therefore only need to handle deletion of a node with at most one non‑leaf child. Let N be the node that replaces the deleted node after removal. If N or its father was black, the tree may violate property 5. We then balance using six cases. Helper to find sibling:
struct node* sibling(struct node *n) {
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
Simplified deletion procedure:
void delete_one_child(struct node *n) {
struct node *child = is_leaf(n->right) ? n->left : n->right;
replace_node(n, child);
if (n->color == BLACK) {
if (child->color == RED)
child->color = BLACK;
else
delete_case1(child);
}
free(n);
}
The six cases (assuming N is a left child; mirror otherwise):
- Case 1: N is the new root – done.
- Case 2: Sibling S is red. Rotate P left, recolor, then proceed to cases 4–6.
- Case 3: P, S, and both S’s children are black. Color S red and rebalance on P.
- Case 4: S and its children are black, P is red. Swap colors of P and S.
- Case 5: S is black, its left child is red, right child is black (N left). Rotate S right and swap colors to prepare for case 6.
- Case 6: S is black, its right child is red (N left). Rotate P left, recolor appropriately. All paths contain the same number of black nodes.
Detailed code for each case (mirror conditions omitted for brevity but included in the full implementation below):
void delete_case1(struct node *n) {
if (n->parent != NULL)
delete_case2(n);
}
void delete_case2(struct node *n) {
struct node *s = sibling(n);
if (s->color == RED) {
n->parent->color = RED;
s->color = BLACK;
if (n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3(n);
}
void delete_case3(struct node *n) {
struct node *s = sibling(n);
if ((n->parent->color == BLACK) && (s->color == BLACK) &&
(s->left->color == BLACK) && (s->right->color == BLACK)) {
s->color = RED;
delete_case1(n->parent);
} else
delete_case4(n);
}
void delete_case4(struct node *n) {
struct node *s = sibling(n);
if ((n->parent->color == RED) && (s->color == BLACK) &&
(s->left->color == BLACK) && (s->right->color == BLACK)) {
s->color = RED;
n->parent->color = BLACK;
} else
delete_case5(n);
}
void delete_case5(struct node *n) {
struct node *s = sibling(n);
if (s->color == BLACK) {
if ((n == n->parent->left) && (s->right->color == BLACK) && (s->left->color == RED)) {
s->color = RED;
s->left->color = BLACK;
rotate_right(s);
} else if ((n == n->parent->right) && (s->left->color == BLACK) && (s->right->color == RED)) {
s->color = RED;
s->right->color = BLACK;
rotate_left(s);
}
}
delete_case6(n);
}
void delete_case6(struct node *n) {
struct node *s = sibling(n);
s->color = n->parent->color;
n->parent->color = BLACK;
if (n == n->parent->left) {
s->right->color = BLACK;
rotate_left(n->parent);
} else {
s->left->color = BLACK;
rotate_right(n->parent);
}
}
Complete C++ Implementation
Below is a full, working C++ implementation of a red‑black tree. It demonstrates insertion, deletion, and in‑order traversal. The code has been restructured and variable names changed for clarity.
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
class RBTree {
private:
struct Node {
int value;
Color color;
Node *left, *right, *parent;
Node(int v) : value(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
Node* grandparent() const {
return parent ? parent->parent : nullptr;
}
Node* uncle() const {
Node* g = grandparent();
if (!g) return nullptr;
return (parent == g->left) ? g->right : g->left;
}
Node* sibling() const {
return (parent->left == this) ? parent->right : parent->left;
}
};
Node* root;
Node* nil;
void leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != nil) y->left->parent = x;
y->parent = x->parent;
if (x->parent == nil)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
void rightRotate(Node* y) {
Node* x = y->left;
y->left = x->right;
if (x->right != nil) x->right->parent = y;
x->parent = y->parent;
if (y->parent == nil)
root = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
}
void insertFixup(Node* z) {
while (z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
Node* y = z->parent->parent->right;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
z = z->parent;
leftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
} else { // symmetric
Node* y = z->parent->parent->left;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
}
root->color = BLACK;
}
void insert(Node* z) {
Node* y = nil;
Node* x = root;
while (x != nil) {
y = x;
if (z->value < x->value)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == nil)
root = z;
else if (z->value < y->value)
y->left = z;
else
y->right = z;
z->left = nil;
z->right = nil;
z->color = RED;
insertFixup(z);
}
void transplant(Node* u, Node* v) {
if (u->parent == nil)
root = v;
else if (u == u->parent->left)
u->parent->left = v;
else
u->parent->right = v;
v->parent = u->parent;
}
Node* minimum(Node* x) {
while (x->left != nil)
x = x->left;
return x;
}
void deleteFixup(Node* x) {
while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node* w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
leftRotate(x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rightRotate(w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
leftRotate(x->parent);
x = root;
}
} else {
Node* w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rightRotate(x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
leftRotate(w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rightRotate(x->parent);
x = root;
}
}
}
x->color = BLACK;
}
void deleteNode(Node* z) {
Node* y = z;
Node* x;
Color yOrigColor = y->color;
if (z->left == nil) {
x = z->right;
transplant(z, z->right);
} else if (z->right == nil) {
x = z->left;
transplant(z, z->left);
} else {
y = minimum(z->right);
yOrigColor = y->color;
x = y->right;
if (y->parent == z) {
x->parent = y;
} else {
transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
delete z;
if (yOrigColor == BLACK)
deleteFixup(x);
}
void inorder(Node* p) {
if (p == nil) return;
inorder(p->left);
cout << p->value << " ";
inorder(p->right);
}
public:
RBTree() {
nil = new Node(0);
nil->color = BLACK;
nil->left = nil->right = nullptr;
root = nil;
}
~RBTree() { /* destructor omitted for brevity */ }
void insert(int val) {
Node* z = new Node(val);
insert(z);
}
void remove(int val) {
Node* z = root;
while (z != nil) {
if (val == z->value) break;
else if (val < z->value) z = z->left;
else z = z->right;
}
if (z != nil) deleteNode(z);
}
void print() {
inorder(root);
cout << endl;
}
};
The implementation above uses a sentinel nil to simplify boundary conditions. All operations preserve the red‑black properties and exhibit guaranteed O(log n) time.