Red-black trees

A binary search tree answers lookups, ordered queries and ranges along a single path from the root, but the length of that path depends on the order in which the keys arrived: sorted input turns it into a list. A red-black tree is a search tree that colours every node red or black and keeps five simple rules about the colours, and those rules alone force the height to stay below 2 log2(n + 1) whatever the order of the keys. Every insertion repairs the rules with at most two rotations and every deletion with at most three, so search, insertion and deletion all take O(log n) time in the worst case. That guarantee is why Java's TreeMap, C++'s std::map and the Linux kernel's scheduler and timers are built on red-black trees. This page defines the five properties, proves the height bound, derives insertion and deletion case by case with their mirror images, shows the 2-3-4 trees that red-black trees encode and the left-leaning variant, measures heights and rotations against the theory and against an unbalanced search tree, and compares the tree with sortedcontainers. Afterwards you will be able to trace any insertion or deletion by hand naming every case, implement and test a red-black tree with an invariant checker as the oracle, and choose a suitable ordered map in Python. It builds on Binary search trees, carries its own short recap of them, and sits beside AVL trees and B-trees and B+ trees.

The structures need only the standard library; to run the plots and the notebook install the base group, and the structures group for the comparison with sortedcontainers.

Intuition

Picture a filing cabinet whose drawers each hold one, two or three folders in alphabetical order, with a rule that every route from the top of the cabinet down to a bottom drawer passes through the same number of drawers. When a new folder makes a drawer overflow, the drawer splits in two and its middle folder moves up into the drawer above; when a drawer runs empty, it borrows a folder from a neighbour or merges with it. Because every route has the same number of drawers and every drawer holds at least one folder, the cabinet can never become lopsided. That cabinet is a 2-3-4 tree, a small B-tree.

A red-black tree stores the same cabinet as a binary tree. Each drawer becomes one black node, and the other folders of the drawer hang beside it as red children, glued to it. The colour rules then say exactly what the cabinet's rules say: a red node never has a red child, because a drawer holds at most three folders, and every path from a node down to the bottom passes the same number of black nodes, because every route passes the same number of drawers. A path can alternate black and red at most, so the longest path is at most twice as long as the shortest. Inserting 1 to 15 in increasing order into a plain search tree builds a path of fifteen nodes, height 14; a red-black tree built from the same order has height 5, and from a random order almost always height 4.

How it works

Throughout the handbook the height of a tree counts edges on the longest path from the root down to a key, so a single node has height 0 and the empty tree height −1. The black height, defined below, counts something else and is kept separate.

A search tree recap

A binary search tree stores one key in each node and keeps every key of a node's left subtree smaller than the node's key and every key of its right subtree larger:

A search compares the key with the root and goes left or right, one level per comparison, until it finds the key or falls off the tree. Insertion searches for the key and hangs a new node where the search fell off. Deletion has three cases: a leaf is cut off, a node with one child is replaced by that child, and a node with two children takes the key of its inorder successor (the leftmost node of its right subtree, which has no left child) and that successor's node is removed by one of the first two cases instead. Every operation walks one path, so it costs O(h). The shape depends only on the order of the insertions: random order gives a logarithmic height with a large constant, and sorted order a height of n − 1, a list. search_tree.py holds this plain tree, and the cost section measures it against the red-black tree.

The five properties

A red-black tree is a binary search tree in which every node carries a colour and every missing child is treated as a leaf of its own, a nil leaf, holding no key. It satisfies five properties:

1. Every node is red or black.
2. The root is black.
3. Every nil leaf is black.
4. A red node has two black children, so no red node has a red parent.
5. For every node, all paths from it down to nil leaves pass the same number of black nodes.

The common number in property 5 is the black height. Books count it in two ways, so this page fixes one convention and keeps to it:

A single black node therefore has black height 1, and a nil leaf 0. The other common convention counts the node itself when it is black and leaves the nil leaf out; it gives the same number at every black node and one less at every red node, where bh′ is that other count:

Mixing the two makes a valid tree look broken, which is the reason to name the convention before tracing.

The diagrams on this page are drawn without colour, so a node's colour shows twice over: a black node is a filled circle and a red node an outlined one, and every label repeats the colour as B or R after the key, as in 69 B and 95 R. A nil leaf, when drawn, is a small filled box. A solid ring around a node marks the node a fix-up is repairing, the x of the case (in a deletion, the double black), and a dashed ring a newly inserted key. In the diagrams of the cases, triangles stand for whole subtrees and a node marked R/B may have either colour.

Every path from 69 down to a nil box passes three black nodes counting the box: for example 69, 24, 16, nil and 69, 76, 95, 80, 77, nil. The red keys 26, 64, 77 and 95 all have black children, and the root is black, so all five properties hold. Properties 4 and 5 are the ones that do the work: 4 keeps reds apart, 5 balances the blacks.

A sentinel nil versus None

In code, the nil leaves need not be separate objects. The package gives every tree one shared black sentinel node, tree.nil, and every missing child and the root's parent point to it. Two things become simpler. A colour test never needs to ask whether a child exists, because the sentinel answers "black". And when deletion removes a leaf, the empty place it leaves is the sentinel, whose parent field can be set to the node above, so the deletion fix-up can walk upward from an empty child exactly as from a real node. The cost is one node per tree, and a sentinel whose parent field is written during deletions cannot be shared between trees used by several threads.

With None for missing children every colour test goes through a helper that reads None as black, every pointer update must check whether a child exists, and the deletion fix-up must carry the parent and side of the double black separately, because an empty child has no parent field to read. none_links.py holds that version; it builds exactly the same trees with exactly the same rotations, and examples/variants.py checks this on 20000 random operations. The sentinel version's fix-up copied onto None links fails with AttributeError: 'NoneType' object has no attribute 'parent' on the first deletion of a black leaf.

Rotations

A rotation is the only operation that changes the shape. A left rotation at x lifts its right child y into x's place, x becomes y's left child, and y's old left subtree, whose keys lie between x and y, becomes x's right subtree. A right rotation at y is the mirror image and undoes it.

The inorder sequence is the same before and after, so the search-tree property survives:

A rotation relinks three pointers (x's child, y's child and the parent's child, plus the parent fields) in O(1) and keeps colours as they are, so on its own it can break properties 2, 4 and 5; the fix-ups always pair it with recolouring. Forgetting to point x's old parent (or the root) at y is the classic bug: the parent keeps pointing at x, which is now below y, and y with its right subtree vanishes from the tree.

Insertion

Insert the key exactly as in a plain search tree and colour the new node red. A red node adds nothing to any black height, so property 5 still holds; the only property that can break is property 4, when the new node's parent is red too, or property 2, when the new node is the root. The fix-up keeps this invariant at the top of its loop: x is red, every black height is right, and the only possible violation is that x's parent is red (or that the root is red). A red parent is never the root, so x has a grandparent g, which must be black. Write p for the parent and u for the uncle, p's sibling. Everything below is drawn for p as a left child; the mirror cases swap every left and right.

• Red uncle. Recolour p and u black and g red. Every path through g still passes one black node at that level, now p or u instead of g, so black heights are unchanged, but g is now red and may have a red parent. Continue with x = g, two levels up. No rotation.
• Triangle. The uncle is black (often a nil leaf) and x is the inner grandchild, the right child of a left child. A left rotation at p turns the triangle into a line, with the old parent now at the bottom as the new x. One rotation, and the line case follows at once.
• Line. The uncle is black and x is the outer grandchild. Recolour p black and g red and rotate right at g. p takes g's place as a black node over the two red nodes x and g, every path keeps its black count, and the subtree's root is black, so the loop ends. One rotation.

When the loop ends, colour the root black; that is the only step that raises the black height of the whole tree. The loop climbs two levels per red-uncle step and ends after a triangle or a line, so an insertion makes at most ⌊h/2⌋ red-uncle steps and at most two rotations: a triangle and the line it becomes. The claim, repeated in many summaries, that one rotation always suffices is false: inserting 95 and 32 in the worked example below needs two rotations each, and pitfalls.insert_without_triangle_rotation shows what a single rotation leaves behind, a red node under a red node.

Deletion

Delete as in a plain search tree. If the node holding the key has two children, its inorder successor's key and value move into it and the successor's own node, which has at most one child, is the one physically removed. Every decision below is made on that node, called y here, not on the key that was named: deleting a red key with two children may well physically remove a black leaf.

• y is red. A red node with at most one child is a leaf (a single black child would break property 5), so removing it changes no black height. Done.
• y is black with one child. That child must be red, again by property 5. Move it up into y's place and colour it black, which restores the black that every path through y lost. Done.
• y is a black leaf. Every path through its empty place is now one black short. Treat that empty child, x, as carrying an extra black: it counts as two, a double black, and the properties hold if the extra black is counted.

The fix-up moves the extra black up the tree until it can be dropped or absorbed. If x is red, it simply turns black and absorbs the extra black. If x is the root, every path passes through it, so a missing black there is missing everywhere at once and nothing needs to change: the extra black disappears and the black height of the whole tree drops by one. Otherwise look at x's sibling s and its children, the near nephew n on x's side and the far nephew f on the other side. Everything is drawn for x as a left child, with the mirror cases swapping left and right. The first two cases depend on the colour of the sibling:

• Red sibling. p must be black. Recolour s black and p red and rotate at p towards x. Black heights are unchanged, and x now has a black sibling, the old near nephew; continue with one of the next three cases. Because p is now red, a black-sibling-with-black-children step that follows ends at once by absorbing the extra black in p.
• Black sibling with black children. Recolour s red. That takes one black away from every path through s, so both sides of p are now one black short, and the extra black moves up to p: if p is red it absorbs it, otherwise p becomes the double black and the loop continues one level higher. No rotation.

The other two cases apply when the sibling is black and has a red child:

• Near nephew red, far nephew black. Recolour n black and s red and rotate at s away from x. Black heights are unchanged and x now has a black sibling whose far child is red: the next case.
• Far nephew red. Give s the colour of p, recolour p and f black, and rotate at p towards x. p is now a black node above x, which pays off the double black, and f's new black replaces the black that s took up to p's place on the far side. Done.

These are the four cases that many books number 1 to 4 in this order. The loop rotates at most three times: a red sibling (one rotation) can be followed only by an absorbing black-sibling step or by the near and far nephew cases (one rotation each), and the far nephew case ends the loop. A double black that climbs from the bottom through black-sibling steps makes no rotation at all. Deleting 69 in the worked example uses all three rotations.

Using the predecessor instead of the successor for a key with two children is equally correct but removes a different node, so every intermediate tree differs. The package uses the successor by default and accepts replacement="predecessor"; hand traces must agree on which one they use.

The 2-3-4 view

Merge every black node with its red children and the red-black tree becomes a 2-3-4 tree: a node with one, two or three keys and one more child than keys. Property 4 says a group holds at most three keys, since a black node has at most two red children and a red node no red child; property 5 says every path from the root passes the same number of groups, so all leaves of the 2-3-4 tree sit on one level.

Each black key sits in a filled cell marked B and its red partners in outlined cells marked R beside it, so every group has exactly one filled cell, in its middle when it holds three keys. The number of levels of the 2-3-4 tree is the black height of the root, which also bounds the number of keys from both sides:

The fix-ups are the 2-3-4 operations in disguise. A red-uncle step finds a group with four keys, the black g with the red p and u and the new red x, and splits it: p and u become groups of their own and g, now red, joins the group above, exactly the middle key moving up. A triangle or a line arises when a group of two keys receives a third key on its outer edge; the rotations re-encode the group so that its middle key is the black one. In deletion, a black sibling with black children is a fusion of two groups of one key with a key from the parent, a near or far red nephew is a transfer of a key from the sibling's group, and a red sibling is a re-encoding of the parent's group of two keys that brings the right sibling next to x. One 2-3-4 tree corresponds to several red-black trees, because a group of two keys can lean either way; from_two_three_four builds either encoding.

Left-leaning red-black trees

Left-leaning red-black trees, proposed by Sedgewick in 2008, add one rule: a red node may only be a left child, and in the variant built here no node keeps two red children. Then every group of two keys has a single encoding and groups of three keys never last, so the tree mirrors a 2-3 tree. Insertion becomes a short recursive function that repairs each node on the way back up with three local steps: rotate a red right child to the left, rotate two reds in a row on the left into a temporary group of three, and split that group by flipping the colours of a node and its two children. left_leaning.py implements it.

The code is shorter, but it does more work. On 20000 random keys it made 1.1858 rotations and 4.1813 colour changes per key against 0.5890 and 2.3208 for the standard insertion, and its height was 19 against 16; on 20000 ascending keys it stayed at height 14, against 25 for the standard tree. Deletion is markedly more intricate than insertion in the left-leaning form, and the production libraries named below all use the classic tree.

Cost

Every operation

For a red-black tree with n keys and height h:

• search, minimum, maximum, floor, ceiling, successor and predecessor: at most h + 1 comparisons, O(log n) in the worst case.
• insert: one search, then at most ⌊h/2⌋ red-uncle steps and at most two rotations, O(log n) in the worst case.
• delete: one search, one walk down to the successor, then at most h + 1 black-sibling steps and at most three rotations, O(log n) in the worst case.
• a range query reporting k keys: O(h + k).
• space: one node per key with a colour, a key, a value and three links, and one sentinel per tree.

Insertion climbs two levels per red-uncle step and stops after its rotations:

Deletion's double black climbs one level per black-sibling step, from at most h + 1 levels down, and the three other cases rotate once each:

A range query walks down to the first key at most once per level and then reports keys in order, each step of the inorder walk paid for by a reported key or by one of the two boundary paths:

All of these are worst-case bounds; the number of colour changes per operation, analysed below, is O(log n) in the worst case but O(1) amortized. The distinction matters. Structures that store extra information in every node, such as the order-statistic and interval trees of Augmented trees, must repair that information after every rotation, so a constant number of rotations per update keeps their updates cheap, while colour changes touch nothing else.

Why the height is logarithmic

First, a subtree is never smaller than its black height allows. By induction on the height: a nil leaf has black height 0 and holds 0 = 2⁰ − 1 keys. A node x with black height bh(x) has two children whose black height is bh(x) or bh(x) − 1, depending on their colour, so each child's subtree holds at least 2^(bh(x)−1) − 1 keys:

Second, take a longest path from the root r down to a key at depth h and continue it to that key's nil leaf. Below the root it passes h + 1 nodes, the nil leaf included. No two of them in a row are red and the last is black, so at least half of them are black, and the black height of the root is at least (h + 1)/2. Putting the two together:

Many books state the bound as h ≤ 2 log2(n + 1) because they count the edge down to the nil leaf as part of the height; in the convention of this handbook that is the same statement shifted by one. No binary tree with n keys is shorter than a perfect one:

so a red-black tree is never more than about twice as tall as the best possible tree for its keys.

How tall a red-black tree can really be

The factor 2 is real. The sparsest red-black tree of height h, the one with the fewest keys, has a single long path that alternates black and red, with all-black perfect trees hanging beside it. Counting its keys level by level gives m(h), the fewest keys a red-black tree of height h can hold:

The first heights need 1, 2, 4, 6, 10, 14, 22 and 30 keys. bounds.fewest_keys recomputes these numbers by an exhaustive dynamic program over all colourings, and the tests check that every size up to 20 keys reaches exactly the largest height the formula allows. The tallest red-black tree with n keys is therefore

A surprise from the measurements: inserting keys in ascending order, the worst order for a plain search tree, builds exactly this tallest possible red-black tree for every n from 1 to 5000 that was checked. Sorted input drives the red-black tree to the edge of its rules, and that edge is still only about 2 log2 n.

The cost of insertion and deletion, amortized

A single insertion can recolour all the way up the tree, ⌊h/2⌋ red-uncle steps, but such insertions are rare, and over a sequence the total is linear. Take the number of red nodes as a potential. Attaching a new red node raises it by one, a red-uncle step lowers it by one (two nodes turn black, one turns red), and the triangle and line steps leave it unchanged. The potential starts at zero and never goes negative, so over m insertions into an empty tree the red-uncle steps R_m number at most m:

With deletions mixed in the same holds, amortized O(1) colour changes per operation, though the proof needs a more careful potential; it is the classical result that 2-3-4 trees need O(1) splits and fusions per update on average, carried over by the correspondence above.

The accounting gives one more exact identity. Count black nodes over any sequence that starts and ends with an empty tree. A red-uncle step (R of them) adds one black node and a root blackening (B_r) adds one; removing a black leaf (L) removes one and so does a black-sibling-with-black-children step (F); absorbing the extra black (A) and the far nephew step (Q) each add one, and every other step leaves the count alone. Every double black ends exactly once, absorbed, dropped at the root (D) or paid off by a far nephew step. And the black height of the whole tree rises only at root blackenings and falls only at drops, so the two are equal:

So over any such sequence the red-uncle steps of the insertions exactly balance the black-sibling steps of the deletions: every 4-node split is matched by a fusion. The measurements below show it to the last step, and a test checks it on random sequences.

Counted heights and rotations

The example heights_and_rotations.py builds trees of 16 to 16384 keys in random order (the mean of three seeds) and in ascending order, and an unbalanced search tree from the same random orders.

At n = 16384 the red-black tree built in random order has height 16, and the one built in ascending order height 25, the tallest any red-black tree of that size can have and still below the bound of 27.0. The plain search tree built in random order reaches 32.33, taller than the red-black tree's worst case; built in ascending order it has height 2047 at n = 2048. Height is the worst case, but searches pay the average depth plus one. A successful search in the random red-black tree makes 13.3615 comparisons on average and in the ascending one 13.5014, both slightly below log2 n = 14, while the plain search tree makes 17.2276, close to the classical prediction for random insertion orders:

which gives 17.5639 at n = 16384.

Both panels are flat: rotations and colour changes per operation do not grow with n. At n = 16384 random insertions made 0.5829 rotations and 2.3193 colour changes per key, ascending insertions 0.9984 and 4.9927, and deleting every key in random order 0.3822 and 1.7701. The largest number of rotations any single insertion needed in all these runs was 2, and any single deletion 3, the worst cases exactly.

The same example counts how often each case runs over 4096 random insertions followed by 4096 random deletions, per operation and averaged over three seeds. An insertion meets a red uncle 0.5129 times, a triangle 0.1892 times and a line 0.3882 times on average. A deletion physically removes a red node 0.2846 of the time, a black node with a red child 0.2154 and a black leaf 0.5000, and then meets a red sibling 0.0605 times, a black sibling with black children 0.5129 times, a red near nephew 0.1065 and a red far nephew 0.2123 times. The red-uncle and black-sibling counts are equal, 6302 each over the three runs, as the identity above demands.

Worked example

Every step below is printed by examples/worked_example.py and asserted by tests/test_worked_example.py. Trees are written as outlines: a node with children is (key left right), a node without children is just its key, a red key carries a star and an empty child is a dash. So (41 33 52) is a black 41 with the red children 33 and 52.

Inserting twelve keys

The keys 80, 76, 71, 24, 16, 98, 69, 26, 95, 32, 77 and 64 are inserted into an empty tree. Each bullet gives the cases of the fix-up and the tree afterwards.

• 80 becomes the root, red for a moment and then black: 80.
• 76 goes left of 80, whose colour is black, so nothing is to repair: (80 76* -).
• 71 goes left of the red 76. The uncle, 80's right child, is a nil leaf and therefore black, and 71 is the outer grandchild: line. 76 turns black, 80 red, and a right rotation at 80 lifts 76: (76 71 80). One rotation, two colour changes.
• 24 goes left of the red 71, whose sibling 80 is red: red uncle. 71 and 80 turn black and 76 red, which is the root, so it turns black again: (76 (71 24* -) 80). No rotation, four colour changes.
• 16 goes left of the red 24 with no uncle: line. 24 turns black, 71 red, and a right rotation at 71: (76 (24 16 71) 80).
• 98 goes right of the black 80: (76 (24 16 71) (80 - 98*)).
• 69 goes left of the red 71, which is the right child of 24, with the red uncle 16: red uncle, mirrored. 71 and 16 turn black and 24 red; 24's parent 76 is black, so the loop stops: (76 (24 16 (71 69 -)) (80 - 98*)).
• 26 goes left of the red 69, which is the left child of 71, with no uncle: line. 69 turns black, 71 red, right rotation at 71: (76 (24 16 (69 26 71)) (80 - 98)).
• 95 goes left of the red 98, which is the right child of 80, with no uncle, so 95 is an inner grandchild: triangle, mirrored. A right rotation at 98 lifts 95 and makes 98 the outer grandchild: line, mirrored. 95 turns black, 80 red, and a left rotation at 80: (76 (24 16 (69 26 71)) (95 80 98*)). Two rotations.
• 32 goes right of the red 26, whose sibling 71 is red: red uncle. 26 and 71 turn black and 69 red. Now 69 is red under the red 24, which is the left child of 76, and the uncle 95 is black; 69 is the right child of a left child: triangle. A left rotation at 24 puts 24 below 69: line. 69 turns black, 76 red, and a right rotation at 76 makes 69 the root: (69 (24 16 (26 - 32)) (76 71 (95 80 98*))). Four comparisons, two rotations, five colour changes.
• 77 goes left of the red 80, whose sibling 98 is red: red uncle, making 95 red under the red 76, whose sibling 24 is red too: red uncle, mirrored. 76 and 24 turn black and the root 69 red and then black again: (69 (24 16 (26 - 32)) (76 71 (95 (80 77* -) 98))). Seven colour changes, no rotation.
• 64 goes right of the red 32, which is the right child of 26, with no uncle: line, mirrored. 32 turns black, 26 red, and a left rotation at 26: (69 (24 16 (32 26 64)) (76 71 (95 (80 77 -) 98))).

The first six insertions build a tree of height 2 with 76 at the root; the next six make it two levels deeper and bring 69 to the root:

The twelve insertions made 32 comparisons, 8 rotations and 30 colour changes. The final tree has height 4 and black height 3, and between them the insertions met every case on both sides: red uncle, triangle and line, each also mirrored. The insertion of 32 meets all three cases in one fix-up:

Each frame shows the state before the next case, with the roles x, p, u and g of that case written under the keys. The red-uncle step pushes the problem two levels up; the triangle and the line then fix it with one rotation each.

Deleting seven keys

Then 69, 71, 95, 76, 32, 77 and 98 are deleted from that tree, each key with two children replaced by its inorder successor.

• 69 is the root and has two children, so its successor 71 moves into the root and the node that held 71, a black leaf, is removed. A double black is left at the empty left child of 76. Its sibling 95 is red: red sibling. 95 turns black, 76 red, and a left rotation at 76. The new sibling 80 is black with the red near child 77 and an empty far child: near nephew red. 77 turns black, 80 red, and a right rotation at 80. The new sibling 77 has the red far child 80: far nephew red. 77 takes 76's colour, red, 76 and 80 turn black, and a left rotation at 76 pays off the double black: (71 (24 16 (32 26 64)) (95 (77* 76 80) 98)). Three rotations and seven colour changes, the most a deletion can need.
• 71 has two children; its successor 76 moves up and the black leaf that held 76 is removed, leaving a double black at the empty left child of 77. The sibling 80 has two black (empty) children: black sibling with black children. 80 turns red and the extra black moves up to 77, which is red and absorbs it by turning black: (76 (24 16 (32 26 64)) (95 (77 - 80*) 98)). No rotation.
• 95 has two children; its successor 98 moves into its node and the black leaf that held 98 is removed, leaving a double black at the empty right child of the node now holding 98. Its sibling 77 is black with the red near child 80, on the right because this is the mirror image: near nephew red, mirrored. 80 turns black, 77 red, and a left rotation at 77; then far nephew red, mirrored: 77 turns black and a right rotation at 98 finishes: (76 (24 16 (32 26 64)) (80 77 98)). Two rotations.
• 76 has two children; its successor 77 moves up and the black leaf that held 77 is removed, leaving a double black at the empty left child of 80. The sibling 98 has black children: black sibling with black children. 98 turns red and the extra black moves up to 80, which is black and becomes the double black. Its sibling 24, on the left this time, has the black children 32 and 16: black sibling with black children, mirrored. 24 turns red and the extra black reaches the root 77 and disappears: (77 (24 16 (32 26 64)) (80 - 98)). No rotation; the black height of the whole tree drops from 3 to 2.
• 32 has two children; its successor 64 moves up and the node that held 64 is a red leaf, so removing it changes nothing else: (77 (24 16 (64 26 -)) (80 - 98*)).
• 77 has two children; its successor 80 moves into the root, and the node that held 80 is black with the red child 98, which moves up and turns black: (80 (24 16 (64 26 -)) 98).
• 98 is a black leaf on the right of the root, so a double black is left there. Its sibling 24 is red: red sibling, mirrored. 24 turns black, 80 red, and a right rotation at 80 makes 24 the root. The new sibling 64 has the red far child 26: far nephew red, mirrored. 64 takes 80's colour, red, 80 and 26 turn black, and a right rotation at 80: (24 16 (64* 26 80)). Two rotations.

The seven deletions made 7 rotations and met all four double-black cases on both sides, besides the removal of a red leaf, of a black node with a red child, an absorption by a red parent and a drop at the root. The deletion of 69 shows the longest fix-up. First the successor takes the place of the key and leaves a double black behind:

The roles written under the keys name the first case, a red sibling, and three cases with one rotation each follow:

The double black stays at the empty left child of 76 through all three cases, while the sibling changes from 95 to 80 to 77; only the last rotation, at 76 itself, removes it.

The code

The package red_black_trees is plain Python, one idea per module. Importing it needs only the standard library; Matplotlib is imported by plotting.py alone and sortedcontainers inside the functions of comparisons.py that use it.

• node.py holds Node, the colours RED and BLACK, make_nil for the sentinel and snapshots: the tree as nested tuples that tests compare and pictures draw. outline.py writes and parses the one-line outlines used above.
• counting.py holds OperationCounter with the fields comparisons, rotations and recolours, three_way for counted comparisons and CountedKey for counting the comparisons library code makes.
• trace.py holds the Step record (action, keys, snapshot, case and side), record, describe, format_trace, cases and CaseLog, a trace that keeps steps without snapshots for counting cases over thousands of operations.
• rotations.py holds rotate_left, rotate_right and recolour; insertion.py holds insert and insert_fixup; deletion.py holds find, transplant, delete and delete_fixup.
• tree.py holds RedBlackTree, the ordered map: insert, delete, search, the mapping protocol, min, max, floor, ceiling, successor, predecessor, range, prefix, height, black_height and from_shape. queries.py holds the read-only walks it uses, written iteratively so that they also serve the unbalanced tree.
• search_tree.py holds SearchTree, the plain search tree of the recap; none_links.py holds NoneLinkedTree; left_leaning.py holds LeftLeaningTree; two_three_four.py converts between red-black trees and 2-3-4 trees.
• invariants.py holds red_black_violation, is_red_black and check_red_black, which check the five properties, the parent links, the key order and the size, and name the first broken one in a sentence; tests run it after every operation.
• bounds.py holds the formulas of the cost section, the dynamic program that checks them and the sparsest trees; workloads.py holds the worked example's keys and seeded random inputs and operation sequences that grow and drain to empty.
• layout.py computes tidy positions for drawing binary trees; drawing_parts.py writes the pieces of a drawing as Graphviz text, black nodes filled, red nodes outlined and every label ending in B or R; drawing.py arranges them into deterministic pictures with every node pinned and the frames of a sequence in rows that fit the width of a card; and group_drawing.py draws a tree beside its 2-3-4 tree. Graphviz's own layout reorders the children of incomplete trees inside clusters, so a lone left child could otherwise come out on the right.
• comparisons.py holds SortedKeysMap, a dict with a sorted key list kept by bisect that serves as the test oracle, and helpers for sortedcontainers' SortedDict; pitfalls.py holds deliberately broken versions for the pitfalls below; plotting.py draws every figure in the handbook's colours.

The heart of insertion is the loop below; side is "left" when the parent is a left child, and child and other turn the same lines into the mirror image:

while node.parent.colour == RED:
    parent = node.parent
    grand = parent.parent
    side = "left" if parent is grand.left else "right"
    uncle = child(grand, other(side))
    if uncle.colour == RED:
        recolour(tree, parent, BLACK, trace)
        recolour(tree, uncle, BLACK, trace)
        recolour(tree, grand, RED, trace)
        node = grand
        continue
    if node is child(parent, other(side)):
        rotate(tree, parent, side, trace)
        node, parent = parent, node
    recolour(tree, parent, BLACK, trace)
    recolour(tree, grand, RED, trace)
    rotate(tree, grand, other(side), trace)

The examples run in a few seconds each from the repository root:

• examples/worked_example.py prints every step of the worked example and writes the eight generated diagram sources.
• examples/heights_and_rotations.py measures heights, search costs, rotations, colour changes and case frequencies and saves two figures.
• examples/variants.py compares the sentinel and None versions, reads trees as 2-3-4 trees and measures the left-leaning variant.
• examples/common_mistakes.py runs every broken version from pitfalls.py next to the correct code.
• examples/compare_with_sortedcontainers.py checks the tree against SortedDict and the sorted key list and counts their comparisons.
• examples/practice.py prints fresh exercises with their solutions; --seed gives a new set.

python trees/red-black-trees/examples/worked_example.py
python trees/red-black-trees/examples/heights_and_rotations.py
python trees/red-black-trees/examples/variants.py
python trees/red-black-trees/examples/common_mistakes.py
python trees/red-black-trees/examples/compare_with_sortedcontainers.py
python trees/red-black-trees/examples/practice.py --seed 7

The sample project, project/word_index.py with its helper project/index.py, builds an ordered symbol table over a whole book: every word of Moby Dick with the positions where it occurs, in a red-black tree keyed by the word. It answers lookups, prefix ranges, floor and ceiling queries and ranges between two words, and checks every answer against a dict with a sorted key list. The default run indexes 216625 words, 17368 of them distinct, with 11.5224 comparisons per word, 10379 rotations and 40687 colour changes; the tree's height is 16, against a bound of 27.17 and a shortest possible height of 14, and its black height is 9. Looking up "whale" finds 1110 occurrences; the prefix "whal" covers 19 words; the misspelling "pequad" lies between "peppered" and "pequod", and "queequeeg" just before "queequeg", which is how a spelling suggester would use floor and ceiling. 3000 random lookups, floors, ceilings, prefixes and ranges agree with the oracle. Finally the run deletes all 7650 words that occur only once, in random order, with 2368 rotations and 10437 colour changes, running the full invariant check every 1000 deletions; 9718 words remain and the height is still 16. Options --words, --prefixes, --near, --probes, --check-every and --seed change the queries, --text indexes another text file, and --figures writes the figure elsewhere; the default run takes a few seconds.

python trees/red-black-trees/project/word_index.py
python trees/red-black-trees/project/word_index.py --prefixes sea,ship --near ahabs

Indexing m words with v distinct ones costs at most h + 1 comparisons per word:

The measured 11.5224 per word is well under log2 17368, about 14.08, because the frequent words are found high in the tree.

The right panel holds the project's most interesting result. Counted once per distinct word, the plain search tree is clearly the worst. Counted once per word of the text, so that frequent words weigh more, it does almost as well as the red-black tree: words like "the", "of" and "and" appear in the first lines, land near its root and stay there. The red-black tree built in text order keeps much of that advantage, 10.6974 comparisons per word of text, because rotations rarely push old keys far down, while the tree built from the alphabetical vocabulary, whose shape ignores frequency, needs 14.2498. A balanced tree guarantees the worst case; when the access pattern is skewed and known, a splay tree or a hash table can do better.

The text is Moby Dick; Or, The Whale by Herman Melville, eBook 2701 of Project Gutenberg, public domain in the United States. The project downloads it once from the stable address https://www.gutenberg.org/files/2701/2701-0.txt into .data/red-black-trees/ at the repository root, never commits it, and pins the SHA-256 of the text between Gutenberg's start and end markers; a different text only prints a warning, because Project Gutenberg occasionally corrects its books, and --strict turns the warning into an error. All other data are synthetic, generated from seeds by workloads.py.

The notebook red_black_trees.ipynb follows this page: the properties and the black-height convention, the worked example traced step by step, the invariant checker on random sequences, the cost measurements, the 2-3-4 view and the comparison with sortedcontainers. The tests in tests check the worked example step by step, every case and its mirror, the invariants after every operation of long random sequences of insertions, deletions and searches, the bounds of the cost section on counts, the agreement of the variants and of the oracles, and the broken versions, and run in a few seconds:

python -m pytest trees/red-black-trees

In practice

Python, sortedcontainers and the standard library

Python has no balanced search tree in its standard library. dict and set are hash tables: lookups are O(1) on average, but they know no order besides insertion order and answer no floor, ceiling or range query. A dict with a sorted list of its keys kept by bisect, the SortedKeysMap the tests use as their oracle, answers ordered queries by binary search, but every new or deleted key shifts half the list on average. The third-party sortedcontainers package, the usual choice, stores keys in a list of sorted sublists of about a thousand keys each, which keeps insertions cheap and memory compact, and SortedDict pairs that with a dict, so its lookups are hash lookups. examples/compare_with_sortedcontainers.py shows that the three agree:

from red_black_trees import RedBlackTree, random_permutation, sorted_dict, sorted_dict_floor

keys = random_permutation(1000, seed=1)
tree, library = RedBlackTree(keys), sorted_dict((key, None) for key in keys)
assert list(tree) == list(library)
assert all(tree.floor(k + 0.5) == sorted_dict_floor(library, k + 0.5) for k in range(999))

On 20000 random insertions, deletions and searches all three held the same keys, floors, ceilings and ranges at every one of 401 checkpoints. Counted through wrapped keys, they also do about the same number of comparisons: for 65536 random insertions the tree made 14.8820 three-way comparisons per key and SortedDict 14.8182 less-than tests, and a floor query cost 16.3582 against 16.0628. The difference is in the constants of the language. Inserting 50000 keys, SortedDict was several times faster than this pure-Python tree and the dict with a sorted list about twice as fast, and SortedDict's hashed lookups were dozens of times faster; these wall-clock ratios vary from run to run and mostly measure Python against C, not one algorithm against another. When to use which:

• Use dict or set when you only look keys up.
• Use sortedcontainers' SortedDict, SortedList or SortedSet in Python when you also need order: minimum and maximum, floor and ceiling, ranks, or ranges.
• Use a dict with a bisect-sorted key list for small or mostly static collections.
• Use a red-black tree when you need guaranteed O(log n) worst cases with O(1) rotations per update, nodes that stay where they are while the tree changes (iterators and pointers into the structure stay valid), or nodes you can augment with extra fields, as in Augmented trees.
• Use a heap when only the minimum matters, and a B-tree when keys live on disk or cache lines matter.

Where red-black trees run

Java's TreeMap and TreeSet are red-black trees, and HashMap turns a bucket that collects eight or more colliding keys into a small red-black tree, once its table has at least 64 buckets, so that an adversary who forces collisions gets O(log n) instead of O(n) per lookup. C++'s std::map, std::set, std::multimap and std::multiset are red-black trees in the three major standard libraries (the _Rb_tree of libstdc++, the __tree of libc++ and the _Tree of Microsoft's library): the C++ standard asks for logarithmic operations and for iterators that stay valid while other elements are inserted or erased, which a node-based balanced tree provides. .NET's SortedSet and SortedDictionary are red-black trees too.

The Linux kernel has its own implementation in lib/rbtree.c, written to be embedded inside other structures. The CPU scheduler keeps the runnable tasks of each CPU in a red-black tree, ordered by virtual run time and, since the EEVDF scheduler of Linux 6.6, by virtual deadline, and caches the leftmost node so the next task is found in O(1); the high-resolution timers keep pending timers in one ordered by expiry; epoll keeps the file descriptors it watches in one; and many file systems and drivers use them for extents and requests. Memory areas of a process were kept in a red-black tree until Linux 6.1 replaced it with the maple tree, a B-tree variant, which shows the trade-off the next paragraph names.

Red-black trees are not the only balanced trees. AVL trees keep the heights of sibling subtrees within one of each other and are more tightly balanced,

so their searches are slightly shorter, but a deletion may rotate at every level on the way up, while a red-black tree rotates at most three times. B-trees and their relatives pack many keys per node, which suits disks and caches better than one key per node: databases and file systems use B+ trees, and Rust's standard library chose a B-tree for its BTreeMap. Splay trees and treaps trade the worst case for simplicity or adaptivity. Red-black trees win where the guarantee per operation and the small, constant amount of restructuring both matter.

Pitfalls

• Deciding the case by the key you were asked to delete. The cases depend on the node physically removed, the successor when the key has two children. Deleting the red 95 from the worked tree removes the black leaf that held 98 and needs a fix-up; skipping it because 95 was red leaves black heights of 2 and 1 below 98. examples/common_mistakes.py runs this and every following mistake.
• Believing one rotation is always enough. A triangle needs a rotation at the parent before the line's rotation at the grandparent; rotating only at the grandparent leaves the inner grandchild as the red child of a red node, as in (38 - (62 45 -)) after inserting 62, 38 and 45.
• Recolouring with a black uncle. The red-uncle recolouring is right only when the uncle is red; with a black or missing uncle it leaves one side of the grandparent a black short.
• Inserting new nodes black. A black node lengthens the black count of every path through it, so the second key already breaks property 5. New nodes are red.
• Forgetting the last line of the insertion fix-up. A red-uncle step that reaches the top leaves the root red; colour it black.
• Forgetting to move the double black up. When the sibling and both its children are black and the parent is black too, recolouring the sibling red is not the end: the parent becomes the double black and the loop continues.
• Tracing only one side. Every case has a mirror image in which every left and right swap, including the direction of every rotation and which nephew is near; in the worked example 95, 69 and 98 all need mirrored cases.
• Mixing black-height conventions. Counting the node itself and not the nil leaf gives one less at every red node: the red 95 of the worked tree has black height 2 in this page's convention and 1 in the other, while its black children 80 and 98 have 1 in both. Comparing numbers from the two conventions makes a valid tree look broken; name the convention first.
• Rotations that lose a link. A rotation updates the child pointer of the old parent (or the root) and three parent fields; leaving out the first one drops a whole subtree from the tree, as the broken left rotation at 24 in pitfalls.py drops 32 and 64.
• Reading the parent of an empty child. With None for missing children, the deletion fix-up cannot ask the double black for its parent; carry the parent and side along, or use a sentinel.
• Mixing successor and predecessor. Both are correct, but they remove different nodes and produce different trees; deleting 69 gives (71 (24 16 (32 26 64)) (95 (77 76 80) 98)) with the successor and (64 (24 16 (32 26 -)) (76 71 (95 (80 77 -) 98))) with the predecessor.
• Checking only local rules. A tree with no red node under a red node can still have unequal black heights; check property 5 for every node, as check_red_black does, and check the key order and the parent links as well.
• Expecting one particular tree. The classic algorithm, its left-leaning variant, top-down versions and different replacement rules all build valid but different trees from the same keys. Tests should check the properties and the contents, not a particular shape, unless the algorithm is fixed as in the worked example.

Further reading

• R. Bayer, "Symmetric binary B-Trees: Data structure and maintenance algorithms", Acta Informatica 1(4), 290-306, 1972. The structure, as binary B-trees.
• L. J. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees", Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 8-21, 1978. The red and black colouring and its link to 2-3-4 trees.
• R. E. Tarjan, "Updating a balanced search tree in O(1) rotations", Information Processing Letters 16(5), 253-257, 1983.
• S. Huddleston and K. Mehlhorn, "A new data structure for representing sorted lists", Acta Informatica 17(2), 157-184, 1982. Amortized constant restructuring of (a, b)-trees, which carries over to red-black trees.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, fourth edition, chapter 13, MIT Press, 2022. Red-black trees with the sentinel and the four deletion cases.
• R. Sedgewick and K. Wayne, Algorithms, fourth edition, section 3.3, Addison-Wesley, 2011. Balanced search trees through 2-3 trees and left-leaning red-black trees.
• R. Sedgewick, "Left-leaning red-black trees", Princeton University, 2008.
• C. Okasaki, "Red-black trees in a functional setting", Journal of Functional Programming 9(4), 471-477, 1999. Insertion in a few lines of pattern matching.
• K. Germane and M. Might, "Deletion: The curse of the red-black tree", Journal of Functional Programming 24(4), 423-433, 2014.
• D. E. Knuth, The Art of Computer Programming, volume 3, Sorting and Searching, second edition, section 6.2.3, Addison-Wesley, 1998. Balanced trees and the AVL height bound.
• The Linux kernel documentation, "Red-black Trees (rbtree) in Linux", Documentation/core-api/rbtree.rst.
• G. Jenks, the sortedcontainers documentation, which explains its list-of-lists design and measures it against tree-based ordered maps.