TreesData structureaka RB tree, symmetric binary B-tree

Red-Black Tree

A self-balancing BST that colors nodes red or black and enforces color rules so that no path is more than twice as long as any other.

▶ Visualize Pattern: Intervals Practice (2)

Progress

Definition

A red-black tree is a Binary Search Tree where each node carries one bit of color and five rules hold: every node is red or black; the root is black; every leaf (null) is black; a red node has two black children (no two reds in a row); and every root-to-leaf path has the same number of black nodes (the black-height). Together these imply the longest path is at most twice the shortest, so h ≤ 2 log₂(n + 1).

Compared with an AVL Tree, a red-black tree is slightly taller but needs at most two rotations per insert and three per delete, with the rest of the fix-up done by recoloring. That makes it the default choice for library ordered maps: C++ std::map/std::set, Java TreeMap/TreeSet, the Linux kernel scheduler and many memory allocators.

A red-black tree is exactly a B-Tree of order 4 (a 2-3-4 tree) drawn as a binary tree: each black node with its red children forms one B-tree node. That view explains why the rules look arbitrary but produce balance.

self-balancingcoloringO(log n) guaranteedstd::mapTreeMap

Intuition

A mental model before the formal terms.

Think of black nodes as "real" levels and red nodes as extra keys squeezed into the same level. The rule "same black count on every path" means every leaf sits at the same *black* depth, like a perfectly balanced tree; the rule "no red-red" limits how many extras can hide in one level. So the tree is a perfect tree with at most a factor-of-two stretch.

Insert always paints the new node red so that black-heights stay equal; the only rule that can break is red-red, and that is fixed by pushing the problem upward with recolors until a rotation or the root resolves it.

How it works

Insert as in a BST and color the new node red. If its parent is black, done.
If the parent is red, look at the uncle. Uncle red: recolor parent and uncle black, grandparent red, and repeat at the grandparent. Uncle black: rotate — a single rotation at the grandparent for the "line" case, a double rotation for the "triangle" case — then recolor so the subtree root is black.
Finally paint the root black; this can only increase black-height uniformly.
Delete removes a node with at most one child (after successor replacement). Removing a red node breaks nothing. Removing a black node creates a "double black" deficit, resolved by cases on the sibling's color and its children's colors, using at most three rotations.
Search, min, max, successor and inorder traversal are identical to a plain BST.

Why it works

Let bh be the black-height. The subtree rooted at any node contains at least 2^bh - 1 nodes (induction on height). Since no two reds are adjacent, h ≤ 2·bh, so n ≥ 2^(h/2) - 1 and h ≤ 2 log₂(n + 1).

Each insert fix-up step either terminates with at most two rotations or moves the violation two levels up, so the fix-up is O(log n) with O(1) rotations.

Rotations preserve inorder order, and the recolor cases are chosen precisely so black-height stays equal on all paths after each step.

Operations

Operation	Description	Cost
search(key)	Standard BST descent.	O(log n)
insert(key)	BST insert as red, then recolor/rotate fix-up walking up; ≤ 2 rotations.	O(log n)
delete(key)	BST delete then double-black fix-up; ≤ 3 rotations.	O(log n)
rotate	Same pointer surgery as AVL, plus color swaps.	O(1)
min / max / successor	Same as BST.	O(log n)
inorder traversal	Sorted output.	O(n)

Recognition

How to tell a problem wants this.

You need a guaranteed-O(log n) ordered container and you are in a language with one built in: reach for TreeMap/std::map and know it is a red-black tree.
Interview question: "how does TreeMap work?" or "compare AVL and red-black".
Write-heavy ordered workloads where fewer rotations matter.

“overlapping intervals” → Intervals “binary tree” → Tree Traversal

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related AVL Tree visualization.

Commands — insert N commands separated by commas

Empty tree

1/63Empty AVL tree. Each node shows its balance factor bf = height(left) − height(right); the invariant is |bf| ≤ 1 everywhere.

Comparing / rebalancingInsertion pathNewly insertedMoved by a rotation

PseudocodeLearn AVL Tree →

1insert(node, key): BST insert recursively
2update height(node); bf = height(left) - height(right)
3if bf > 1 and key < node.left.key:  LL → rotateRight(node)
4if bf < -1 and key > node.right.key: RR → rotateLeft(node)
5if bf > 1 and key > node.left.key:  LR → rotateLeft(node.left), then rotateRight(node)
6if bf < -1 and key < node.right.key: RL → rotateRight(node.right), then rotateLeft(node)
7return node (possibly the new subtree root)

Variables

height0

Complexity

access O(log n)

search O(log n)

insert O(log n)

delete O(log n)

Speed

Pseudocode

1insert(key):
2  z = bstInsert(key); z.color = RED
3  while z.parent is RED:
4    uncle = sibling of z.parent
5    if uncle is RED: recolor parent, uncle BLACK; grandparent RED; z = grandparent
6    else:
7      if z is inner child: rotate z.parent toward outside; z = old parent
8      rotate grandparent away from z; swap colors of parent and grandparent
9  root.color = BLACK

Implementation

1from typing import Optional
2 
3RED = "red"
4BLACK = "black"
5 
6 
71 · Node with color and parent pointer
8class RBNode:
9    def __init__(self, key: int) -> None:
10        self.key = key
11        self.color = RED
12        self.left: Optional["RBNode"] = None
13        self.right: Optional["RBNode"] = None
14        self.parent: Optional["RBNode"] = None
15 
16 
17class RBTree:
18    def __init__(self) -> None:
19        self.root: Optional[RBNode] = None
20 
21    def contains(self, key: int) -> bool:
22        cur = self.root
23        while cur is not None:
24            if key == cur.key:
25                return True
26            cur = cur.left if key < cur.key else cur.right
27        return False
28 
292 · Rotations that maintain parent pointers
30    def _rotate_left(self, x: RBNode) -> None:
31        y = x.right
32        assert y is not None
33        x.right = y.left
34        if y.left is not None:
35            y.left.parent = x
36        y.parent = x.parent
37        if x.parent is None:
38            self.root = y
39        elif x is x.parent.left:
40            x.parent.left = y
41        else:
42            x.parent.right = y
43        y.left = x
44        x.parent = y
45 
46    def _rotate_right(self, y: RBNode) -> None:
47        x = y.left
48        assert x is not None
49        y.left = x.right
50        if x.right is not None:
51            x.right.parent = y
52        x.parent = y.parent
53        if y.parent is None:
54            self.root = x
55        elif y is y.parent.left:
56            y.parent.left = x
57        else:
58            y.parent.right = x
59        x.right = y
60        y.parent = x
61 
623 · BST insert as a red leaf
63    def insert(self, key: int) -> None:
64        z = RBNode(key)
65        parent: Optional[RBNode] = None
66        cur = self.root
67        while cur is not None:
68            parent = cur
69            if key == cur.key:
70                return
71            cur = cur.left if key < cur.key else cur.right
72        z.parent = parent
73        if parent is None:
74            self.root = z
75        elif key < parent.key:
76            parent.left = z
77        else:
78            parent.right = z
79        self._fix_insert(z)
80 
81    @staticmethod
82    def _is_red(n: Optional[RBNode]) -> bool:
83        return n is not None and n.color == RED
84 
854 · Fix-up: recolor or rotate while parent is red
86    def _fix_insert(self, z: RBNode) -> None:
87        while self._is_red(z.parent):
88            p = z.parent
89            assert p is not None
90            g = p.parent
91            assert g is not None  # a red node is never the root
92            if p is g.left:
93                uncle = g.right
94                if self._is_red(uncle):  # case 1: recolor, move up
95                    assert uncle is not None
96                    p.color = uncle.color = BLACK
97                    g.color = RED
98                    z = g
99                else:
100                    if z is p.right:  # case 2: LR -> LL
101                        z = p
102                        self._rotate_left(z)
103                        p = z.parent
104                        assert p is not None
105                    p.color = BLACK  # case 3: rotate
106                    g.color = RED
107                    self._rotate_right(g)
108            else:  # mirror image
109                uncle = g.left
110                if self._is_red(uncle):
111                    assert uncle is not None
112                    p.color = uncle.color = BLACK
113                    g.color = RED
114                    z = g
115                else:
116                    if z is p.left:
117                        z = p
118                        self._rotate_right(z)
119                        p = z.parent
120                        assert p is not None
121                    p.color = BLACK
122                    g.color = RED
123                    self._rotate_left(g)
1245 · Root is always black
125        assert self.root is not None
126        self.root.color = BLACK
127 
128    def inorder(self) -> list[int]:
129        out: list[int] = []
130        stack: list[RBNode] = []
131        cur = self.root
132        while cur or stack:
133            while cur:
134                stack.append(cur)
135                cur = cur.left
136            cur = stack.pop()
137            out.append(cur.key)
138            cur = cur.right
139        return out

Walkthrough

Colors are module-level string constants; nodes start RED with parent = None.
Rotations assert the pivot child exists and use is for identity checks like x is x.parent.left.
insert descends iteratively, attaches the red node and calls _fix_insert.
_fix_insert follows the three cases; the many assert ... is not None lines exist to satisfy static type checkers, since the invariants guarantee them.
The root is forced black at the end.

Complexity (this implementation)

time O(log n) insert, search · space O(1) extra

Iterative, so no RecursionError risk; inorder is also iterative.

Language notes

Use is / is not for node identity; == would fall back to identity anyway but is states the intent.
A shared NIL sentinel node (as in CLRS) removes most None checks at the cost of extra care in inorder.
Python has no red-black tree in the stdlib; sortedcontainers is the common third-party choice and is faster than a pure-Python tree.

Common mistakes in this language

Comparing colors with is on strings — it happens to work for interned literals but use ==.
Forgetting to re-read p = z.parent after the case-2 rotation.
Leaving the root red after the loop.

Language differences that matter here

C++ has red-black trees built in (std::map/std::set); JS/TS/Python do not.
TS uses a type guard so uncle.color type-checks; Python needs assert lines for the same purpose; JS and C++ rely on the invariant only.
Identity comparison: C++ compares pointers with ==, JS/TS use ===, Python uses is.

Complexity

Operation	Average	Worst	Note
Access	O(log n)	O(log n)
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)	≤ 2 rotations, O(log n) recolors.
Delete	O(log n)	O(log n)	≤ 3 rotations.
Update	O(log n)	O(log n)
Rotation	O(1)	O(1)
Inorder traversal	O(n)	O(n)
Space	O(n)		Height ≤ 2 log₂(n + 1). One color bit per node (often stored in a pointer's low bit).

Advantages & disadvantages

Advantages

Guaranteed O(log n) with a constant number of rotations per update — good for write-heavy use.
Only one bit of metadata per node.
Battle-tested: the implementation behind most standard library ordered maps.

Disadvantages

Up to twice as tall as an AVL tree, so lookups can be slightly slower.
Deletion fix-up has many cases and is notoriously error-prone to write by hand.
Pointer chasing and poor locality like any binary tree; B-Trees win for large or disk-resident data.

Use cases

std::map, std::set, Java TreeMap, TreeSet, .NET SortedDictionary.
Linux CFS scheduler run-queue and virtual memory area trees.
Sweep-line algorithms that need an ordered status structure with predecessor/successor.

Use it when

You need a general-purpose ordered map with guaranteed bounds and mixed reads/writes.
You are using a standard library ordered container — you already are using one.
Fewer rotations matter, e.g. when rotations invalidate cached data or iterators.

Avoid it when

Read-dominated workloads where the shallower AVL Tree is measurably faster.
No ordering needed — Hash Map.
Large or disk-resident data — B-Tree / B+ Tree.

Alternatives

AVL Tree Skip List B-Tree Hash Map

Compare: AVL Tree vs Red-Black Tree

Common mistakes

Forgetting to set the root black after fix-up.
Treating null leaves as red; they must count as black in the uncle test.
Missing the triangle-to-line pre-rotation, which leaves a red-red violation after the main rotation.
Losing parent pointer updates during rotations — every rotation touches three parent links.

Interview patterns

State the five properties and derive the 2 log₂(n+1) height bound.
Walk through inserting 10, 20, 30 (recolor vs rotate cases).
Explain why TreeMap uses red-black rather than AVL.
Map a red-black tree to a 2-3-4 tree to explain the color rules.

Interview questions on this

Recursion versus iterationIntermediate
Greedy or dynamic programming?Advanced

Mock interviews

Merge IntervalsIntermediate

Interview problems

Kth Smallest Element in a BSTmedium Meeting Rooms IImedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related