What is a Red-Black Tree?
A Red-Black Tree is a specialized self-balancing binary search tree (BST) where each node carries an extra bit representing its color — either Red or Black.
These colors are used to keep the tree approximately balanced during insertions and deletions, guaranteeing that search, insertion, and deletion all complete in O(log N) time, even in the worst case.
Five Red-Black Tree Properties
- Node Color: Every node is either Red or Black.
- Root Property: The root is always Black.
- Leaf Property: Every leaf (NULL sentinel) is Black.
- Red Node Property: If a node is Red, both its children must be Black — no two consecutive Red nodes may appear on any root-to-leaf path.
- Black Height Property: For every node, all simple paths from that node to its descendant leaves contain the same number of Black nodes.
Balancing Operations
Every new node is inserted as Red. If this violates the RB properties, two operations restore balance:
- Rotations (Left or Right): Structural changes that adjust the local height without breaking the BST ordering.
- Recoloring / Color Flips: Toggling node colors between Red and Black to redistribute Black-height evenly.
Case 1
Uncle is RED → Recolor parent, uncle, and grandparent. Move z up.
Case 2
Uncle is BLACK, z is right child → Left-rotate parent. Convert to Case 3.
Case 3
Uncle is BLACK, z is left child → Recolor + Right-rotate grandparent. Done.
Complexity Analysis
- Insertion Time: O(log N)
- Deletion Time: O(log N)
- Search Time: O(log N)
- Space Complexity: O(N)