Red-black tree rules and the height bound

Why this matters

A binary search tree is fast only while it stays short. The AVL tree lesson in this module showed one way to keep it short: check the heights after each change and rotate when one side becomes too tall. A red-black tree uses a different method. Each node gets a colour, either red or black, and four simple rules about the colours keep the tree short. The colours never store a height. The rules do the work.

Red-black trees sit behind std::map and std::set in the GCC version of the C++ standard library, and behind TreeMap in Java. If you use either container, you use a red-black tree. Interviewers also ask about the rules, often as "why can a red node never have a red child?"

This lesson states the rules, checks them with a C++ program that reports the first broken rule, and then shows the argument for the height bound with a concrete tree. It does not teach the insert and delete procedures in full. Those procedures recolour nodes and rotate them until the rules hold again, and they are long enough to deserve their own lesson.

The problem the colours solve

An AVL tree keeps the heights of the two sides of each node within one level of each other. The lesson on sorted input showed that inserting sorted values into a plain binary search tree builds a chain, with height equal to the number of nodes. A chain of 1,000 nodes takes 1,000 steps to search, while a balanced tree takes about 10.

The colour rules are a looser kind of balance. They allow one side of a node to be a little taller than the other, but they limit how much taller. That limit is enough to keep the height proportional to the logarithm of the number of nodes.

A logarithm here means the number of times you can halve a count before reaching 1. The base-2 logarithm of 1,000 is about 10, because 2 to the power 10 is 1,024. Write it log2 n.

The four colour rules

Every node in a red-black tree has one extra piece of data, its colour. A colour is either red or black. The tree also has empty spots, the places where a child would be if there were no child. Programmers call an empty spot a null child. In this lesson, null means an empty spot.

A red-black tree must follow four rules:

1. Every node is red or black.
2. The root is black.
3. A red node has only black children. Two red nodes cannot be next to each other on a path from the root.
4. Every path from the root down to a null spot contains the same number of black nodes.

The fourth rule does most of the work. Pick any path from the root to a null spot and count the black nodes on it. Every such path must give the same count. That count is called the black height of the tree.

Here is a small tree that follows all four rules. The number 1 is red, and every other node is black.

        4 (black)
       /        \
  2 (black)    6 (black)
     /
  1 (red)

Check the paths. The path 4, 2, 1, null has two black nodes, 4 and 2. The path 4, 2, null has two black nodes. The path 4, 6, null has two black nodes. The black height is 2.

Now change node 1 to black. The path 4, 2, 1, null now has three black nodes, while the path 4, 2, null still has two. Rule 4 is broken. Change node 1 to red and add a red node 0 below it, and rule 3 is broken, because a red node now has a red child.

Two facts follow from the rules. The root is black, so the black height of the tree is at least 1 whenever the tree has a node. Also, the colours do not decide the order of the keys. The keys still follow the binary search tree rule, which is separate from the colour rules.

Checking the rules with a C++ program

The program below builds small trees by hand and checks them. It stores each node with std::unique_ptr. A std::unique_ptr is a C++ smart pointer. It owns a node and frees it automatically when the owner goes away, so the program has no delete calls.

The core function is black_height. It returns the black height of a subtree as a std::optional<int>, which either holds an int or holds nothing. When a rule breaks, the function writes a short message into error and returns nothing.

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <memory>
#include <optional>
#include <string>
 
enum class Color { Red, Black };
 
struct Node {
    int key;
    Color color;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
 
    Node(int k, Color c, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr)
        : key(k), color(c), left(std::move(l)), right(std::move(r)) {}
};
 
using NodePtr = std::unique_ptr<Node>;
 
NodePtr make(int key, Color color, NodePtr left = nullptr, NodePtr right = nullptr) {
    return std::make_unique<Node>(key, color, std::move(left), std::move(right));
}
 
// Counts the black nodes on any path from this node down to a null spot.
// Returns nullopt and fills in `error` when a rule is broken.
std::optional<int> black_height(const Node* n, std::string& error) {
    if (n == nullptr) {
        return 0;
    }
    if (n->color == Color::Red) {
        for (const Node* child : {n->left.get(), n->right.get()}) {
            if (child != nullptr && child->color == Color::Red) {
                error = "red node " + std::to_string(n->key) + " has red child " + std::to_string(child->key);
                return std::nullopt;
            }
        }
    }
    auto left = black_height(n->left.get(), error);
    if (!left) {
        return std::nullopt;
    }
    auto right = black_height(n->right.get(), error);
    if (!right) {
        return std::nullopt;
    }
    if (*left != *right) {
        error = "black heights differ at node " + std::to_string(n->key) + ": " + std::to_string(*left) +
                " on the left, " + std::to_string(*right) + " on the right";
        return std::nullopt;
    }
    return *left + (n->color == Color::Black ? 1 : 0);
}
 
bool is_valid(const Node* root, std::string& error) {
    if (root != nullptr && root->color != Color::Black) {
        error = "root is red";
        return false;
    }
    return black_height(root, error).has_value();
}
 
int height(const Node* n) {
    if (n == nullptr) {
        return 0;
    }
    return 1 + std::max(height(n->left.get()), height(n->right.get()));
}
 
int count(const Node* n) {
    if (n == nullptr) {
        return 0;
    }
    return 1 + count(n->left.get()) + count(n->right.get());
}
 
// Builds a valid tree with black height b and the largest height that the rules allow.
NodePtr stretched(int b) {
    if (b == 0) {
        return nullptr;
    }
    NodePtr red_left = make(0, Color::Red, stretched(b - 1), stretched(b - 1));
    NodePtr right = stretched(b - 1);
    return make(0, Color::Black, std::move(red_left), std::move(right));
}
 
int main() {
    std::cout << "Valid tree with 7 nodes\n";
    NodePtr perfect = make(4, Color::Black,
                           make(2, Color::Black, make(1, Color::Black), make(3, Color::Black)),
                           make(6, Color::Black, make(5, Color::Black), make(7, Color::Black)));
    std::string error;
    std::cout << "  valid: " << std::boolalpha << is_valid(perfect.get(), error) << "\n\n";
 
    std::cout << "Broken tree: a red node with a red child\n";
    NodePtr red_red = make(4, Color::Black,
                           make(2, Color::Red, make(1, Color::Red), make(3, Color::Black)),
                           make(6, Color::Black));
    error.clear();
    std::cout << "  valid: " << is_valid(red_red.get(), error) << "\n";
    std::cout << "  error: " << error << "\n\n";
 
    std::cout << "Broken tree: one path has more black nodes than another\n";
    NodePtr uneven = make(4, Color::Black, make(2, Color::Black, make(1, Color::Black)), make(6, Color::Black));
    error.clear();
    std::cout << "  valid: " << is_valid(uneven.get(), error) << "\n";
    std::cout << "  error: " << error << "\n\n";
 
    std::cout << "Stretched valid trees, with n nodes and height h\n";
    std::cout << "  b  n   h  2*log2(n+1)  valid\n";
    for (int b = 1; b <= 4; ++b) {
        NodePtr tree = stretched(b);
        error.clear();
        int n = count(tree.get());
        std::cout << "  " << std::setw(1) << b << "  " << std::setw(2) << n << "  " << std::setw(2) << height(tree.get())
                  << "  " << std::setw(11) << std::fixed << std::setprecision(2) << 2.0 * std::log2(n + 1) << "  "
                  << is_valid(tree.get(), error) << "\n";
    }
    return 0;
}

Compile it with the warnings turned on and run it:

g++ -std=c++20 -Wall -Wextra -o rb_check rb_check.cpp && ./rb_check

The output is:

Valid tree with 7 nodes
  valid: true
 
Broken tree: a red node with a red child
  valid: false
  error: red node 2 has red child 1
 
Broken tree: one path has more black nodes than another
  valid: false
  error: black heights differ at node 2: 1 on the left, 0 on the right
 
Stretched valid trees, with n nodes and height h
  b  n   h  2*log2(n+1)  valid
  1   2   2         3.17  true
  2   8   4         6.34  true
  3  26   6         9.51  true
  4  80   8        12.68  true

Read the first broken case. Node 2 is red and its left child, node 1, is also red. The checker stops at the first rule it finds and reports it. The second broken case has no red nodes. Node 2 has a black left child and an empty right side. The left side counts one black node and the empty right side counts zero, so the message says the black heights differ at node 2.

The checker counts an empty spot as zero black nodes. It does not count the empty spot itself. Both conventions give the same answer for rule 4, as long as you use the same one everywhere. Textbooks often count the empty spots as black. This lesson does not, to keep the numbers small.

The table at the end is the main result. Its columns are the black height b, the node count n, the height h in nodes, the bound 2*log2(n+1), and whether the rules hold. The function stretched builds a tree for each black height. Its root is black, its left child is red with two smaller stretched trees below it, and its right child is a smaller stretched tree. The program confirms that each tree is valid. The next section explains why the height grows the way it does.

Why the rules keep the tree short

The argument has two steps. First, the rules limit the height of a tree to twice its black height. Second, the rules force the black height to be small compared with the number of nodes.

Step 1: a height limit from the black height

Take any path from the root to a null spot. The root is black, and the path cannot have two red nodes in a row, by rule 3. So each red node on the path is followed by a black node, or it is the last node before the null spot. Each red node can be matched with the black node that comes just before it on the path, and no black node is matched twice. So the number of red nodes is at most the number of black nodes.

By rule 4, every path has the same number of black nodes, the black height b. The red nodes on the path are at most b. So the whole path has at most 2b nodes. The height of the tree is at most 2b.

Step 2: a size limit from the black height

Claim: a node whose paths to null spots each have k black nodes has at least 2 to the power k, minus 1, black nodes in its subtree. Write this as 2^k - 1.

Proof by counting. An empty spot has k = 0 and holds 0 black nodes, and 2^0 - 1 = 0, so the claim holds there.

Now take a node with black height k below it.

• If the node is black, its children each have black height k - 1. By the claim, each child subtree has at least 2^(k-1) - 1 black nodes. The node itself adds one, so the total is at least 1 + 2 times (2^(k-1) - 1), which equals 2^k - 1.
• If the node is red, its children each have black height k. Each child subtree has at least 2^k - 1 black nodes, so the total is at least 2 times (2^k - 1). Since 2^k - 1 is zero or more, twice that is at least 2^k - 1.

So the claim holds for every node. The root is black, and its black height is b, so the tree has at least 2^b - 1 black nodes, and therefore at least 2^b - 1 nodes in total.

Putting the two steps together

With n nodes, we have n ≥ 2^b - 1. Adding one to both sides and taking the base-2 logarithm gives b ≤ log2(n+1). The height is at most 2b, so:

height ≤ 2 × log2(n+1)

For a concrete value, take n = 80. The bound is 2 × log2(81), which is about 12.68. So a valid tree with 80 nodes can have a height of at most 12.

The program's table shows a tree that reaches much of that limit. For black height 4, the stretched tree has 80 nodes and height 8. A perfectly balanced tree with 80 nodes has height 7, because six levels hold only 63 nodes and seven levels hold 127. The stretched tree is taller than that, but it stays inside the bound, and no valid tree can go past the bound.

The table also shows the pattern. Each extra black level adds about three times as many nodes and two levels of height. The height grows with the logarithm of the node count, not with the node count itself.

A worked example: tracing the eight-node tree

The function stretched(2) builds a tree with eight nodes. Written as an indented list, with R for red and B for black, it looks like this:

root  B
  left  R
    left  B
      left  R
    right  B
      left  R
  right  B
    left  R

Trace each path from the root to an empty spot. Count the black nodes on each path, the same way rule 4 does:

Every path has two black nodes, so rule 4 holds. The longest path has four nodes, and it has two red nodes. Each red node is followed by a black node or an empty spot, so rule 3 holds. The height of the tree is 4, which is twice the black height of 2. The program prints the same numbers in its table: 8 nodes, height 4, bound 6.34.

A perfectly balanced tree with 8 nodes also has height 4, so this example is no taller than a balanced tree. The gap appears at larger black heights, as the table at the end of the program shows.

What the rules give up

Red-black trees are not the tightest possible balance. An AVL tree keeps the two sides of each node within one level of each other, and its height is at most about 1.44 log2 n. A red-black tree allows the height to reach 2 log2(n+1), which is larger.

The trade-off is in the updates. An AVL delete can need a rotation at many levels on the way back up. A red-black delete needs at most three rotations, and an insert needs at most two. Lookups are a little slower in the worst case, while inserts and deletes do less restructuring. Many library containers choose this trade-off.

Where red-black trees are used

• The GCC version of the C++ standard library uses a red-black tree for std::map and std::set. Its header bits/stl_tree.h defines the two colours as _S_red and _S_black. You can find the header in the include folder of your GCC installation.
• Java's TreeMap uses a red-black tree, and TreeSet is built on top of TreeMap. The class has private constants named RED and BLACK, which you can see with javap -p java.util.TreeMap on a Java installation.
• The Linux kernel has its own red-black tree code in lib/rbtree.c, and kernel subsystems use it to keep ordered collections of objects.

These containers use the colour rules, with recolouring plus at most a few rotations per change.

Common mistakes

Checking the heights instead of the black count. Rule 4 is about black nodes, not heights. The tree in the example above has a path of four nodes through 1 and a path of three nodes through the empty right side of 2, and it is still valid, because both paths have two black nodes.

Forgetting the empty spots. A checker that only looks at real nodes misses the case where one side of a node is empty and the other side is not. The program above treats an empty spot as zero black nodes, which is why it reports the second broken tree.

Colouring the root red. Rule 2 is easy to forget when you write the insert procedure, because the new node is often red. After an insert, the code must colour the root black. The checker reports this case with the message root is red.

Copying a std::unique_ptr. A std::unique_ptr cannot be copied, only moved. This line causes a compiler error:

auto b = a;  // a is a std::unique_ptr<Node>

GCC 15 reports it like this:

error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]'

The fix is auto b = std::move(a);, or a function that returns the node and gives ownership to the caller.

Reading a member of an empty spot. A null pointer has no node behind it. If the checker reads n->color when n is null, the program crashes. With the sanitizers turned on (-fsanitize=address,undefined), the program prints a message such as:

runtime error: member access within null pointer of type 'const struct Node'

The fix is to return early when the pointer is null, as the checker does at the top of black_height.

Practice

Exercise 1. Is this tree valid? The root is 10, black. Its left child, 5, is red. Its right child, 20, is black. Both children of 5 are null, and both children of 20 are null.

Show the answer

No. The path 10, 5, null has one black node, 10. The path 10, 20, null has two black nodes, 10 and 20. Rule 4 is broken. The checker would report "black heights differ at node 10".

Exercise 2. Start from the four-node tree in the section on the colour rules: 4 black, with 2 black and 6 black below it, and 1 red below 2. Add the node 3 as a red right child of 2. Is the tree still valid?

Show the answer

Yes. The red node 3 has only null children, so rule 3 holds. The path 4, 2, 3, null has two black nodes, 4 and 2. The path 4, 2, 1, null also has two. The path 4, 6, null has two. Every path still has the same count, so rule 4 holds.

Exercise 3. What is the smallest number of nodes in a valid red-black tree with black height 3?

Show the answer

Seven nodes. The bound says that n is at least 2^b - 1, which is 2^3 - 1 = 7 for b = 3. A perfect tree with seven black nodes has three black nodes on every path, so the bound is reached. Six nodes cannot do it, because the bound requires at least 7.

Exercise 4. A valid red-black tree has 15 nodes. What is the largest height the rules allow?

Show the answer

The bound is height at most 2 × log2(15 + 1), which is 2 × log2(16), which is 2 × 4 = 8. The bound is not always reached. Checking every valid shape with 15 nodes gives heights from 4 to 6, so the largest height the rules allow for 15 nodes is 6. A tree with 15 nodes and all black nodes has height 4, and red nodes let it grow to 6.

Exercise 5. Change the loop in the program so that it prints black heights 1 to 5 instead of 1 to 4. What is the row for black height 5?

Show the answer

The row has the same columns as the table above: black height 5, 242 nodes, height 10, bound 15.85, valid true. The stretched tree for black height 5 has a red left child with two stretched trees of black height 4 below it, plus a right stretched tree of black height 4. That gives 2 + 3 × 80 = 242 nodes and height 2 + 8 = 10. The bound is 2 × log2(243), which is about 15.85.

Summary

• A red-black tree is a binary search tree where each node is red or black, and four colour rules hold.
• Rule 4 says every path to a null spot has the same number of black nodes. That number is the black height.
• Rule 3 says a red node has only black children, so a path has at most as many red nodes as black nodes.
• A tree with black height b has at least 2^b - 1 nodes, so the black height is at most log2(n+1).
• The height is at most 2 × log2(n+1), which is larger than an AVL tree's bound but cheaper to keep during updates.