Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A Red-Black tree is a self-balancing binary search tree that colors every node red or black and enforces four invariants: the root is black, every leaf is black, red nodes cannot have red children, and every path from a node to its leaves contains the same number of black nodes (equal black-height)
A Red-Black tree is a self-balancing binary search tree that colors every node red or black and enforces four invariants: the root is black, every leaf is black, red nodes cannot have red children, and every path from a node to its leaves contains the same number of black nodes (equal black-height).
This yields a tree at most twice the height of the corresponding perfectly balanced tree, so operations stay O(log n).
How It Works
New nodes are inserted as red leaves (a red insertion only risks violating the "no adjacent reds" rule).
The fix-up walks up the tree: if the uncle is red, recolor the parent, uncle, and grandparent; if the uncle is black, apply one or two rotations plus recoloring.
This is a localized fix that touches at most O(log n) nodes, and recoloring is O(1) per level, making insertion O(log n).
Red-Black trees are slightly looser than AVL trees but require fewer rotations on average, which is why they back most library ordered maps.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Search | O(log n) | O(1) |
| Insert | O(log n) | O(1) rotations |
| Delete | O(log n) | O(1) rotations |
| Height bound | ≤ 2 · log₂(n+1) | — |
| Recolor | O(1) | O(1) |
Best Use Cases
- TreeMap / TreeSet in Java, std::map / std::set in C++
- Linux kernel Completely Fair Scheduler (CFS) run queue
- Implementing interval trees and computational geometry primitives
- Ordered key-value stores that need fewer rotations than AVL
Worked Example
Insert [10, 20, 30, 15, 25, 5, 1] and track recolors + rotations
Input: insert in order: 10, 20, 30, 15, 25, 5, 1; then search 25- 1 Insert 10 (root, black), 20 (red right child), 30 (red) — 20's uncle 10 is red, so recolor rather than rotate.
- 2 A left rotation at 10 lifts 20 to root; 30 recolors to black, keeping the black-height invariant.
- 3 Insert 15 and 25: standard red insertions with local recoloring to fix the no-red-red rule.
- 4 Insert 5: fine. Insert 1: 1's parent 5 is red and its uncle 15 is red — recolor, then fix upward.
- 5 The result: root 20 (black), left 10 (red) with black children 5 (→ red 1) and 15, right 30 (black) with red child 25.
- 6 Every root-to-leaf path has the same number of black nodes (black-height 2). Search 25 finds it in O(log n).
Pseudocode
insert(z):
BST-insert z colored RED
while parent(z) is RED:
if uncle(z) is RED:
recolor parent, uncle, grandparent
z = grandparent
else:
if z is inner child: z = parent(z); rotate
rotate grandparent; swap colors
color root BLACK 1. Every node is RED or BLACK 2. The root is always BLACK 3. Red nodes have only BLACK children 4. Every path from root to leaf has the same number of BLACK nodes (black-height)
Insert Sequence
Watch recoloring and rotations restore the Red-Black invariants after each insert.