Vibe Engines Learn
Algorithms · Data Structures

Balance in Two Colors.

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.

Keep going

Algorithm

AVL Tree →
Algorithm

Binary Search Tree →
Algorithm

Treap →
Roadmap

The DSA Roadmap →
Finished this one? 0 / 98 Algorithms done

Explore the topic

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

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →