Red-Black Trees
About
In a regular Binary Search Tree (BST), if we insert sorted data (say, 1, 2, 3, 4, ...), the tree becomes unbalanced, and performance degrades to O(n) — just like a linked list.
Self-balancing BSTs, such as AVL Trees and Red-Black Trees, solve this by automatically restructuring the tree to keep it balanced, so that all major operations (insert, delete, search) always stay O(log n) in time.
Why the Red-Black Coloring ?
The idea behind the color system is to encode balancing constraints without storing height values (as AVL Trees do).
By tagging each node as red or black, we can:
Enforce rules that keep paths from root to leaf relatively even in length.
Use color flips and rotations to maintain balance after inserts or deletes, without always recalculating heights.
The coloring introduces logical boundaries, helping maintain a reasonably balanced structure with fewer rotations than AVL Trees.
Color Example
Consider this small Red-Black Tree:
10(B)
/ \
5(R) 15(R)Root is black.
Children are red.
All paths have the same number of black nodes.
Why Red-Black Trees ?
To maintain logarithmic time complexity for insertion, deletion, and lookup:
O(log n) for search, insert, delete.
To avoid worst-case performance in unbalanced trees (like linked list structure in plain BSTs).
Red-Black Trees are less rigidly balanced than AVL Trees, so insertions/deletions are faster in practice.
What is Black Height ?
The black height of a node is the number of black nodes on any path from that node to its descendant leaves (excluding itself, including the leaves).
Red-black properties ensure that:
The shortest path has only black nodes.
The longest path alternates red and black, i.e., is at most twice as long as the shortest.
So even in the worst case, the tree doesn’t grow too tall.
Properties
To ensure balance, every Red-Black Tree must follow these 5 properties:
Every node is either red or black.
The root is always black.
All leaves (nulls or NILs) are considered black.
Red nodes cannot have red children (i.e., no two red nodes can be adjacent).
Every path from a node to its descendant NIL nodes must have the same number of black nodes.
This consistent black node count is called black-height.
Example
We’ll build a Red-Black Tree from the following sequence of insertions:
Insert: 10, 20, 30, 15, 25, 5, 1
Let’s walk through the tree structure after all insertions, assuming proper rotations and recoloring have taken place to maintain Red-Black properties.
Final Tree Structure
20 (Black)
/ \
10 (Red) 25 (Black)
/ \ \
5 (Black) 15 (Black) 30 (Red)
/
1 (Red)Color Assignment
20: Black → root must be black10: Red → red child of black (OK)25: Black5: Black → black child of red (OK)15: Black30: Red1: Red
Red-Black Tree Properties Validation
Let’s validate all 5 Red-Black Tree properties on this example:
Property 1: Every node is either red or black
All nodes have been assigned either red or black.
Red nodes:
10,30,1Black nodes:
20,5,15,25
Valid
Property 2: The root is black
Root = 20 (Black)
Valid
Property 3: All leaves (null children) are black
All null children (not shown in diagram) are considered black.
Valid
Property 4: If a node is red, then both its children are black
Check all red nodes:
10: Children =5(Black),15(Black)1: Both children are null (nulls are black)30: Child is null (null is black)
Valid
Property 5: Every path from a node to its descendant leaves has the same number of black nodes
Let’s count black nodes on different paths from root (20) to leaves:
20 → 10 → 5 → 1 → null=Black(20), Red(10), Black(5), Red(1), null→ 3 black nodes20 → 10 → 15 → null=Black(20), Red(10), Black(15), null→ 3 black nodes20 → 25 → 30 → null=Black(20), Black(25), Red(30), null→ 3 black nodes
All paths have exactly 3 black nodes
Red-Black Tree Insertion & Deletion Logic
Insertion Logic
When inserting into a Red-Black Tree, we want to:
Keep the Binary Search Tree (BST) property.
Restore all Red-Black properties after insertion.
Step 1: Insert as a Red Node
Insert the new node just like in a regular BST.
Color the new node red (this helps with maintaining the black-height).
If the new node becomes the root, recolor it to black.
Step 2: Fix Violations (Balancing Phase)
There may be a violation of the Red-Black rules — specifically:
If the parent of the new node is black → no violation.
If the parent is red → violation of the "no two reds in a row" rule.
Depending on the color of the uncle (the sibling of the parent), we take different actions:
Case 1: Uncle is Red (Recoloring)
Recolor the parent and uncle to black.
Recolor the grandparent to red.
Move the current pointer to the grandparent and repeat the process up the tree.
This case reduces red-red conflicts but may propagate the problem upward.
Case 2: Uncle is Black or Null (Rotation + Recoloring)
There are 4 sub-cases based on the direction of insertion:
Left-Left (LL): Right rotation at grandparent.
Right-Right (RR): Left rotation at grandparent.
Left-Right (LR): Left rotation at parent, then right rotation at grandparent.
Right-Left (RL): Right rotation at parent, then left rotation at grandparent.
After the rotations:
Recolor the nodes so that the new parent becomes black and the two children are red.
These operations ensure:
The red-red violation is fixed.
The black-height remains balanced.
Final Step
Always ensure that the root node is black at the end.
Deletion Logic
Deletion is more complex than insertion because removing a node — especially a black node — can disturb the black-height.
Step 1: Perform BST Deletion
Use the standard BST delete logic:
If the node has two children, find its in-order successor and replace the node with it.
Then, delete the successor.
At this point, we might be deleting:
A red node → no problem.
A black node → this causes a "black height deficit", which we need to fix.
Step 2: Fix Double Black Problem
After deleting a black node, the tree might temporarily contain an invalid state called "double black", meaning a node that is missing a black count compared to its siblings.
We fix it based on the sibling’s color and its children’s colors.
Case 1: Sibling is Red
Rotate at the parent to make the sibling black.
This transforms the problem into a situation with a black sibling (Case 2 or 3).
Case 2: Sibling is Black and its children are both black
Recolor the sibling to red.
Move the "double black" problem up to the parent.
Case 3: Sibling is Black and has at least one red child
Perform appropriate rotation based on the structure.
Recolor the sibling and parent to restore Red-Black properties.
After this, the tree is valid again.
Special Case: Deleting the Root
If the deleted node was the root, no double black arises.
Just remove the root and you're done.
Balancing via Rotation
Why Rotation Is Needed
Red-Black Trees enforce strict color and structural rules to maintain balance. When we insert or delete a node, these rules might get violated.
To restore the red-black properties, the tree must:
Restructure itself (using rotations)
Possibly recolor nodes
Rotations help reorganize the nodes without breaking the binary search tree (BST) ordering property.
Types of Rotations
There are two basic types of rotations:
1. Left Rotation
Shifts nodes counter-clockwise.
Used when a new red node is inserted as a right child and causes a red-red violation.
2. Right Rotation
Shifts nodes clockwise.
Used when a new red node is inserted as a left child and causes a red-red violation.
Each of these can be visualized as rearranging a small 3-node subtree to change shape but preserve the BST ordering.
Left Rotation
Let’s say:
x
\
y
/
T1After left rotate(x):
y
/ \
x T1Step-by-step:
ybecomes new parentxbecomes left child ofyT1becomes right child ofx
This rotation is useful when a right-heavy subtree needs to be balanced.
Right Rotation
Let’s say:
y
/
x
\
T1After right rotate(y):
x
/ \
T1 yStep-by-step:
xbecomes new parentybecomes right child ofxT1becomes left child ofy
This rotation helps when a left-heavy subtree needs to be corrected.
When Rotations Are Used
Rotations are used in specific cases during insertion or deletion:
Insertion Case:
A red-red violation (both child and parent red) occurs
If the uncle node is black, we use rotation + recoloring
Deletion Case:
A black node is removed, which may cause black-height imbalance
Rotations help push extra blackness or rearrange black nodes
Double Rotations (Left-Right or Right-Left)
Sometimes, a single rotation is not enough to restore balance.
Example:
A red node is inserted as the left-right child (left child’s right subtree). This needs:
Left rotation on the child
Right rotation on the parent
These are called double rotations and are combinations of the basic ones.
How Rotations Preserve BST Property
During a rotation:
The in-order relationship among nodes remains unchanged.
Only the structure changes, not the relative positions of values.
This ensures the rotated tree is still a valid Binary Search Tree.
Effect of Rotations on Red-Black Properties
Binary Search Tree property
Always preserved
Red-red violation
Resolved if applicable
Black-height balance
Restored via rotation
Path length uniformity
Maintained
Time Complexity
For a tree with n nodes:
Search: O(log n)
Insert: O(log n)
Delete: O(log n)
Even in the worst case, the tree stays balanced enough to keep log-time performance.
Java Implementation
// Java implementation of Red-Black Tree with Insertion and Deletion
// Includes explanation as inline comments
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
class Node {
int data;
Node left, right, parent;
boolean color;
Node(int data) {
this.data = data;
this.color = RED;
}
}
private Node root;
// Left Rotation
private void rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != null) y.left.parent = x;
y.parent = x.parent;
if (x.parent == null) root = y;
else if (x == x.parent.left) x.parent.left = y;
else x.parent.right = y;
y.left = x;
x.parent = y;
}
// Right Rotation
private void rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != null) y.right.parent = x;
y.parent = x.parent;
if (x.parent == null) root = y;
else if (x == x.parent.left) x.parent.left = y;
else x.parent.right = y;
y.right = x;
x.parent = y;
}
// Insertion fixup to maintain red-black properties
private void fixInsert(Node z) {
while (z.parent != null && z.parent.color == RED) {
if (z.parent == z.parent.parent.left) {
Node y = z.parent.parent.right; // uncle
if (y != null && 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;
rotateLeft(z);
}
z.parent.color = BLACK;
z.parent.parent.color = RED;
rotateRight(z.parent.parent);
}
} else {
Node y = z.parent.parent.left; // uncle
if (y != null && 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;
rotateRight(z);
}
z.parent.color = BLACK;
z.parent.parent.color = RED;
rotateLeft(z.parent.parent);
}
}
}
root.color = BLACK;
}
public void insert(int data) {
Node node = new Node(data);
Node y = null;
Node x = root;
while (x != null) {
y = x;
if (node.data < x.data)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y == null) root = node;
else if (node.data < y.data) y.left = node;
else y.right = node;
fixInsert(node);
}
// Transplant helper (used in deletion)
private void transplant(Node u, Node v) {
if (u.parent == null) root = v;
else if (u == u.parent.left) u.parent.left = v;
else u.parent.right = v;
if (v != null) v.parent = u.parent;
}
// Find minimum node
private Node minimum(Node x) {
while (x.left != null) x = x.left;
return x;
}
// Deletion fixup to maintain red-black properties
private void fixDelete(Node x) {
while (x != root && colorOf(x) == BLACK) {
if (x == x.parent.left) {
Node w = x.parent.right;
if (colorOf(w) == RED) {
w.color = BLACK;
x.parent.color = RED;
rotateLeft(x.parent);
w = x.parent.right;
}
if (colorOf(w.left) == BLACK && colorOf(w.right) == BLACK) {
w.color = RED;
x = x.parent;
} else {
if (colorOf(w.right) == BLACK) {
w.left.color = BLACK;
w.color = RED;
rotateRight(w);
w = x.parent.right;
}
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
rotateLeft(x.parent);
x = root;
}
} else {
Node w = x.parent.left;
if (colorOf(w) == RED) {
w.color = BLACK;
x.parent.color = RED;
rotateRight(x.parent);
w = x.parent.left;
}
if (colorOf(w.right) == BLACK && colorOf(w.left) == BLACK) {
w.color = RED;
x = x.parent;
} else {
if (colorOf(w.left) == BLACK) {
w.right.color = BLACK;
w.color = RED;
rotateLeft(w);
w = x.parent.left;
}
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
rotateRight(x.parent);
x = root;
}
}
}
if (x != null) x.color = BLACK;
}
private boolean colorOf(Node node) {
return node == null ? BLACK : node.color;
}
public void delete(int data) {
Node z = root;
while (z != null && z.data != data) {
if (data < z.data) z = z.left;
else z = z.right;
}
if (z == null) return;
Node y = z;
boolean yOriginalColor = y.color;
Node x;
if (z.left == null) {
x = z.right;
transplant(z, z.right);
} else if (z.right == null) {
x = z.left;
transplant(z, z.left);
} else {
y = minimum(z.right);
yOriginalColor = y.color;
x = y.right;
if (y.parent == z) {
if (x != null) 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;
}
if (yOriginalColor == BLACK && x != null)
fixDelete(x);
}
// In-order traversal to test tree contents
public void inorder() {
inorderHelper(root);
System.out.println();
}
private void inorderHelper(Node node) {
if (node != null) {
inorderHelper(node.left);
System.out.print(node.data + " ");
inorderHelper(node.right);
}
}
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree();
int[] values = {20, 15, 25, 10, 18, 30, 5};
for (int v : values) tree.insert(v);
System.out.print("Inorder after insertion: ");
tree.inorder();
tree.delete(15);
System.out.print("Inorder after deleting 15: ");
tree.inorder();
}
}
Structure of Red-Black Tree vs AVL Tree
Red-Black Trees tend to look more bushy (wider and shallower), while AVL Trees are more tightly balanced (more height-aware).
Example of tree heights:
AVL Tree: height ~ 1.44 logâ‚‚(n)
Red-Black Tree: height ~ 2 logâ‚‚(n)
So Red-Black Trees can afford a little imbalance in favor of fewer rotations.
Last updated