1. One-Liner
RB insert places a new red node like BST, then recolors and rotates to fix red-red conflicts and black-height rules.
2. The Problem It Solves
Balanced search trees need fast search/insert/delete with worst-case guarantees. Red-black trees keep height ≤ 2× the black height, giving O(log n) with simpler rebalancing than AVL in many libraries (TreeMap, std::map).
3. The Core Idea
New nodes start red (avoid breaking black count). If parent is red, fix using uncle color: if uncle red → push blackness up (recolor parent, uncle, grandparent). If uncle black → rotate + recolor to eliminate double red and preserve black paths.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | BST-insert new node z as red leaf. |
| 2 | If root → paint black; done. |
| 3 | While parent of z is red: let p = parent, g = grandparent, u = uncle. |
| 4 | If u red: recolor p,u black, g red; z = g; continue. |
| 5 | Else: align with rotations (LR/RL as needed), then rotate + recolor so black-height and no adjacent reds. |
5. Dry Run Example
Insert into near-balanced tree: first recolor case bubbles red to grandparent; if uncle black, one or two rotations finish—local picture matches CLRS cases.
6. Key Properties
| Invariant | Meaning |
|---|---|
| Black height | Same # black nodes on root→leaf paths |
| No double red | Red node’s parent is black |
| Root black | Often enforced after fixup |
7. Where It Is Used
| Library | Role |
|---|---|
| Java TreeMap | Sorted map |
| C++ std::map | Typically RB |
| Linux kernel | rbtree for intervals |
8. Interview Tips
Know why new node red. Explain uncle red vs black branches. Left-leaning red-black is a simplified variant (Sedgewick). Compare amortized rotations vs AVL.
9. Comparison with Other Algorithms
| Tree | Balance | Insert typical |
|---|---|---|
| RB | Height ≤ 2bh | Fewer rotations |
| AVL | Stricter | More rotations |
| B-tree | Node fanout | Disk-oriented |
10. Complexity
| -- | -- |
|---|---|
| Insert | O(log n) time, O(1) rotations amortized typical |
| Space | O(n) pointers |
Implementation Example (PYTHON)
RED, BLACK = 0, 1
class RBNode:
def __init__(self, k):
self.k, self.c = k, RED
self.l = self.r = self.p = None
def left_rotate(T, x):
y = x.r
x.r = y.l
if y.l: y.l.p = x
y.p = x.p
if not x.p: T.root = y
elif x == x.p.l: x.p.l = y
else: x.p.r = y
y.l, x.p = x, y