AVL trees keep a strict balance and therefore rotate often. A red-black tree relaxes the condition: every node gets a colour, and a few rules about colours guarantee that the longest path is at most twice as long as the shortest one. The height is then at most 2 · log2(n+1), and inserts and deletes need very few rotations.

A red-black tree of seven nodes: every path has two black nodes
A red-black tree of seven nodes: every path has two black nodes

The five rules

  1. Every node is red or black.
  2. The root is black.
  3. Empty leaves (None) count as black.
  4. A red node has only black children: two reds never stand in a row.
  5. From any node, all paths down to the leaves contain the same number of black nodes (the black height).

Why does this bound the height? The shortest path has only black nodes, the longest alternates black and red (rule 4), and by rule 5 both have the same number of black nodes. So the height is at most 2 · bh, and a tree with black height bh has at least 2^bh - 1 nodes. Hence h ≤ 2 · log2(n+1).

Checking the rules in code

python
RED, BLACK = "R", "B"

class Node:
    def __init__(self, key, color, left=None, right=None):
        self.key = key
        self.color = color
        self.left = left
        self.right = right

def is_red(n):
    return n is not None and n.color == RED