AVL-деревья держат строгий баланс и потому часто вращаются. Красно-чёрное дерево смягчает условие: каждый узел получает цвет, а несколько правил о цветах гарантируют, что самый длинный путь не больше чем вдвое длиннее самого короткого. Высота тогда не превышает 2 · log2(n+1), а вставка и удаление требуют совсем немного поворотов.

Красно-чёрное дерево из семи узлов: на каждом пути по два чёрных узла
Красно-чёрное дерево из семи узлов: на каждом пути по два чёрных узла

Пять правил

  1. Каждый узел красный или чёрный.
  2. Корень чёрный.
  3. Пустые листья (None) считаются чёрными.
  4. У красного узла дети только чёрные: два красных подряд не бывает.
  5. От любого узла до листьев на всех путях одинаковое число чёрных узлов (чёрная высота).

Почему это ограничивает высоту? Кратчайший путь состоит только из чёрных узлов, длиннейший чередует чёрные и красные (правило 4), а по правилу 5 чёрных на обоих одинаково. Значит, высота не больше 2 · bh, а дерево с чёрной высотой bh содержит не менее 2^bh - 1 узлов. Отсюда h ≤ 2 · log2(n+1).

Проверка правил в коде

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