The AVL tree closed the binary search tree's worst-case-linear-chain gap by keeping every subtree's left/right heights within 1 of each other — strict, and expensive to maintain: an AVL delete can rebalance every level on the way back to the root. A red-black tree closes the same gap with a looser rule, paid for in a different currency: instead of tracking a height number per node, every node gets a color, red or black, under four rules that together bound the tree's height without ever requiring it to be as tightly balanced as AVL's. That looseness is why most language standard libraries' ordered map/set types — the ones AVL's own Where AVL trees show up section already named — pick red-black trees: fewer rotations per write, in exchange for a tree that's allowed to run somewhat deeper.
Insert a number and watch it attach as a red leaf, then watch the fixup loop repair any red-red violation it creates — every node a fixup step touches lights up, and the log names the exact case. The tree below was built by inserting 1 through 7 in ascending order, the identical sequence the AVL tree page used — a direct, checked comparison: AVL settles that sequence into a perfectly balanced tree of height 3; this page's own red-black tree settles the same sequence into height 4, one level deeper, for exactly the "looser balance" trade named above. Try continuing with 8, 9, 10 and watch the tree stay reasonably bushy rather than growing into a line. Search works like any BST search — it never changes a node's color, so a found or missed value just lights up the path it walked. Delete removes a value and, if that unbalanced the black-height, runs its own fixup loop the same way — the log names which double-black case fired at each step. Try deleting 4 from the loaded tree (an internal node with two children) to see the in-order-successor swap named in Pitfalls below, live.
A binary search tree is a valid red-black tree exactly when all four of these hold at once:
null for that and treats null as
black wherever a color is needed, rather than allocating real sentinel nodes.)2·log₂(n+1) — looser than AVL's roughly 1.45·log₂(n), but still
logarithmic, which is the only guarantee either structure actually needs.Insertion starts as an ordinary BST insert — walk down by comparison, attach a new node where you
fall off the tree — with one fixed choice: the new node is always colored red. Red,
not black, because a new red leaf can only ever threaten the no-red-red rule (fixable locally); a new
black leaf would silently break the equal-black-height rule on every path through it, a much
worse problem with no local fix. Attaching a red leaf leaves every rule intact except possibly one:
if the new node's parent is also red, two reds now sit in a row. The fixup loop repairs exactly that,
walking up one grandparent at a time. At each step, call the new problem node z. Whichever
side z's parent is on, check z's uncle (the grandparent's
other child):
z's parent and uncle black, and
the grandparent red. No rotation. This can't break the black-height rule (every path through the
grandparent still crosses the same number of black nodes as before — two of its neighbors went
black, it went red), but the grandparent turning red might now conflict with its own
parent. Set z to the grandparent and check again — this is the one case that can
cascade more than one level up a single insert, something an AVL insert never needs (see Pitfalls).z is an "inner" grandchild
(a triangle shape: z is a right child but its parent is a left child, or the mirror).
One rotation at z's parent turns this into the straight-line shape Case 3 expects,
then falls through to it.z is an "outer" grandchild
(a straight line: both left children or both right children). Recolor the parent black and the
grandparent red, then rotate once at the grandparent. This always ends the loop — no ancestor further
up ever sees its black-height change, the same "one fix and done" reasoning
AVL's own rotations rely on, just reached by a different
route (case 1 can cascade; case 3 never does).Case 2 -> 3 (parent is a left child, z is its right child — the mirror handles a right-child parent):
gp(black) gp(black) p(black)
/ \ / \ / \
p(red) u(black) --> z(red) u(black) --> z(red) gp(red)
\ / \
z(red) p(red) u(black)
(left-rotate at p, z takes p's place) (recolor p black / gp red, right-rotate at gp)After the loop ends (or never starts, if the parent was already black), the root is unconditionally forced back to black — covers the case where the tree was empty (the new node became the root, and the root must always be black) and the case where a Case-1 recolor pushed red all the way up to the root itself.
Deletion starts as an ordinary BST delete: splice out a leaf directly, splice out a one-child node by promoting its child, or — for a node with two children — swap in the in-order successor (the minimum of the right subtree) and delete that instead, since it's guaranteed to have at most one child. The value moves; the physical node object holding it doesn't. Removing a red node never breaks any rule (no path's black-height changes), so that case needs no fixup at all. The hard case is removing a black node: every path that ran through it is now one black node short, and unlike insert's local red-red violation, this "missing black" can't be seen by looking at any single node — the standard fix models it as an imaginary extra unit of blackness (a "double-black" token) sitting where the removed node used to be, even when that spot is now an empty NIL child, and walks it up the tree resolving it one step at a time by examining the current node's sibling:
If the loop exits because the current node turned red rather than through Case 4's rotation (Case 2 can end this way), that node is unconditionally recolored black afterward — absorbing the double-black token by spending the "this node is red" slack it was already carrying, rather than firing a fifth named case. Try clearing and reinserting 1 through 7, then deleting 1, to see this live: it fires Case 1 (sibling 4 is red) then Case 2 (new sibling 3 is black with two black children, pushing the double-black up to 2) — and stops there, because 2 is red after Case 1's own recolor, not through a fourth case. Deleting 4 from that same loaded tree instead shows the two-children swap: 4 has two children, so its in-order successor 5 physically moves into 4's slot before 4 is discarded (named in the log, and in Pitfalls below).
const RED = 'red', BLACK = 'black';
function isRed(node) { return node !== null && node.color === RED; }
class RedBlackTree {
#root = null;
#rotateLeft(x) {
const y = x.right;
x.right = y.left;
if (y.left !== null) y.left.parent = x;
y.parent = x.parent;
if (x.parent === null) this.#root = y;
else if (x === x.parent.left) x.parent.left = y;
else x.parent.right = y;
y.left = x;
x.parent = y;
}
#rotateRight(x) {
const y = x.left;
x.left = y.right;
if (y.right !== null) y.right.parent = x;
y.parent = x.parent;
if (x.parent === null) this.#root = y;
else if (x === x.parent.right) x.parent.right = y;
else x.parent.left = y;
y.right = x;
x.parent = y;
}
insert(value) {
let y = null, x = this.#root;
while (x !== null) {
if (value === x.value) return; // duplicates ignored
y = x;
x = value < x.value ? x.left : x.right;
}
const z = { value, color: RED, left: null, right: null, parent: y };
if (y === null) this.#root = z;
else if (value < y.value) y.left = z;
else y.right = z;
this.#insertFixup(z);
}
#insertFixup(z) {
while (isRed(z.parent)) {
const gp = z.parent.parent;
if (z.parent === gp.left) {
const uncle = gp.right;
if (isRed(uncle)) { // Case 1
z.parent.color = BLACK; uncle.color = BLACK; gp.color = RED;
z = gp;
} else {
if (z === z.parent.right) { z = z.parent; this.#rotateLeft(z); } // Case 2 -> 3
z.parent.color = BLACK; gp.color = RED; // Case 3
this.#rotateRight(gp);
}
} else { // mirror image
const uncle = gp.left;
if (isRed(uncle)) {
z.parent.color = BLACK; uncle.color = BLACK; gp.color = RED;
z = gp;
} else {
if (z === z.parent.left) { z = z.parent; this.#rotateRight(z); }
z.parent.color = BLACK; gp.color = RED;
this.#rotateLeft(gp);
}
}
}
this.#root.color = BLACK;
}
#transplant(u, v) {
if (u.parent === null) this.#root = v;
else if (u === u.parent.left) u.parent.left = v;
else u.parent.right = v;
if (v !== null) v.parent = u.parent;
}
#findNode(value) {
let x = this.#root;
while (x !== null) {
if (value === x.value) return x;
x = value < x.value ? x.left : x.right;
}
return null;
}
delete(value) {
const z = this.#findNode(value);
if (z === null) return false;
let y = z, yOriginalColor = y.color, x, xParent;
if (z.left === null) {
x = z.right; xParent = z.parent;
this.#transplant(z, z.right);
} else if (z.right === null) {
x = z.left; xParent = z.parent;
this.#transplant(z, z.left);
} else {
y = z.right;
while (y.left !== null) y = y.left; // in-order successor
yOriginalColor = y.color;
x = y.right;
if (y.parent === z) {
xParent = y;
} else {
xParent = y.parent;
this.#transplant(y, y.right);
y.right = z.right; y.right.parent = y;
}
this.#transplant(z, y);
y.left = z.left; y.left.parent = y;
y.color = z.color;
}
if (yOriginalColor === BLACK) this.#deleteFixup(x, xParent);
return true;
}
#deleteFixup(x, xParent) {
while (x !== this.#root && !isRed(x)) {
if (x === xParent.left) {
let w = xParent.right;
if (isRed(w)) { // Case 1
w.color = BLACK; xParent.color = RED;
this.#rotateLeft(xParent);
w = xParent.right;
}
if (!isRed(w.left) && !isRed(w.right)) { // Case 2
w.color = RED;
x = xParent; xParent = x.parent;
} else {
if (!isRed(w.right)) { // Case 3 -> 4
w.left.color = BLACK; w.color = RED;
this.#rotateRight(w);
w = xParent.right;
}
w.color = xParent.color; xParent.color = BLACK; // Case 4
if (w.right !== null) w.right.color = BLACK;
this.#rotateLeft(xParent);
x = this.#root;
}
} else { // mirror image
let w = xParent.left;
if (isRed(w)) {
w.color = BLACK; xParent.color = RED;
this.#rotateRight(xParent);
w = xParent.left;
}
if (!isRed(w.right) && !isRed(w.left)) {
w.color = RED;
x = xParent; xParent = x.parent;
} else {
if (!isRed(w.left)) {
w.right.color = BLACK; w.color = RED;
this.#rotateLeft(w);
w = xParent.left;
}
w.color = xParent.color; xParent.color = BLACK;
if (w.left !== null) w.left.color = BLACK;
this.#rotateRight(xParent);
x = this.#root;
}
}
}
if (x !== null) x.color = BLACK;
}
contains(value) {
let x = this.#root;
while (x !== null) {
if (value === x.value) return true;
x = value < x.value ? x.left : x.right;
}
return false;
}
}The interactive demo above uses equivalent insertRB/searchRB/deleteRB
functions with extra bookkeeping to record the comparison path and which fixup case(s) fired, purely to
drive the highlighting and log text — the algorithm is identical, including the parent pointers, which
this page needs and the AVL/BST pages didn't: finding a node's uncle/grandparent (insert) or sibling
(delete) requires walking up the tree, not just down, and a purely recursive
rebalance-on-unwind (what AVL's own reference implementation uses) can't see two ancestor levels — or a
sibling — at once mid-recursion the way these fixups need to. Delete's own tricky bit, not shared with
insert: the "double-black" token can sit on an empty null child, which has no parent
pointer of its own — the reference implementation (and the shipped demo) thread that parent through
deleteFixup as an explicit second argument instead, rather than allocating a real sentinel
node.
Verified with 20,000 randomized sequences (40 mixed inserts/deletes each, tracking a live set of
present values so deletes target a real mix of leaves/one-child/two-child nodes, followed by a full
drain that deletes every remaining value in random order) against a plain JavaScript Set as
a reference model — 978,240 total operations checked, after every single one, not just at the
end: the no-red-red rule, equal black-height on every path, the root is always black and has a null
parent, parent pointers stay consistent, the BST ordering property, that contains/
searchRB agrees with the Set, and that the tree is fully empty (null
root) after every drain finishes. Plus explicit edge cases (deleting from an empty tree, deleting the only
node, deleting a missing value, both the y.parent === z and deeper-successor branches of the
two-children case) and an ascending-then-descending 1-to-200 insert/delete round trip. Insert alone was
separately re-checked against an ascending 1-to-2000 run (the classic worst case for a plain, unbalanced
BST), confirming the tree's height stays at 19 — comfortably under the 2·log₂(n+1) ≈ 21.9
bound, never anywhere near 2000. Re-verified by extracting the exact shipped insertRB/
deleteRB functions out of the HTML and re-running an equivalent 978,240-operation pass
directly against them (zero mismatches), plus a real click-driven fake-DOM harness confirming the two
worked examples named above (deleting 1 from the loaded tree logs exactly "Case 1... then Case 2" and
highlights nodes 4/2/3; deleting 4 logs the successor-5 swap and "no fixup needed") and that deleting a
missing value, an empty-input delete, and inserting-then-deleting the only value down to an empty tree
all behave as claimed. The randomized-trial checker was itself self-tested first — a deliberately
broken copy (Case 2's sibling recolor removed) was confirmed to fail on the very first trial with an
"unequal black-height" error before trusting a clean run on the real code, the same standing discipline
recent sessions' link/anchor crawlers have followed. See /tmp/rbdel/ref.js,
/tmp/rbdel/test_ref.js, /tmp/rbdel/extracted.js,
/tmp/rbdel/test_extracted.js, /tmp/rbdel/fake_dom.js, and
/tmp/rbdel/click_harness.js, scratch, not committed.
A single insert's recoloring can cascade more than one level up — something an AVL insert
never needs. AVL's rotation restores the subtree's original height exactly, so no ancestor
further up is ever affected; one fix and the insert is done. Red-black's Case 1 has no such
guarantee — recoloring the grandparent red can itself violate the no-red-red rule one level higher,
requiring another full pass of the fixup loop. Checked, not just asserted: inserting
7, 4, 28, 10, 24, 9, 11, 19, 16, 18 in that order into an empty tree, the final
insert(18) triggers two consecutive Case-1 recolors (first from 18's own
grandparent, then again from the next grandparent up) and reaches the root without ever rotating —
zero rotations, two separate levels recolored, from one insert. Run it in the demo above (clear first,
then insert that exact sequence) to see it live; the log names both Case-1 steps in order.
In the two-children case, the color that decides whether a fixup runs belongs to the
successor, not to the node the caller asked to delete — and by the time that decision is made,
the successor's own color field has already been overwritten with the deleted node's color
(so its slot in the tree keeps the right look), which means that original color has to be captured in a
local variable before the overwrite, not read from the node afterward. Get this backwards — read
it from the wrong node, or after the overwrite — and the bug doesn't just misbehave, it can crash
outright: a from-scratch variant of the reference implementation that captures z's own color
instead of the successor's own original color, run against the tiny sequence insert 3, insert 2,
insert 0, delete 2 (four operations, checked directly, not searched for), throws a null-pointer
exception inside its own fixup loop — it wrongly decides a fixup is needed when the actual removed color
was red, and the fixup loop then dereferences a sibling that doesn't exist for the case it thinks it's in.
The correct implementation removes the same four operations cleanly, needing no fixup at all, and ends
with root 3 (black), left child 0 (red), no right child.
Looser balance is a real, measured trade, not just a claim. Inserting 1 through
2000 in ascending order — the classic worst case for a plain BST — produces an
AVL tree of height 11 but a red-black tree of height 19,
both checked against their own shipped code, not estimated. Both are still O(log n) —
neither comes close to the 2000-deep line a plain BST would produce on the same input — but AVL's
extra rotations buy a measurably shallower tree, which is exactly the "cheaper writes for a somewhat
deeper tree" trade named in the intro above, made concrete instead of asserted.
std::map/
std::set, Java's TreeMap/TreeSet, and the Linux kernel's
internal rbtree are all red-black trees — the most common concrete choice behind the abstract
"self-balancing BST" idea this page and AVL tree both
introduce.O(log n), not the fastest possible O(log n).O(log n) nodes per operation, which
keeps the cost of copying a modified path bounded the same way it keeps rotation cost bounded.Time: insert, search/contains, and
delete are all O(log n), guaranteed — the same class of guarantee AVL tree offers, just with a looser constant
(2·log₂(n+1) vs AVL's roughly 1.45·log₂(n)). Both fixup loops (insert's and
delete's) only ever walk up one root-to-leaf path, however many cases either passes through. Each fixup
step (recolor or rotate) is O(1). Space:
O(n) for n nodes — the same two child pointers a plain BST spends, plus one
parent pointer and one color bit, marginally more per-node bookkeeping than AVL's cached height integer,
in exchange for cheaper rebalancing.
See Choosing a Search Tree for the full read-heavy-vs-write-heavy tradeoff against AVL, plus where splay and B-tree fit in.