Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithms · Data Structures

Balance in Two Colors.

Watch the explainer

A red-black tree keeps a binary search tree balanced using nothing but a single bit of color per node and a handful of rules. The rules: the root is black; a red node’s children are black (no two reds in a row); and every root-to-leaf path passes through the same number of black nodes. Together they force the longest path to be at most twice the shortest — so the height stays O(log n) and search/insert/delete are all logarithmic. Insertion is the interesting part: add the new node red (to avoid disturbing black-heights), then fix any red-red violation with recolorings and at most a couple of rotations. Insert keys and watch the tree recolor and rotate itself back into balance.

O(log n) operations · root black, no red-red, equal black-height · fix with recolor + ≤2 rotations
colors

Each node is red or black — one bit that encodes the balancing constraints.

no red-red

A red node cannot have a red child (so red nodes are spread out).

black-height

Every root-to-leaf path has the same number of black nodes.

insert fix-up

Add the node red, then recolor and rotate to restore the color rules.

redblack.js — recolor, rotate, rebalance
Ready
A red-black tree. Each insert adds a red node, then restores the rules (no two reds in a row; equal black-height on every path) with recolorings and rotations. Insert to build a balanced tree.
0
nodes
0
height
–
last fix

How it works

The colors are a compact way to guarantee balance without storing exact heights. Because no path may have two reds in a row and all paths share the same black count, the longest possible path (alternating red-black) is at most twice the shortest (all black) — which caps the height at 2·log₂(n+1). Insertion tries not to break these rules: a new node is colored red, since adding a red leaf doesn’t change any path’s black-height. The only thing that can go wrong is a red node landing under a red parent. The fix depends on the uncle (the parent’s sibling): if the uncle is red, a pure recoloring pushes the problem up two levels; if the uncle is black, one or two rotations plus a recolor fix it locally and permanently. So each insertion needs only O(log n) recolorings and at most two rotations.

1

Insert as a red BST leaf

Place the new key by ordinary BST descent and color it red. A red leaf keeps every path’s black-height unchanged, so the only possible violation is a red child under a red parent.

2

Red uncle → recolor

If the new node’s uncle (its parent’s sibling) is red, recolor the parent and uncle black and the grandparent red. This fixes the local red-red but may push a violation up to the grandparent; repeat from there.

3

Black uncle → rotate

If the uncle is black, a rotation (one for the "zig-zig" case, two for "zig-zag") plus a recolor restores the rules locally and for good — no further propagation needed.

✓

Recolor the root black

Finally ensure the root is black. The tree now satisfies all red-black rules, so its height stays O(log n) and every operation is logarithmic.

Operations
O(log n)
Height
≤ 2·log₂(n+1)
Rotations / insert
≤ 2
Used in
std libraries

The code

# red-black insert fix-up (0 = red, 1 = black) def insert_fixup(z): while z.parent.color == RED: if z.parent == z.parent.parent.left: uncle = z.parent.parent.right if uncle.color == RED: # case 1: recolor z.parent.color = uncle.color = BLACK z.parent.parent.color = RED; z = z.parent.parent else: if z == z.parent.right: # case 2: zig-zag z = z.parent; rotate_left(z) z.parent.color = BLACK # case 3: zig-zig z.parent.parent.color = RED; rotate_right(z.parent.parent) else: ... # mirror image root.color = BLACK

Quick check

1. What color is a newly inserted red-black tree node, and why?

2. When the new node’s uncle is red, how is the violation fixed?

3. What do the red-black rules guarantee about the tree’s height?

FAQ

What is a red-black tree?

A self-balancing BST where each node is red or black under rules — root black, red nodes have black children, and every root-to-leaf path has equal black count — that keep it balanced, bounding height to O(log n). Search, insert, and delete are all O(log n).

How does insertion keep a red-black tree balanced?

Insert the node red (which keeps black-heights unchanged), then fix any red-red: a red uncle means recolor (possibly propagating up), a black uncle means one or two rotations plus a recolor to fix it locally. Each insert needs O(log n) recolorings and ≤2 rotations.

How do red-black trees compare to AVL trees?

Both are O(log n) self-balancing BSTs. AVL is more strictly balanced (faster lookups) but does more rotations on updates; red-black allows slightly more imbalance and fewer rotations (cheaper updates). Libraries (C++ std::map, Java TreeMap) usually use red-black; AVL is chosen when lookups dominate.

Where are red-black trees used?

Standard-library ordered containers (C++ std::map/std::set, Java TreeMap/TreeSet) and system software (the Linux kernel uses them for scheduling and memory management) — a common default wherever you need an ordered map/set with guaranteed O(log n) operations.

The picture: what sorted inserts turn into

1B2B3B4R5R6B7Rkeys 1..7 inserted in order: height 4; a plain BST would be 7
The page’s sorted-input test (keys 1 to 7, ascending), drawn after the last insert. Dashed circles are red nodes, solid are black. Every path from the root to an empty slot passes through exactly two black nodes (the root included), and no red node has a red child. The tree is not perfectly balanced: the right side is deeper than the left, which is allowed. Ascending inserts are the worst case for a plain binary search tree, which would be a 7-deep chain; the recolors and 3 rotations kept this one at height 4.

Worked example, step by step

Insert 1, 2, 3, 4, 5, 6, 7 into an empty tree. Each key is added as a red leaf by ordinary search-tree descent, then the fix-up runs while a red node has a red parent. In the last column R and B mark colours and (left,right) shows the shape, with · for an empty slot.

InsertWhat the fix-up didHeightTree after
1first node: it is the root, so it is made black11B(·,·)
2red parent is black, nothing to fix21B(·,2R(·,·))
3zig-zig: rotate 1 left22B(1R(·,·),3R(·,·))
4red uncle: recolor 3 and 1 black, 2 red32B(1B(·,·),3B(·,4R(·,·)))
5zig-zig: rotate 3 left32B(1B(·,·),4B(3R(·,·),5R(·,·)))
6red uncle: recolor 5 and 3 black, 4 red42B(1B(·,·),4R(3B(·,·),5B(·,6R(·,·))))
7zig-zig: rotate 5 left42B(1B(·,·),4R(3B(·,·),6B(5R(·,·),7R(·,·))))

Highlighted rows are the ones that needed a rotation. Insert 3 is the first problem: 1 is the root, 2 is its red right child, 3 is red under red, and the uncle (the empty slot on the left of 1) counts as black, so one rotation fixes it for good. Insert 4 is the other case: 4’s parent 3 and its uncle 1 are both red, so the fix is pure recoloring, no rotation. That recolor turns the root 2 red, and the last line of the algorithm turns it black again; without that line the tree breaks (see below). Inserts 5, 6 and 7 repeat the same two cases further down the right side. In total 3 rotations and 6 node recolors for 7 inserts. On 1,000 ascending keys the tree ends with height 17, using 983 rotations and 2934 recolors, and its rule check reports no violations.

Complexity and trade-offs

CaseTimeSpaceWhy
Search, insert, delete (red-black)O(log n) worst caseO(n)Height is at most 2·log₂(n+1) because the longest path (alternating colours) is at most twice the shortest (all black). One colour bit per node.
Rebalancing per insertO(1) rotations, O(log n) recolorsO(1) extraAt most two rotations per insert. Recoloring can climb toward the root, but it moves up two levels at a time. The 1,000 ascending inserts above averaged 0.98 rotations each.
Plain binary search treeO(log n) average, O(n) worstO(n)No balancing at all. Sorted input makes a chain: the keys 1..7 give height 7, against 4 here.
AVL treeO(log n) worst caseO(n)Stricter balance gives a shallower tree and faster lookups, but inserts and deletes may rotate more. Choose AVL for read-heavy data and red-black for mixed workloads.
Sorted array / hash mapinsert O(n) / lookup O(1) averageO(n)An array needs shifting to insert. A hash map is quicker for exact lookups but has no key order, so it cannot answer “next larger key” or range queries.

The case for a red-black tree is the worst-case promise together with ordered operations: predecessor, successor, range scans and in-order iteration are all available without sorting. What you give up is simplicity. Deletion has more cases than insertion, and the code is easier to get wrong than AVL’s height field. If you only need lookups by exact key, a hash table is faster; if the data sits on disk, a B-tree wins, because it packs many keys into each node and so reads far fewer blocks.

Common mistakes

  • Not turning the root black at the end

    Recoloring can push a red up to the root. Inserting 1, 2, 3, 4, 5 without the final “root is black” line gives 2R(1B(·,·),4B(3R(·,·),5R(·,·))), and the check reports: root is red. With the line, the same keys give 2B(1B(·,·),4B(3R(·,·),5R(·,·))).

  • Treating an empty uncle as red

    Missing children are black. If the code reads a null uncle as red it recolors when it should rotate. With keys 1, 2, 3 that leaves the tree as 1B(·,2B(·,3R(·,·))), which the check rejects (black-height differs (1 vs 2)), instead of the correct 2B(1R(·,·),3R(·,·)).

  • Skipping the first rotation in the zig-zag case

    For keys 10, 30, 20 the new node is the left child of a right child. Rotating the grandparent alone leaves the bend in place, and the fix-up never settles: after 50 rounds of the loop it is still flipping, with 10B(·,30R(20R(·,·),·)) and red 20 under red 30. Rotate the parent first to straighten the bend, which gives 20B(10R(·,·),30R(·,·)) in one more step.

  • Stopping after one recolor

    After a recolor the grandparent has turned red, and its own parent may be red as well. If the loop does not continue from the grandparent, keys 1 to 8 end as 2B(1B(·,·),4R(3B(·,·),6R(5B(·,·),7B(·,8R(·,·))))), which the check rejects: red 6 under red 4. (Keys 1 to 5 happen to survive this bug, so a short test would miss it.) The loop must keep going until the parent is black or the root is reached.

  • Believing balanced means perfectly balanced

    A red-black tree does not keep both sides the same height; it keeps the longest path within twice the shortest. Tests that demand a perfect tree after a run of inserts will fail on correct code. Test the colour rules and the in-order sequence instead.

Where this shows up

  • Ordered maps and sets in standard libraries

    Java’s TreeMap is documented as a red-black tree, and common C++ implementations build std::map and std::set the same way. When you ask for the smallest key above x, a tree like this answers it in logarithmic time.

  • Operating-system kernels

    The Linux kernel ships a generic red-black tree that other kernel code reuses wherever it needs sorted keys with guaranteed worst-case time.

  • Interval and range bookkeeping

    Augmenting each node with extra data (for example the largest endpoint in its subtree) gives interval trees and order-statistic trees. Rotations repair that data locally, which is why the fixed small number of rotations matters.

  • Interview and teaching context

    It is the standard example of a self-balancing tree whose rules are about colour rather than height. Knowing the three insert cases, and why the new node starts red, is usually enough; reciting deletion is rarely required.

SOLVE IT YOURSELF

Solve it: keep the colours legal

A red-black tree balances with colours instead of heights. The left-leaning variant needs just three fix-up rules, applied in a fixed order — write them and let the invariants prove themselves. Python or TypeScript, running for real in your browser.

YOUR TASK

Implement the three fix-ups at the end of insert for a left-leaning red-black tree. The rotations, colour flip and validator are provided; the tests check the real invariants — root black, no red node with a red child, and every root-to-leaf path crossing the same number of black nodes.

HINTS — 6 IDEAS
  1. New nodes are always red — that way they do not change any path’s black count, so only the red-red rule can be violated.
  2. Fix-up 1 — lean left: if the right child is red and the left is not, rotate_left. This is the invariant the whole variant is named after.
  3. Fix-up 2 — balance a red pair: if the left child is red and its left child is red too, rotate_right.
  4. Fix-up 3 — split: if both children are red, flip_colors, pushing the redness up to the parent to be resolved there.
  5. The order matters. Rule 1 turns a right-leaning case into a left-leaning one so rule 2 can recognise it; rule 2 turns a red-red chain into two red siblings so rule 3 can split it. Reorder them and the tree silently goes wrong rather than crashing.
  6. The caller re-blackens the root after every insert — that is the one rule that cannot be fixed locally.
CPython · WebAssembly

Keep going

▶  Watch it explained

Red-Black Tree: Time and Space Complexity, From First Principles

Finished this one? 0 / 99 Algorithms done
NextTreap: Balance by Chance Next on the “Keeping a tree balanced” ladder · rung 4 of 5

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms