Red-Black Tree
This note is complete, reviewed, and considered stable.
A Red-Black Tree is a self-balancing Binary Search Tree where every node contains an additional piece of information called a color.
Each node is either:
- Red
- Black
The coloring rules ensure that the tree remains approximately balanced.
Why Do We Need Red-Black Trees?
A normal BST can become skewed.
Balanced BST
Height = O(log n)
Skewed BST
Height = O(n)
Red-Black Trees prevent such degeneration and keep the height bounded.
Properties of a Red-Black Tree
Every valid Red-Black Tree must satisfy the following five properties.
Every Node is Either Red or Black
Example:
Root Must Be Black
Valid:
Invalid:
Root cannot be red.
All NIL Leaves Are Black
Instead of using actual null pointers conceptually, Red-Black Trees treat every missing child as a special NIL node.
Red Node Cannot Have Red Children
No two consecutive red nodes can appear on a path.
Valid:
Invalid:
This is called a Red-Red Violation.
Every Path Must Have Same Number of Black Nodes
The number of black nodes from any node to its descendant NIL leaves must be identical.
This count is called the Black Height.
Valid:
All root-to-NIL paths contain the same number of black nodes.
Black Height
Black Height (BH) is:
Number of black nodes from a node to any NIL leaf, excluding the starting node itself.
Example:
For node 20:
Path:
20 → 10 → 5 → NIL
Black nodes below 20:
5, NIL
BH(20) = 2
Insertion in Red-Black Tree
Insertion occurs in two phases.
-
Phase 1: Insert the node exactly like a BST.
-
Phase 2: Fix Red-Black property violations.
New Nodes Are Always Inserted Red
Suppose we insert 15.
Immediately we have:
10 (Red)
|
15 (Red)
Red-Red violation.
Fixing Violations
There are two major tools:
- Recoloring
- Rotations
Case 1: Uncle is Red
Initial tree:
Node = 5
Parent = 10
Uncle = 30
Both Parent and Uncle are Red.
Solution
Recolor:
Parent -> Black
Uncle -> Black
Grandparent -> Red
Result:
If grandparent becomes root, recolor it back to black.
Case 2: Uncle is Black
Rotations are required.
Left-Left (LL) Case
Before insertion:
Violation:
Red node cannot have Red children.
After right rotation:
Right-Right (RR) Case
Before:
Left Rotation
After:
Left-Right (LR) Case
Before:
Step 1: Left Rotation
Step 2: Right Rotation
Right-Left (RL) Case
Before:
Step 1: Right Rotation
Step 2: Left Rotation
Tree Rotations
Rotations are local restructuring operations that preserve BST ordering.
Right Rotation
Before:
After:
Left Rotation
Before:
After:
Example Insertion Sequence
Insert:
10, 20, 30
Insert 10
Insert 20
Valid.
Insert 30
RR violation.
Apply left rotation:
Balanced again.
Deletion in Red-Black Tree
Deletion is significantly more complicated than insertion.
Process:
- Delete node as BST.
- If a red node is removed → usually no problem.
- If a black node is removed → black-height may decrease.
- Fix violations using:
- Recoloring
- Rotations
- Double Black resolution
Because deletion involves many cases, most implementations follow the CLRS algorithm or library implementations directly.
Red-Black Tree vs AVL Tree
| Feature | Red-Black Tree | AVL Tree |
|---|---|---|
| Balance | Looser | Stricter |
| Height | Slightly Taller | Shorter |
| Search | Slightly Slower | Faster |
| Insertion | Faster | Slower |
| Deletion | Faster | Slower |
| Rotations | Fewer | More |
| Complexity | Easier | More Strict |
Complexity of Operations
| Operation | Complexity |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
| Min | O(log n) |
| Max | O(log n) |