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?
New nodes are inserted red. Adding a red node leaves every root-to-leaf path’s black count unchanged, so the only rule that can break is "no red under red" — a much easier violation to fix than a black-height imbalance.
2. When the new node’s uncle is red, how is the violation fixed?
A red uncle means a pure recoloring works: parent and uncle become black, grandparent becomes red. This can create a new red-red at the grandparent, so the fix-up repeats one level up — but no rotation is needed.
3. What do the red-black rules guarantee about the tree’s height?
No two reds in a row plus equal black-height on all paths means the longest path (alternating colors) is at most twice the shortest (all black). That bounds the height at about 2·log₂(n+1), so all operations are O(log n).
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.
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
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.
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.
Fix-up 2 — balance a red pair: if the left child is red and its left child is red too, rotate_right.
Fix-up 3 — split: if both children are red, flip_colors, pushing the redness up to the parent to be resolved there.
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.
The caller re-blackens the root after every insert — that is the one rule that cannot be fixed locally.