Red-Black Trees

By the end of this lesson you will be able to state and check all 5 red-black properties on any colored binary tree; trace leftRotate/rightRotate, transplant, insert + insertFixup (all 3 cases and their mirrors), and delete + deleteFixup (all 4 cases and their mirrors) line by line; explain WHY a red-black tree's height is always ≤ 2 lg(n+1); implement the whole thing in null-safe Dart (and understand the one place null safety forces a genuine design change from the pseudocode); and compare red-black trees against AVL trees and treaps.

This lesson assumes you already have a plain binary search tree (BST) under your belt — searching, inserting, deleting, finding the minimum and maximum, in-order walks, and the fact that an UNBALANCED BST can degrade to a height-n linked list (insert 1,2,3,4,5,... in order and every node just gets a right child). If any of that is unfamiliar, read Binary Search Trees first. This lesson answers the question that lesson leaves open: how do we keep a BST's height at O(lg n), no matter what order keys arrive in?

Hide the small dark NIL sentinel squares in every tree drawing below (they're shown by default so you can see exactly where the shared sentinel nil sits)

1. The 5 red-black properties & black-height

A plain BST has NO rule stopping it from becoming a lopsided chain. A red-black tree is an ordinary BST with one extra bit of information per node — a colour, RED or BLACK — plus 5 rules about how colours may be arranged. Think of the rules as building-code regulations: as long as every node obeys them, the building (tree) simply CANNOT lean over past a certain angle (height), no matter how it was built up floor by floor (key by key).

In the pseudocode every "missing" child, and the parent of the root, is one single, SHARED sentinel node called nil, coloured BLACK, instead of a null/empty pointer. This is a convenience trick: a line like x.left.color or x.parent never needs a null-check, because nil is a real (if fake) node object. Every nil is drawn below as a small dark square.

A binary search tree is red-black if every node satisfies these 5 properties:

Every node is either RED or BLACK.
The root is BLACK.
Every leaf (every nil) is BLACK.
If a node is RED, both its children are BLACK (equivalently: no two REDs in a row on any path).
For each node, all simple paths from that node down to descendant leaves contain the SAME number of BLACK nodes.

Property 5 lets us define, for any node x, its black-height bh(x): the number of BLACK nodes on any path from x DOWN to a leaf, NOT counting x itself but counting the leaf. It's well-defined precisely because property 5 guarantees every such path gives the same count.

In Dart. The shared sentinel nil becomes Dart's null (and the pseudocode's parent field stays parent); a tree is pointer-based, so there is no index shift to worry about here. A missing child counts as black, which is what _isBlack(null) == true says:

All five properties as code. checkRedBlackProperties returns one message per broken property (property 1 holds by construction of the RBColor enum, property 3 is the null rule above, properties 2, 4, 5 and the BST order are tested explicitly):

Black-height as code. The definition “black nodes on a path down to a leaf, not counting x, counting the leaf” is one line of recursion, and property 5 is exactly the statement that going down the left or the right gives the same number:

Input size → what is feasible. Checking all five properties is one O(n) pass: n = 10⁶ nodes is 10⁶ steps (instant). Recomputing bh from scratch at every node would be O(n⋅h), and on a lopsided tree up to n² = 10¹² steps, so compute it once bottom-up.

The height bound (previewed here, proved in full in §6): a red-black tree with n internal (real, non-sentinel) nodes has height at most 2 lg(n+1). Properties 4+5 are doing all the work: property 4 forces at least HALF of the nodes on any root-to-leaf path to be black (no two reds touch), and property 5 makes every such path have the same black count — together this caps how much longer any one path can be than any other.

Memorise properties 2, 4 and 5 above everything else — every fixup case in this lesson exists ONLY to restore one of those three after an insert or delete temporarily breaks it. (Properties 1 and 3 are essentially housekeeping and are never actually at risk.)

2. Rotations: leftRotate / rightRotate

A rotation is a local, O(1), pointer-only restructuring that changes the SHAPE of a tree without breaking the BST property (an in-order walk gives the exact same sorted sequence before and after). Picture a mobile hanging from the ceiling: leftRotate(t, x) takes node x and its right child y and swaps who's on top — y rises to take x's old spot, and x drops down to become y's LEFT child. The only subtree that has to move is y's old left subtree (call it β), which slides over to become x's new right subtree — it still belongs between x and y in sorted order, so that's exactly where it has to go.

The pseudocode for leftRotate(t, x) (it requires x.right ≠ nil):

All the rotation examples below share one demo tree, built by inserting [20,10,30,25,35] (its actual shape after insert's fixups: root 20 with children 10 and 30, and 30 has children 25 and 35 — so every one of 20 and 30 has BOTH a left and a right child, letting us rotate either direction at either node).

Example 1 — rotate at the root (x = 20):

Example 2 — rotate at a non-root node (x = 30):

Example 3 — your own node (pick 20 or 30 — the only nodes with a right child on this demo tree):

rightRotate(t, y) is the exact mirror image (it requires y.left ≠ nil) — swap every "left" with "right" and vice versa. Same demo tree:

Example 1 — rotate at a non-root node (y = 30):

Example 2 — rotate at the root (y = 20):

Example 3 — your own node (pick 20 or 30 — the only nodes with a left child on this demo tree):

A rotation NEVER looks at colours and NEVER by itself fixes a red-black violation — it only rearranges pointers. Every fixup case that calls a rotation ALSO does some recolouring around it; the rotation alone would leave the tree structurally different but still red-black-invalid.

Dart implementation. Because rotations are pure pointer surgery, there is no "index shift" the way an array-based procedure would need — the one real adaptation is the shared, mutable nil sentinel becoming Dart's ordinary null: every RBNode<K>? field can simply BE null, and a small helper _isBlack(node) treats "null" as black so the property logic still reads the same:

The mirror image, rightRotate (swap every left and right):

Input size → what is feasible. A rotation rewires at most 6 pointers whatever the tree size, so it costs O(1) for n = 10 or n = 10⁹ alike; the work in a fixup is the number of rotations (at most 2 per insert, 3 per delete, see the bounds below), never the size of the subtree.

Rotation is O(1) time, changes exactly O(1) pointers, and always preserves the BST property. It performs exactly 6 pointer assignments (lines 2, 4, 5, one of 7/9/11, 12 and 13) and moves only three subtrees' attachment points: x, y and β.

3. transplant

transplant(t, u, v) answers one narrow question: "splice subtree v into the exact spot where subtree u used to hang, as seen from u's OLD parent." It does NOT touch v's children — the caller (delete, §5) is responsible for reattaching whatever u's own children were, if it wants to keep them.

In Dart. Same seven steps; the only change is the guard if (v != null) in place of the unconditional v.parent ← u.parent (null has no fields, so deleteFixup gets the logical parent as an extra argument instead). minimum, which delete uses to find a node's in-order successor, is the left-spine walk right below it:

Input size → what is feasible. transplant is O(1) for any n. minimum walks one left spine, at most the height h ≤ 2 lg(n+1): about 40 steps for n = 10⁶.

The pseudocode writes v.parent ← u.parent unconditionally, EVEN when v is the sentinel nil — because nil is one shared mutable object, this is how deleteFixup later finds "the parent of x" via x.parent even when x turned out to be the sentinel. In null-safe Dart, v can simply be null, and you cannot write null.parent = ... — so our Dart port only sets v.parent when v is non-null, and instead threads the logical parent through as an explicit extra parameter wherever it's needed (see §5).

Example 1 — replacing the root (u = t.root, so line 1's u.parent = nil test fires):

Example 2 — replacing a LEFT child (u is a left child of its parent, so line 3's u = u.parent.left test is true):

Example 3 — your own u and v (format keys | uKey,side, e.g. 20,10,30,5,15,25,35 | 30,right transplants u = the node with key uKey with v = u's left or right child — side may point at an EMPTY child, which is exactly the "v is nil" case the pitfall above describes):

transplant is O(1) and makes just 2 pointer assignments (the parent's child link, and v's parent). You'll see it fire literally every time delete runs (§5) — it's the "unhook and rehook" step underneath every deletion.

4. Insertion: insert & insertFixup

Step 1 is nothing new: walk down from the root exactly like an ordinary BST insert, and hang the new node z off whichever leaf spot it belongs at. Step 2 is the new part: always colour the brand-new node RED, then call a repair procedure. Colouring it red (rather than black) means AT MOST ONE property can be violated — property 2 (if z is the root) or property 4 (if z's parent is also red) — never property 5, since a red leaf changes no path's BLACK count at all (interview question 9 below tests exactly this).

insert(t, z) — the plain-BST-insert part, plus colouring z red and handing off to the fixer:

insertFixup(t, z) — repeatedly restores properties 2 and 4 while they're broken. It only ever needs to look at z's parent, grandparent, and uncle (the grandparent's OTHER child):

Input size → what is feasible. n = 10⁶ inserts ≈ 10⁶×(2 lg 10⁶ ≈ 40) = 4·10⁷ steps, well under a second, whatever the key order. Feed a plain BST the same sorted keys and it needs n²/2 = 5·10¹¹ steps.

The loop invariant (true at the top of every iteration): (a) z is red; (b) if z.parent is the root, z.parent is black; (c) at most ONE red-black violation exists at a time — either property 2 (if z is a red root) or property 4 (if both z and z.parent are red).

Case 1 (uncle y is RED): recolour z.parent and y BLACK, grandparent RED, then move z up two levels to the grandparent and keep looping. No rotation. The violation just moved UP the tree (and possibly disappeared).
Case 2 (uncle y is BLACK, z is an "inner" child — e.g. a right child while its parent is a left child): one rotation converts this into Case 3. z is reassigned to its old parent first.
Case 3 (uncle y is BLACK, z is an "outer" child): recolour and rotate once — this ALWAYS ends the loop (the new subtree root is black, so property 4 can't still be violated above it).

Each of these cases has a mirror image when z.parent is a RIGHT child of the grandparent instead of a left child. The pseudocode writes the mirror as a single comment row (lines 16–17) rather than repeating the whole body, so in the animations below a mirror step is labelled with the SAME line numbers as its non-mirror twin, just describing the opposite side.

How to read the animations below: the code panel inside each player is insertFixup, so only fixup steps highlight a row. The first steps of every insert (the BST walk and hanging the red leaf) are insert lines 1–19 — their captions say “insert line N” and refer to the insert panel printed above, with no row highlighted.

Example 1 — Case 1 in isolation (insert 20, then 10 and 30 as its children, then 5 — 5's uncle 30 is red):

Example 2 — Case 2 → Case 3 (insert 20, then 10, then 15 — 15 is an "inner" child, so it first rotates into an "outer" position):

Example 3 — your own sequence (comma-separated distinct integers, at most 12 so the picture stays readable; the default demonstrates a Case-1 MIRROR):

A very common bug: after Case 2's rotation, forgetting that z itself changed (line 11, z ← z.parent) — every line after that must use the NEW z, not the node you started the iteration with, or Case 3's recolouring touches the wrong nodes.

Dart implementation. This procedure is almost a direct transcription — the only adaptation is using _isRed(node)/_isBlack(node) helpers everywhere the pseudocode writes x.color = RED, since node may be null (never a crash, because _isBlack(null) == true by definition, exactly matching "nil is always black"):

insertFixup in Dart, with the pseudocode's line numbers in the comments. The three cases are marked CASE 1, CASE 2, CASE 3; the else half is the mirror image (lines 16–17). onCase is a test hook that reports which case ran:

Each case, checked. One tiny tree per case and per mirror, asserting the case that fires (case 3 always ends the loop with a black subtree root over two red children):

Analysis: the loop only repeats via Case 1, and each Case-1 iteration moves z two levels UP a tree of height O(lg n), so the loop runs O(lg n) times. Cases 2 and 3 always terminate the loop immediately. Total: O(lg n) time, and at most 2 rotations ever, no matter how many Case-1 iterations happen.

insert: O(lg n) time, ≤ 2 rotations total, exactly 1 recolouring pass per Case-1 step, always ends with the root forced black (line 18) — restoring property 2 even if it was the ONLY thing broken.

5. Deletion: delete & deleteFixup

Deletion is harder than insertion for one reason: you might have to remove a BLACK node, and removing a black node from a path makes that path "short" a black node compared to every other path — a property-5 violation. The trick is to imagine the removed black colour as an "extra black" token that gets pushed down onto whichever node x moved into the gap, making x temporarily doubly black (if it was already black) or red-and-black (if it was red) — a fictitious colour that exists ONLY inside the fixup procedure, purely as housekeeping, and is never actually drawn.

delete(t, z) — mirrors ordinary BST delete (splice out a ≤1-child node directly; for a 2-child node, splice in its in-order successor instead) but tracks y (the node that actually gets removed/moved), y's ORIGINAL colour (before any recolouring), and x (whatever moves into y's old spot — possibly the sentinel):

If y's original colour was RED, removing it can't violate anything (a red node is never load-bearing for property 4 or 5) — no fixup needed. If it was BLACK, deleteFixup(t, x) repairs the extra-black:

Inside the loop, w is always x's sibling. The 4 cases (mirrored when x is a right child instead of a left child):

Case 1 (w is RED): w can't actually be a solution by itself (it must have black children, by property 4, since it's red) — recolour w black / x.parent red and rotate, which converts the sibling to a BLACK one, falling through into Case 2, 3 or 4.
Case 2 (w BLACK, BOTH of w's children BLACK): w can safely turn RED — this removes one black from w's subtree, balancing it against x's side, and pushes the "extra black" up to x.parent. Move x up and keep looping (this is the only case that repeats the loop).
Case 3 (w BLACK, w's far child BLACK, near child RED): a rotation at w converts this into Case 4 by moving a red node to become w's new far child.
Case 4 (w BLACK, w's far child RED): one rotation + recolour absorbs the extra black completely and sets x ← t.root, ending the loop for good. This is the only case that fully resolves things without depending on anything above it.

How to read the animations below: the code panel inside each player is deleteFixup, so only fixup steps highlight a row. The steps before it (finding x, y and splicing) are delete lines 1–24 — their captions say “delete line N” and refer to the delete panel printed above, with no row highlighted. The starting tree is built off-screen by insert.

Example 1 — Case 2 in isolation:

Example 2 — Case 1 → Case 4:

Example 3 — your own tree and deletions (format insert-keys | delete-keys, e.g. 53,37,36,67,91,12,58,11|91 — the default below walks Case 3 → Case 4):

After Case 1's rotation, w MUST be reassigned (line 8: w ← x.parent.right) before the following cases inspect it — the OLD w is no longer x's sibling after the rotation. Forgetting this reassignment is the single most common deleteFixup bug (see also the debugging question in the interview bank).

Dart implementation. This is where null safety forces a REAL design change, not just a helper function. The pseudocode relies on the sentinel's mutable parent field so that even when x IS nil, the code can still ask "what is x's parent?". A null x in Dart has no fields at all. The idiomatic fix: thread the logical parent of x through explicitly, as its own parameter (xParent), updated at every point where the pseudocode would update nil.parent:

deleteFixup in Dart. xParent plays the role of x.parent. The four cases are marked CASE 1 to CASE 4, with the pseudocode's line numbers (1–25) in the comments; the else half is the mirror image (lines 23–24):

Each case, checked. Small deletions that trigger the cases, asserting which ones fire:

Analysis: the loop only repeats via Case 2, moving x up a tree of height O(lg n), so O(lg n) iterations. Cases 1, 3 and 4 all terminate in O(1) further work. Total: O(lg n) time, and at most 3 rotations ever (one in Case 1, at most one more in Case 3, one final one in Case 4).

Input size → what is feasible. n = 10⁶ deletes ≈ 4·10⁷ steps (about 40 per delete). The rotation bounds are checked in code on 24,000 seeded random operations, counting the rotations of every single insert and delete:

delete: O(lg n) time, ≤ 3 rotations total. The whole "extra black" idea exists purely so the loop can be expressed WITHOUT special-casing "did we just delete the root" or "how many levels up is the violation" — it's housekeeping, not a real colour.

6. The height bound: height ≤ 2 lg(n+1)

The proof has two steps. Step 1 (induction on height): any subtree rooted at x has AT LEAST 2^bh(x) − 1 internal nodes (a black-height-k tree contains at least as many nodes as a PERFECT binary tree of black-height k, because every extra red layer can only ADD nodes, never remove the minimum count). Step 2: property 4 forces at least half of any root-to-leaf path's nodes to be black, so bh(root) ≥ h/2 where h is the tree's height. Combine: n ≥ 2^(h/2) − 1, and solving for h gives h ≤ 2 lg(n+1).

Watch the bound hold as a tree grows one key at a time (ascending insertion — the exact input order that turns a PLAIN BST into a straight line of height n — is used on purpose here, to show a red-black tree refuses to degrade even in that "worst case for a naive BST"):

The bound as code. Both proof steps and the final bound are checked on a real tree (the function returns every violation it finds, an empty list means the bound holds): step 1 is internalNodes(x) ≥ (1 << bh(x)) − 1 at every node, step 2 is h ≤ 2·bh(root), and the bound is heightBound(n) = 2·lg(n+1) with lg(n+1) = ln(n+1)/ln 2 (1 << k is Dart for 2^k):

Input size → what is feasible. n = 15 → height ≤ 8; n = 10⁶ → height ≤ 39; n = 10⁹ → height ≤ 59. So even a billion keys are reached in at most 59 pointer hops.

The MINIMUM possible height for n nodes (any binary tree, balanced or not) is ⌈lg(n+1)⌉. So a red-black tree's actual height always sits somewhere in [lg(n+1), 2lg(n+1)] — at most a factor of 2 away from a perfectly balanced tree, GUARANTEED, for every possible sequence of insertions and deletions, with no assumptions about input order at all.

Dart already ships an ordered map. dart:collection's SplayTreeMap (lesson d27) is the built-in sorted map and set. It is a splay tree, not a red-black tree: it gives O(lg n) amortized time (a single operation can cost O(n), the average over many cannot), where a red-black tree guarantees O(lg n) for every single operation. Use it first in real code; build your own red-black tree when you need the worst-case guarantee or want to augment nodes (see Augmenting Data Structures).

Every one of search, minimum, maximum, successor and predecessor (unchanged from the plain BST, just re-using nil) is automatically O(lg n) the moment height is bounded — that's the entire payoff of this lesson's fixup machinery.

7. Compare: AVL trees & treaps

AVL trees (Adel'son-Vel'skiĭ & Landis, 1962) use a STRICTER balance rule — at every single node, |height(left) − height(right)| ≤ 1, tracked with an explicit height field instead of a colour bit. Whenever an insertion makes some node's balance factor hit ±2, one of 4 rotation patterns (single LL/RR, or double LR/RL) restores it, using AT MOST O(1) rotations per insertion (fewer than red-black's already-small ≤2).

Watch an AVL insertion trigger a rotation (try 30,10,20 for a "double" LR case, or the default 30,20,10 for a "single" LL case):

Because AVL's balance constraint is TIGHTER than red-black's, an AVL tree's height is provably closer to the perfect-balance minimum: an AVL tree of height h has at least F_h+2 − 1 nodes (Fibonacci numbers), giving height ≤ 1.4405 lg(n+2) — noticeably tighter than red-black's 2 lg(n+1). The trade-off: AVL trees do MORE work (and sometimes more rotations) per DELETE to maintain that tighter bound, which is exactly why libraries doing many more updates than lookups (Linux's CFS scheduler, C++ std::map, Java's TreeMap) usually pick red-black trees instead — looser balance, cheaper maintenance, still O(lg n) for everything.

Input size → what is feasible. AVL and treap inserts are O(lg n) like red-black ones: n = 2·10⁵ keys ≈ 3.5·10⁶ steps. The AVL recursion is at most 1.44 lg n ≈ 26 frames deep, a treap about 2 ln n ≈ 24 frames on average.

Treaps (Seidel & Aragon): give every node an independently random priority in addition to its key. Keys must satisfy the BST property; priorities must satisfy the min-heap property (every child's priority is ≥ its parent's) — together these two constraints pin down a UNIQUE tree shape for any given set of (key, priority) pairs. Treap insert: do an ordinary BST insert by key, then rotate the new node UP past its parent for as long as it violates the heap order (its priority is smaller than its parent's).

Why treaps are balanced: because the shape is fixed by the priorities, a treap built from n independent random priorities has the same shape distribution as a plain BST built by inserting the SAME keys in a uniformly random order, and a randomly-built BST has expected height Θ(lg n). Here is the picture behind that: key j is an ancestor of key i exactly when j has the smallest priority among all keys from i to j, which happens with probability 1/(|i−j|+1). Adding that up over all j gives an expected depth near 2 ln n. The same style of argument shows an insert needs only a small CONSTANT number of rotations on average (the number does not grow with n).

The constant, measured: one more insert into 20,000 random treaps of 50 keys, rotations counted as (depth as a plain-BST leaf) − (final depth); the average stays under 2:

	Red-black tree	AVL tree	Treap
Balance rule	colour invariants (properties 1-5)	\|height(L)−height(R)\| ≤ 1 everywhere	random priority, min-heap order
Height bound	≤ 2 lg(n+1), worst case	≤ 1.44 lg(n+2), worst case	Θ(lg n), EXPECTED (not worst case)
Rotations / insert	≤ 2, worst case	≤ O(1) (1 single or 1 double), worst case	< 2, expected
Rotations / delete	≤ 3, worst case	O(lg n) possible, worst case	O(height), to rotate the node down to a leaf
Extra data per node	1 colour bit	height (or balance factor)	1 random priority
Guarantee holds against	ANY adversary (deterministic structure)	ANY adversary (deterministic structure)	any adversary who can't see the random priorities

Quiz

Interview questions

Cheat sheet

Operation	Time	Space	Notes
search / min / max / successor / predecessor	O(lg n)	O(1)	unchanged from plain BST, just uses nil
leftRotate / rightRotate	O(1)	O(1)	never fixes colour, only shape; 6 pointer assignments
transplant	O(1)	O(1)	splices v into u's old spot; caller reattaches u's children
insert	O(lg n)	O(1)	≤ 2 rotations total; new node always starts RED
delete	O(lg n)	O(1)	≤ 3 rotations total; fixup only runs if removed colour was BLACK
Height, worst case	≤ 2 lg(n+1) — the height bound of §6
AVL tree	O(lg n) all ops	O(1)/node extra	tighter height ≤ 1.44 lg(n+2); O(1) rotations/insert
Treap	O(lg n) expected	O(1)/node extra	Θ(lg n) expected height; < 2 expected rotations/insert
Not balanced (plain BST)	O(n) worst case	—	degrades to a chain on sorted input — the whole reason this lesson exists