Red-black trees

A red-black tree gives every node one extra bit, a colour, and keeps four rules about the colours. The rules are looser than the AVL rule, so the tree is a little taller, but it needs fewer rotations. Java’s TreeMap and most C++ std::map libraries are red-black trees.

The four rules

Every node is either red or black. The names are just labels for the two values of one bit (in Python, a field red that is True or False). In the figure the colour is shown as a tag, R or B, because this course uses the colour red only for mistakes.

1. Every node is red or black.
2. The root is black.
3. A red node never has a red child.
4. Every path from a node down to a missing child passes the same number of black nodes. A missing child counts as black. This number is the node’s black height.

Step through the first variant of the figure to see each rule on a real tree.

Why the height is O(log n)

First, a subtree whose top has black height b holds at least 2^b − 1 nodes (b twos multiplied together, minus 1). Proof by induction on the height: each child has black height at least b − 1, so by induction holds at least 2^b−1 − 1 nodes, and the two children plus the top give at least 2 · (2^b−1 − 1) + 1 = 2^b − 1.

Second, by rule 3, at least half the nodes on any path down from the root are black. So if the tree has height h, the root has black height at least h/2. Put together: n ≥ 2^h/2 − 1, and taking logarithms:

That is looser than the AVL bound (1.44 log₂ n): for a million keys, a height of up to 39 instead of 28. In practice red-black trees are usually much shorter than the bound.

Insert: recolour or rotate

Insert the key as in a plain search tree, as a red leaf. A red node does not change any black count, so rule 4 still holds. Only two rules can break: rule 2, if the new node is the root, and rule 3, if its parent is red. While the node z and its parent are both red, look at the uncle, the parent’s sibling:

• Uncle red: recolour. Make the parent and the uncle black and the grandparent red. Every path through the grandparent still passes the same number of black nodes. But the grandparent may now be red under a red parent, so repeat from the grandparent, two levels up.
• Uncle black (or missing): rotate. If z is on the inside, first rotate at the parent to move it to the outside (as in the double rotation of BALT-2). Then make the parent black and the grandparent red, and rotate at the grandparent. The parent comes up as a black top over two red children, and the loop ends.

Finally, colour the root black. Step through the second variant to see both cases while inserting 1 to 8.

Cost: the recolour case moves two levels up each time, so it runs at most O(log n) times, and the rotate case happens at most once. So an insert is O(log n) with at most two rotations. A delete has more cases but also needs at most three rotations.

A shorter version

The rules above leave many cases. Robert Sedgewick’s left-leaning red-black tree (2008) adds one more rule, a red node is always a left child, and the insert becomes three checks on the way back up a recursive insert:

def is_red(node):
    return node is not None and node.red

# inside the recursive insert, after inserting below node:
if is_red(node.right) and not is_red(node.left):
    # a red link leans right: turn it left
    node = rotate_left(node)
if is_red(node.left) and is_red(node.left.left):
    node = rotate_right(node)  # two reds in a row on the left
if is_red(node.left) and is_red(node.right):
    flip_colours(node)  # children black, node red
return node

Here a rotation also passes the colour: the node that comes up takes the old top’s colour, and the old top becomes red. flip_colours makes both children black and the node red. New nodes are red, and the outer function colours the root black at the end. The result obeys all four rules, so practice BALT-P4 accepts it, or any other correct red-black insert.

AVL or red-black?

Both are O(log n) for every job. AVL trees are a little shorter, so searches are a little faster. Red-black trees change less on delete. That suits libraries, where updates are frequent and other data may point into the tree.