Red-Black Tree from Scratch (2026)
A Red-Black Tree is a self-balancing Binary Search Tree where each node has an extra bit representing its color — red or black. It maintains balance through five structural properties involving node colors: the root is black, red nodes cannot have red children (no two consecutive reds), and every path from root to leaf contains the same number of black nodes.
Red-Black trees guarantee O(log n) time for search, insert, and delete. They are less strictly balanced than AVL trees but require fewer rotations on average, making them preferred in language runtimes like Java's TreeMap and C++'s std::map.
Red-Black Tree Properties
The five properties are: (1) every node is either red or black; (2) the root is black; (3) leaves (null nodes) are considered black; (4) red nodes cannot have red children; (5) every path from a node to its descendant leaves has the same number of black nodes. These constraints ensure the longest path is at most twice the shortest path.
struct Node {
int data;
Node *left, *right, *parent;
bool isRed; // true = Red, false = Black
Node(int d) : data(d), left(nullptr), right(nullptr),
parent(nullptr), isRed(true) {}
};Insertion and Fixups
Insert a node as a red leaf (standard BST insert). If the parent is black, done. If the parent is red, we have a red-red violation. Depending on the uncle's color, we either recolor or perform rotations (left/right) and recolor to fix the violation, propagating upward if needed.
void fixViolation(Node*& root, Node*& pt) {
Node *parent_pt = nullptr, *grand_parent_pt = nullptr;
while ((pt != root) && (pt->isRed) && (pt->parent->isRed)) {
parent_pt = pt->parent;
grand_parent_pt = parent_pt->parent;
if (parent_pt == grand_parent_pt->left) {
Node* uncle_pt = grand_parent_pt->right;
if (uncle_pt && uncle_pt->isRed) {
grand_parent_pt->isRed = true;
parent_pt->isRed = false;
uncle_pt->isRed = false;
pt = grand_parent_pt;
} else {
if (pt == parent_pt->right) rotateLeft(root, parent_pt);
rotateRight(root, grand_parent_pt);
}
} else { /* symmetric for right child */ }
}
root->isRed = false;
}Frequently Asked Questions
Why is the root always black?
If the root were red, it could cause a red-red violation with its children. Making the root black also ensures property 5 (equal black height) holds consistently across all paths.
What is the black-height of a Red-Black tree?
The black-height is the number of black nodes on any path from the root to a leaf. By property 5, this is the same for all paths. The tree's height is at most 2× black-height.
Originally published on Ayodhyyya. Last updated June 1, 2026.