Red-black tree rules and the height bound in Python

Why this matters

An earlier lesson in this module showed that a plain binary search tree (BST) turns into a chain when keys arrive in sorted order. A chain of 100000 keys is 100000 nodes tall, so one search can visit every key in the tree. A balanced tree holding the same keys has a height of about 17, so a search visits about 17 nodes.

A red-black tree is a BST that keeps its height small while you insert and delete. Each node stores one extra label, its colour, which is either red or black. A few rules about the colours force the tree to stay roughly balanced. Java's TreeMap and TreeSet use this design. Python's standard library does not include a red-black tree, so this lesson checks the rules with Python code and explains the height bound with a proof.

This lesson does three things. It states the rules. It checks small trees against them with a Python program. It shows why the rules limit the height. It does not explain how an insert or a delete repairs the colours after a change, and it does not repeat the rotations from the AVL lessons in this module.

A tree that can get tall

Insert the keys 1 to 7 into a plain BST, in that order. Key 1 becomes the root. Key 2 is bigger than 1, so it goes to the right of 1. Key 3 is bigger than both, so it goes to the right of 2. Each new key goes one level deeper than the one before it. After seven inserts the height is 7, and a search for 7 takes seven steps.

Now arrange the same seven keys differently. Put 4 at the root, 2 and 6 as its children, and 1, 3, 5 and 7 on the bottom row. The height is 3. A search for any key takes at most three comparisons.

A red-black tree is a way of making sure the tree stays close to the second picture, whatever order the keys arrive in. The colours are the tool that makes this possible.

The five colour rules

The rules are the whole definition. A tree is a red-black tree when every rule below is true for every node in it.

1. Every node is red or black.
2. The root is black.
3. Every empty spot is black. An empty spot is the place where a child would go when a node has no child there. In Python it is the value None. Many textbooks call it a nil leaf.
4. A red node has two black children. Empty spots count as black, so a red node with no children is allowed. Put another way, no path down the tree has two red nodes in a row.
5. Every path from a node down to an empty spot passes through the same number of black nodes.

Rule 5 needs a name. The black height of a node is the number of black nodes on any path from that node down to an empty spot. The node itself counts if it is black. The empty spot does not count. Rule 5 says that every path from one node gives the same count, so each node has exactly one black height.

Rule 5 also applies to nodes with only one child. A node with one child has an empty spot on its other side, and that empty spot's path has no black nodes below the node. Many beginners miss this case, and the mistakes section shows what it looks like.

First example: checking a tree by hand

Here is a small tree with four keys. The root is 20, and it is black. Its left child is 10, black. Its right child is 30, black. The right child of 30 is 40, red.

Check each rule in turn.

• Rules 1 and 2: every node is red or black, and the root 20 is black.
• Rule 3: the empty spots are all black by definition, so there is nothing to check.
• Rule 4: the only red node is 40. Its two children are empty spots, which count as black. The rule holds.
• Rule 5: write down every path from 20 to an empty spot.
  • 20, then 10, then the empty spot on the left of 10. Black nodes: 20 and 10. Count: 2.
  • 20, then 30, then the empty spot on the left of 30. Black nodes: 20 and 30. Count: 2.
  • 20, then 30, then 40, then the empty spot on the right of 40. Black nodes: 20 and 30. The node 40 is red. Count: 2.

All three counts are 2, so the tree is valid.

Checking by hand works for four keys. It stops working when the tree has a hundred nodes. The program below does the same walk for you. It goes from the bottom of the tree upwards. For each node it asks the left side and the right side for their black heights, and it compares the two numbers. It reports a problem when they differ. It also reports a red node whose parent is red, and a red root. The program builds the example above first, then six more trees, so you can see what a valid tree and several broken trees look like.

The output is:

example: valid
red-red: 2 problem(s)
  - red node 5 has red parent 10
  - node 20: left side has 0 black nodes, right side has 1
unequal: 1 problem(s)
  - node 30: left side has 0 black nodes, right side has 1
red-root: 1 problem(s)
  - root is red
one-child: 1 problem(s)
  - node 2: left side has 1 black nodes, right side has 0
seven keys: valid
five keys: valid

The "example" tree passes, as the hand check said. The "red-red" tree fails rule 4, because the red node 5 sits under the red node 10. It also fails rule 5, because the left side of 20 has no black nodes and the right side has one. The "unequal" tree fails only rule 5. The "red-root" tree fails rule 2. The "one-child" tree fails rule 5 on its one-child node. The last two trees are the seven-key and five-key trees from the next two sections, and both pass.

The program reports each problem once, as a message. The numbers in the messages are black heights, but they do not count the node named in the message. In "one-child", the node 2 has a black left child 1, so its left side has one black node, and its right side is an empty spot with zero.

Second example: the seven-key tree

The tree called "seven keys" in the program is the balanced picture from the first section. The root 4 is black. Its children 2 and 6 are black. Their children 1, 3, 5 and 7 are black. Every node is black, so rule 4 has nothing to check, and every path from 4 to an empty spot passes through three black nodes.

Rule 5 holds because the tree is full. Every path has the same length, and every node is black. A full tree of black nodes with seven nodes has a black height of 3, and its height is also 3.

This tree is the best case. Real red-black trees are rarely full, and they are allowed to have red nodes, which is why the rules exist.

Third example: a tree with red nodes

The "five keys" tree is less neat, and it shows what red nodes do. The root 2 is black with a black left child 1. Its right child is 4, which is red. Node 4 has two black children, 3 and 5.

Check rule 4 first. The only red node is 4. Its children 3 and 5 are black, so the rule holds. Now rule 5. The path 2, then 1, then the empty spot has two black nodes, 2 and 1. The path 2, then 4, then 3, then the empty spot has two black nodes, 2 and 3, because 4 is red. The path 2, then 4, then 5, then the empty spot also has two black nodes.

The tree has five keys and a height of 3. A tree with five keys cannot be shorter than 3, so this tree has the best possible height. The red node 4 adds no black node to the paths through it, so the black counts still match.

Why the rules keep the height low

Here is the key idea in plain words. Every path from the root to an empty spot has the same number of black nodes, which is the root's black height. Call that number b. The question is how long a path can get when it has b black nodes in it.

The first step is that a path can have at most b red nodes. The root is black by rule 2. Every red node has a parent, and by rule 4 that parent is black. Two different red nodes on the same path have two different parents, because a path goes through one node at each level. So the number of red nodes on a path is at most the number of black nodes on it. A path therefore has at most b black nodes and b red nodes, which makes at most 2b nodes in total.

The second step is that a tree with black height b must have many nodes. Here is the claim. A node whose black height is c has at least 2 to the power c, minus 1, nodes in its subtree. For c equal to 1 the claim says at least 1 node. For c equal to 2 it says at least 3 nodes, and for c equal to 3 it says at least 7 nodes.

The claim is proved from the bottom up. An empty spot has black height 0 and holds 0 nodes, and 2^0 - 1 is 0, so the claim holds there. Now take any node x with black height c. Both of its children have the same black height, because of rule 5. If x is black, each child has black height c - 1, so by the claim each child's subtree holds at least 2^(c-1) - 1 nodes. Add x itself, and the subtree of x holds at least 1 + 2 * (2^(c-1) - 1), which is 2^c - 1. If x is red, each child is black and has black height c, so the subtree of x holds at least 1 + 2 * (2^c - 1), which is more than 2^c - 1. Either way the claim holds.

Put the two steps together. A tree with n nodes has a black height b with n >= 2^b - 1. So b is at most the base-2 logarithm of n + 1. The base-2 logarithm of a number is how many times you must halve the number to reach 1. For example, the base-2 logarithm of 8 is 3, because 8 halved three times is 1. The logarithm of 1000 is about 10, because 2 to the power 10 is 1024.

Now combine the bound on the path length with the bound on the black height. The height of the tree is at most 2b, and b is at most the base-2 logarithm of n + 1. So the height of a red-black tree is at most 2 * log2(n + 1). This is the height bound.

Here are three numbers that make it concrete.

• With 7 keys, the bound is 2 times 3, which is 6. The full tree from the second example has height 3, which is inside the bound.
• With 1000 keys, the bound is about 19.9, so the height is at most 19.
• With 100000 keys, the bound is about 33.2, so the height is at most 33.

A plain BST gives no such bound. The same 100000 keys in sorted order give a plain BST height of 100000.

Measuring the height of a balanced tree

Python's standard library has no red-black tree, so there is no built-in tree to measure for this lesson. The next best thing is a self-balancing tree that you can read. The AVL tree from the AVL rotations lesson keeps a different rule, a height difference of at most 1 at every node, and it is also far shorter than a plain BST on sorted input.

Insert the keys 1 to 100000 in sorted order with the insert function from that lesson. Then read the height of the root:

root = None
for k in range(1, 100001):
    root = insert(root, k)
print(root.height)

The output is:

17

The AVL tree has 100000 entries and a height of 17. A plain BST given the same keys would have height 100000. The AVL bound is about 1.44 times log2 n, which is about 24 for 100000 keys, so 17 is inside it. The red-black bound from this lesson is about 33 for the same number of keys. A red-black tree is allowed to be taller than an AVL tree, because its rule is looser, and that is the trade-off the AVL lesson describes.

The number 17 is a measured result for these keys in this order. It is not a promise. Another order of the same keys can give a different shape, and a red-black tree could report a different height.

Where languages use them

The idea appears in many libraries, because a balanced tree gives guaranteed logarithmic time for search, insert and delete.

• Java: TreeMap and TreeSet are red-black trees. TreeSet is built on top of TreeMap.
• C++: std::map and std::set must meet a logarithmic time limit. Common standard library implementations meet it with red-black trees. The language standard asks for the time limit, not for a particular tree.
• Linux: the kernel has its own red-black tree code, which kernel subsystems use for ordered collections of items.

Not every ordered collection is red-black. An AVL tree uses a height difference rule instead of colours. A B-tree keeps many keys in each node, which suits disks. A hash table is faster on average for lookups by exact key, but it does not keep keys in order, so it cannot answer questions such as the smallest key above a value. In Python, a dictionary is a hash table, and the bisect module (binary search on a sorted list) answers the ordered questions for small data.

Common mistakes

Mistake one: thinking rule 5 only applies to nodes with two children. A node with one child fails when the black counts differ. The program's "one-child" tree shows the message you will see:

node 2: left side has 1 black nodes, right side has 0

The fix is to see the empty spot as a path with zero black nodes below the node. Then the counts on both sides can be compared the same way as for any other node.

Mistake two: forgetting that a red node cannot have a red child. The message looks like this:

red node 5 has red parent 10

The checker names the child, not the parent, because it reports the problem when it reaches the red child and looks at the node above it. Read the message as "node 5 is red and sits under a red node 10". The fix is to recolour one of them black, or to restructure the tree. This lesson does not show the restructuring.

Mistake three: thinking the root can be red. The root must be black, so a red root is a rule break even when the rest of the tree is valid. The checker reports this as root is red.

Mistake four: treating the height bound as a promise of perfect balance. The bound says the height is at most about twice the ideal. With 1000 keys the ideal height is about 10, and the bound allows 19. A red-black tree may be taller than the ideal, and it still stays inside the bound.

Mistake five: thinking the colour checker proves the tree is a correct search tree. The checker in this lesson looks only at colours. It does not check that the keys are in order, with every key in the left subtree smaller than its node and every key in the right subtree bigger. A tree can pass the colour rules and still give wrong search results. The lesson on validating a BST covers the key order check, and a real red-black checker needs both checks.

Practice

Exercise 1. Here is a tree. The root 8 is black. Its left child 4 is red. Node 4 has a left child 2, which is black, and no right child. The right child of 8 is 12, black. Is this a valid red-black tree? Say which rule fails, and give the two numbers that show it.

Show the answer

It is not valid. Rule 4 holds, because the only red node 4 has black children (2 and an empty spot). Rule 5 fails at node 4. Its left side has one black node, which is 2, and its right side is an empty spot with zero black nodes. The checker prints node 4: left side has 1 black nodes, right side has 0.

Exercise 2. Build a valid red-black tree with the keys 1, 2, 3 and 4. Use 2 as the root, 1 as its left child, 3 as its right child, and 4 as the right child of 3. Choose the colours so that all five rules hold, and check each path by hand.

Show the answer

Colour 2 black, 1 black, 3 black, and 4 red. Node 4 is red, and its two children are empty spots, so rule 4 holds. The path 2, then 1, then an empty spot has two black nodes. The path 2, then 3, then an empty spot has two black nodes. The path 2, then 3, then 4, then an empty spot also has two black nodes, because 4 is red. All paths give 2, so rule 5 holds. The checker finds no problems in this tree.

Exercise 3. A three-key tree has 2 as a red root, with 1 black on the left and 3 black on the right. Is it valid? If not, what is the smallest change that makes it valid?

Show the answer

It is not valid, because rule 2 says the root must be black. Recolouring 2 black is enough. Then the path 2, then 1, then an empty spot has two black nodes, and the path 2, then 3, then an empty spot also has two black nodes. Both sides agree, so the tree is valid. The checker prints root is red for the tree before the change.

Exercise 4. A red-black tree holds 1023 keys. What is the largest height it can have? Use the bound from this lesson, and give the reasoning in one or two sentences.

Show the answer

The black height b is at most the base-2 logarithm of 1024, which is 10. The height is at most 2 times b, which is 20. A perfect tree with 1023 nodes has height 10, so the bound allows twice that.

Exercise 5. A plain BST receives the keys 1 to 100000 in order, and so does the AVL insert in this lesson. What height does the plain BST end with, and why is it different from the 17 that the AVL tree reports?

Show the answer

The plain BST ends with height 100000. Each key is bigger than all the keys before it, so each one goes to the right of the last, and the tree is a single chain. The AVL tree uses its rotations to keep the height at 17, which is inside its bound of about 24. The rotations after each insert are what change the shape.

Summary

• A red-black tree is a BST where each node is red or black, and five rules about the colours hold for every node.
• Rule 4 says a red node has black children, and rule 5 says every path from a node to an empty spot has the same number of black nodes.
• A path has at most as many red nodes as black nodes, so its length is at most twice the black height.
• A tree with black height b has at least 2 to the power b, minus 1, nodes, so the height is at most 2 * log2(n + 1).
• Java's TreeMap and TreeSet use red-black trees. Python's standard library does not, so this lesson uses the AVL tree from the previous lesson for the measured example, which gives a height of 17 for 100000 sorted keys.
• The rules check colours only, so a complete check also needs the key order.