A search tree needs an ordering rule to find keys, but ordering alone allows a long chain. An AVL tree controls the heights of neighboring subtrees directly. A red-black tree instead stores one color bit per node and controls how black nodes occur on paths. The two children need not have the same ordinary height. Nevertheless, their paths have the same black count, and red nodes cannot occur consecutively. Together these conditions prevent a path from becoming arbitrarily longer than another.
The colors have no meaning for the stored set: changing a color does not change a key. Their purpose is to give an invariant that an update can repair locally. We will first prove the height bound, then derive insertion repair. In particular, we will see why an insertion may recolor several ancestors but needs at most two rotations. Deletion needs a different repair argument and is outside this lesson.
Include the empty child links in the definition
Assume distinct keys with a consistent total order. Every key in a node's left subtree is smaller, and every key in its right subtree is larger. Inserting an existing key leaves the ordered set unchanged. Ordinary search follows these inequalities and does not inspect colors.
Definition 15.2.1
(Internal nodes, external NIL leaves and black height)
Each stored key belongs to an internal node, colored red or black. Every empty child link leads conceptually to a black external leaf called NIL. There may be one shared sentinel object in code, but each empty link is a separate leaf occurrence in the mathematical tree.
A red-black search tree satisfies all of the following:
- Every external
NILleaf is black. - A nonempty root is black.
- Every red internal node has black children.
- At every internal node, all downward paths to external leaves contain the same number of black nodes after leaving that node, including the final
NIL.
That common number is the node's black height . Set . Thus an internal leaf has black height 1, whether the leaf itself is red or black. For an internal node and either child ,
Here the indicator is 1 for a black child, including NIL, and 0 for a red child. Its meaning is to count the child that excludes.
The two internal children can have different black heights: a black child contributes its own color, while a red child does not. What must agree is the total contribution along the two child links. Equal black counts do not require equal numbers of keys in the subtrees.
During insertion repair we temporarily allow a red root or one red node with a red parent. These are intermediate states, not additional valid forms of the final data structure. We will retain search order and equal path black counts throughout.
Prove that a color invariant controls search depth
Let count internal nodes in a subtree. External leaves contribute zero. Let be the largest number of edges on a path from the root to an external leaf; for an empty tree set . A successful search visits at most internal nodes. An unsuccessful search can reach an external leaf after at most key comparisons.
Theorem 15.2.2
(The red-black height bound)
A valid red-black tree with stored keys satisfies
Consequently search takes comparisons in the worst case.
Proof
(Separate the number of black levels from the number of edges)
First prove by induction on subtree size. It is true at NIL, where both sides are zero. For an internal node, each child's black height is at least . The induction hypothesis therefore gives
For a nonempty tree, choose a longest root-to-NIL path. After excluding the root, it contains node occurrences. Its last occurrence is black NIL. Every red occurrence has a following black occurrence, and distinct red occurrences have distinct such followers, because red nodes cannot be consecutive. Thus at least occurrences are black. Their count is exactly , so .
Combining this with yields the stated bound. The empty tree satisfies it separately.
This is a worst-case bound, not a statement that each search takes exactly the same number of comparisons. A red-black tree can be less rigidly balanced than an AVL tree, while still forbidding linear-height chains.
Insert red so that the black count does not change
Find the insertion position by ordinary search-tree comparisons. If the key is absent, replace its external leaf by a new red node with two black NIL children. Each old path through that link counted one black external leaf. Each new path counts a red node and then one black external leaf, so the black count is unchanged.
If has a black parent, all invariants already hold, apart from the possibility that is the root. Coloring the root black finishes that case. If its parent is red, there is a red-red edge. Since the root was black before insertion and the repair loop continues only while the parent is red, this parent has an internal grandparent . The grandparent is black in the loop states described below.
The parent's sibling is the uncle . An absent uncle is black NIL; it must be included when choosing a case. Start with on the left of . The other orientation is obtained by exchanging left and right everywhere.
Common mistake
(An absent uncle is black)
In 10B(5R,-), inserting 7 below 5 leaves the uncle as the empty right link of 10. That link is a black NIL, so the black-uncle case applies: left-rotate 5, color 7 black and 10 red, and right-rotate 10.
Proof X-ray
The repair loop has one moving defect
At the start of an iteration, is red. Search order and equal path black counts hold. The only possible red-red edge is between and its parent; a red root is also permitted temporarily. Every other red node has black children.
If the loop runs, the parent is red, so is not the root. The grandparent exists and is black: otherwise there would be another red-red edge between parent and grandparent. Each case below preserves these facts, moves the one possible defect upward, or removes it completely. They are stronger claims than simply observing that a small drawing looks balanced.
A red uncle lets us move the defect upward
If is red, color and black, color red, and continue with . Every path through this subtree previously counted the black and a red child. Afterwards it counts red and one black child. Its total black contribution is unchanged.
Because and were red, their own children were black, apart from the permitted red-red edge involving . After becomes black, that edge disappears. The newly red has black children. Its only possible conflict is with its own parent, exactly the defect handled by the next iteration. If is the root, the loop stops and the final root recoloring resolves it.
Recoloring this subtree's root red is therefore deliberate. Leaving black after making both children black would increase the subtree's black contribution by one. If is not the whole-tree root, paths through its sibling at an ancestor would no longer have the same count.
A black uncle requires a triangle or line repair
If the uncle is black and is the right child of the left parent, the two red links form a triangle. Left-rotate , changing no colors. The red child becomes the red parent, and the old parent becomes its red left child. This converts the triangle into a line. Because the rotated nodes are both red, paths have the same black contribution before and after the rotation.
Now consider the line, with red parent on the left of black grandparent and red on the left of . Color black, color red, and right-rotate . The new subtree root is :
g(B) p(B)
/ \ / \
p(R) U becomes z(R) g(R)
/ \ / \ / \
z(R) C A B C U
/ \
A B
The letters denote entire subtrees, not necessarily individual leaves. Their roots are black, including the possibility of NIL.
Proof X-ray
Check ordering, colors and black counts separately
Search order gives the inorder sequence before and after repair. The rotation moves from the right of to the left of , where the same inequalities place it correctly. No key is lost or duplicated.
For the black counts, count black nodes from the root of each displayed hanging subtree through its final external leaf, including that hanging root. These counts are equal: equality inside equates and ; equality at red equates them with ; equality at black equates them with . Call the common count .
Before repair, every path through the displayed subtree has one black node at , then contribution . Afterwards, it has one black node at , then contribution . Equal path counts hold at the newly red and at too. Both red nodes, and , have black children.
Finally, the old subtree root was black, and its replacement is black. An ancestor sees the same black contribution and cannot gain a new red-red edge. The repair is complete. In a triangle, first doing the red-red rotation gives this same line argument.
A right-side parent uses the mirror image: a left triangle first right-rotates the parent, and the resulting line left-rotates the grandparent. These are the same proofs with the inequalities and directions reversed.
Keep the moving node and parent links precise
The following pseudocode uses RED and BLACK as color constants. root.parent is a black sentinel. Every internal node has left, right, parent and color fields. NIL is black and is never recolored. rotate_left(x) and rotate_right(x) update the root if needed, the changed parent links and the moved middle subtree. Each rotation preserves search order; it changes no colors by itself.
insert(key):
search for key from root
if key exists: return false
attach a new RED node z at the missing child link
set z.left = NIL and z.right = NIL
while z.parent.color == RED:
if z.parent == z.parent.parent.left:
u = z.parent.parent.right
if u.color == RED:
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z == z.parent.right:
z = z.parent
rotate_left(z)
z.parent.color = BLACK
z.parent.parent.color = RED
rotate_right(z.parent.parent)
else:
u = z.parent.parent.left
if u.color == RED:
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z == z.parent.left:
z = z.parent
rotate_right(z)
z.parent.color = BLACK
z.parent.parent.color = RED
rotate_left(z.parent.parent)
root.color = BLACK
return true
In a triangle, assigning z = z.parent before rotating is important. After rotation, the old parent is the lower red node. The later z.parent now denotes the middle key, which must become black in the line repair. Reusing a cached parent or grandparent without updating it can recolor or rotate the wrong node.
Every red-uncle iteration moves two levels upward. A black-uncle iteration uses at most two rotations and removes the defect; after it, the loop condition is false because has a black parent. The loop therefore terminates. Finally coloring the root black adds one black node to every whole-tree path if necessary, preserves all equalities and removes the temporary root exception.
Finding the insertion point and walking upward take time. At most two rotations occur during one successful insertion, although recoloring can occur at ancestors. These are different operation counts. They do not make the entire insertion constant time.
Theorem 15.2.3
(Insertion preserves the red-black invariants)
Inserting a new key into a valid red-black tree by the procedure above terminates, performs at most two rotations, and returns a valid red-black tree that contains the old keys and the new key. Its running time is .
Proof
(Assembling the cases into one induction)
Before the first iteration, the new red node leaves every black count unchanged, and the only possible red-red edge joins to its parent. Each iteration keeps this invariant by the red-uncle or black-uncle case proved above, and the loop ends after at most two rotations, as shown above. At exit only a red root can remain; coloring it black adds one black node to every path. The loop visits only the at most ancestors of the new node, which gives the time bound.
Follow a recoloring and then a triangle
Worked example 15.2.4
(Insert 10, 5, 15, 1, 2 into an empty tree)
Use notation keyColor(left,right), write - for a black external leaf, and abbreviate an internal leaf by its key and color.
| Inserted key | Repair | Complete tree afterwards |
|---|---|---|
| 10 | The new root becomes black | 10B |
| 5 | Parent 10 is black | 10B(5R,-) |
| 15 | Parent 10 is black | 10B(5R,15R) |
| 1 | Parent 5 and uncle 15 are red: recolor both black, then restore the root's black color | 10B(5B(1R,-),15B) |
| 2 | Parent 1 is red, uncle is NIL, and 2 is an inner child: left-rotate 1, then recolor and right-rotate 5 | 10B(2B(1R,5R),15B) |
For the last insertion, the local key order is . The first rotation puts 2 above 1; the second puts it above 5. The repair does not touch the right subtree rooted at 15.
In the final tree, every path after leaving root 10 contains two black occurrences. For example, the path through 2 and 1 counts black 2 and external NIL, while the path through 15 counts black 15 and external NIL. Thus the root's black height is 2. The longest root-to-NIL path has three edges. Equal black height has not forced equal ordinary path lengths.
Worked example 15.2.5
(Inserting 1, 2, 3, 4 in increasing order)
Inserting 1 and 2 gives 1B(-,2R). Inserting 3 meets red parent 2 and an absent uncle, the empty left link of 1, which is black NIL; 3 is an outer child, so color 2 black, color 1 red and left-rotate 1, giving 2B(1R,3R). Inserting 4 meets red parent 3 and red uncle 1: recolor both black and 2 red, then color the root 2 black again, giving 2B(1B,3B(-,4R)). In the fourth insertion recoloring reaches the root, and the black height of the whole tree rises from 1 to 2.
Worked example 15.2.6
(A recoloring followed by a rotation higher up)
Start from the valid tree 20B(10R(5B(2R,7R),15B),30B), and insert 1 as the left child of 2. Parent 2 and uncle 7 are red: color them black and 5 red, and continue with . Its parent 10 is red and its uncle 30 is black, and 5, 10, 20 form a left line: color 10 black, color 20 red and right-rotate 20. The result is 10B(5R(2B(1R,-),7B),20R(15B,30B)).
Counterexample mode
Coloring every new key black does not avoid repair
Start with one black key 10 and its two external leaves. Insert 5 as a black left child. The left path after leaving 10 counts black 5 and black NIL, while the right path counts only black NIL: 2 versus 1.
There is no red-red edge, but the black-count invariant is already broken. The insertion algorithm chooses red to protect the black counts first, then repairs the much more local possible red-red conflict.
Know what this implementation promises
This is an ordered-set insertion algorithm. It does not preserve insertion order, does not by itself provide constant-time access to arbitrary ranks, and does not imply that the stored array or node allocation order is sorted. Inorder traversal supplies sorted key order. A map can update an existing key's associated value without changing the tree shape or colors.
If subtree sizes are added for rank queries, rotations must also refresh those sizes. If deletion is added, removing a black node can change a path's black count; the insertion loop above is not a deletion repair. Likewise, NIL is an external leaf marker, not an ordinary key that comparisons may visit. A shared sentinel saves storage but does not change the mathematical count of external leaf occurrences.
Exercises with solutions
Quick check
(1. Root 8 is black, its left child 4 is red with black NIL children, and its right child is NIL. Is this a red-black tree? What are n, H and the root black height?)
Solution
Yes. Both paths through 4 and the direct right path count exactly one black node after leaving 8: their terminal NIL. There are no adjacent red nodes. Here , and . The left subtree contains a key while the right subtree contains none; equal black count does not mean equal subtree size.
Quick check
(2. Start with black root 10 and red left leaf 5. Insert 7. Specify the uncle, both rotations and the final colors. Why is a single right rotation at 10 insufficient?)
Solution
New node 7 is red, its parent 5 is red, and its uncle is black NIL. This is a left-right triangle. Left-rotate 5, color 7 black and 10 red, then right-rotate 10. The result is black root 7 with red leaf children 5 and 10.
A single right rotation would place 5 above 10, with 7 as 10's left child. Changing only the new root to black would still leave red 10 with red child 7. The inner red node must first be brought into the outer-line configuration. This statement concerns the specified rotation-and-color repair; the ordering-preservation property alone never guarantees valid colors.
Quick check
(3. A valid tree has black root 20, black child 10 and black child 30. Node 10 has red leaves 5 and 15. Insert 1. Show why recoloring 5 and 15 black while leaving 10 black fails; then give the correct final tree.)
Solution
After insertion, 1 is red below red 5, and its uncle 15 is red. If 5 and 15 become black while 10 stays black, the path from 20 through 10 and 5 counts three black occurrences after leaving 20: 10, 5 and NIL. The right path through 30 counts only 30 and NIL, namely two.
Correct repair also colors 10 red. Its parent 20 is black, so the loop stops. The tree is 20B(10R(5B(1R,-),15B),30B). Every root path has black count 2; the red nodes 10 and 1 have black children. No rotation is required.
Quick check
(4. Explain why the at-most-two-rotations bound does not give constant-time insertion, and whether it applies to deletion.)
Solution
The insertion search may inspect a root-to-leaf path of logarithmic length, and red-uncle repairs may recolor nodes on that path. The bound counts only rotations: recoloring can repeat, but the first black-uncle repair finishes after one or two rotations. Total insertion time remains . This proof makes no claim about deletion; removing black nodes requires a separate invariant and repair analysis.