Красно-чёрное дерево: правила, балансировка и где применяется

Коротко

Красно-чёрное дерево — самобалансирующееся дерево поиска, которое стоит внутри std::map в C++, TreeMap в Java и HashMap при большом числе коллизий.

Идея: баланс через цвет

АВЛ-дерево хранит в каждом узле высоту и держит строгий баланс. Красно-чёрное поступает хитрее — хранит один бит (цвет) и держит баланс приблизительный.

Приблизительный баланс дешевле поддерживать: часто достаточно перекрасить узлы, не двигая их. А гарантия O(log n) при этом сохраняется.

Пять правил

1. Каждый узел либо красный, либо чёрный.
2. Корень всегда чёрный.
3. Все листья (фиктивные NIL-узлы) чёрные.
4. У красного узла оба ребёнка чёрные — то есть два красных узла не могут идти подряд.
5. Для любого узла все пути от него до листьев содержат одинаковое число чёрных узлов.

Пятое правило — главное. Оно называется «чёрной высотой» и именно оно даёт гарантию баланса.

        10(ч)
       /     \
    5(к)     15(к)
    /  \     /   \
  3(ч) 7(ч) 12(ч) 20(ч)

Проверим: от корня до любого листа ровно два чёрных узла (сам узел и лист). Красные узлы не имеют красных детей. Правила соблюдены.

Почему высота не больше 2·log n

Рассуждение простое и его любят на собеседованиях.

Пусть чёрная высота дерева равна bh. Из правила 5 все пути содержат bh чёрных узлов. Из правила 4 красных узлов на пути не может быть больше, чем чёрных — они не идут подряд.

Значит, длина любого пути не превышает 2·bh. При этом поддерево с чёрной высотой bh содержит минимум 2^bh − 1 узлов. Отсюда

n ≥ 2^bh − 1   ⟹   bh ≤ log₂(n + 1)
высота ≤ 2·bh ≤ 2·log₂(n + 1)

То есть дерево может быть вдвое выше идеального — но не больше. Для миллиона элементов это 40 уровней вместо 20. Хуже АВЛ, но всё ещё логарифм.

Как чинится баланс при вставке

Новый узел всегда добавляется красным. Так он не меняет чёрную высоту и не нарушает правило 5. Но может нарушить правило 4, если его родитель тоже красный.

Дальше всё зависит от цвета «дяди» — брата родителя.

Случай 1: дядя красный — перекрашиваем

      дед(ч)                 дед(к)
      /    \                 /    \
  отец(к) дядя(к)   ──►  отец(ч) дядя(ч)
    /                      /
 новый(к)               новый(к)

Родителя и дядю красим в чёрный, деда в красный. Никаких поворотов, только цвета. Проблема могла подняться на уровень выше — повторяем проверку для деда.

Это самый частый случай, и он бесплатный по сравнению с поворотами. Именно поэтому красно-чёрное дерево быстрее вставляет, чем АВЛ.

Случай 2: дядя чёрный — поворот

Здесь перекраска не спасает, нужен поворот — одинарный или двойной, в зависимости от взаимного расположения узлов. Логика та же, что в АВЛ-дереве.

Важное свойство: поворотов при вставке не больше двух, независимо от размера дерева. В АВЛ их может понадобиться до O(log n).

Набросок реализации

Полная реализация с удалением занимает несколько сотен строк — удаление в красно-чёрном дереве считается одним из самых муторных алгоритмов в структурах данных. Приведу вставку, чтобы показать логику.

RED, BLACK = True, False


class Node:
    __slots__ = ('key', 'color', 'left', 'right', 'parent')

    def __init__(self, key, color=RED) -> None:
        self.key = key
        self.color = color
        self.left = self.right = self.parent = None


class RedBlackTree:
    def __init__(self) -> None:
        self.NIL = Node(None, BLACK)      # общий фиктивный лист
        self.root = self.NIL

    def _rotate_left(self, x: Node) -> None:
        y = x.right
        x.right = y.left
        if y.left is not self.NIL:
            y.left.parent = x

        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y

        y.left = x
        x.parent = y

    def _rotate_right(self, x: Node) -> None:
        y = x.left
        x.left = y.right
        if y.right is not self.NIL:
            y.right.parent = x

        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x is x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y

        y.right = x
        x.parent = y

    def insert(self, key) -> None:
        node = Node(key)
        node.left = node.right = self.NIL

        # обычная вставка в дерево поиска
        parent, current = None, self.root
        while current is not self.NIL:
            parent = current
            current = current.left if key < current.key else current.right

        node.parent = parent
        if parent is None:
            self.root = node
        elif key < parent.key:
            parent.left = node
        else:
            parent.right = node

        self._fix_insert(node)

    def _fix_insert(self, node: Node) -> None:
        # чиним, пока родитель красный
        while node.parent and node.parent.color == RED:
            grand = node.parent.parent
            if node.parent is grand.left:
                uncle = grand.right
                if uncle.color == RED:                    # случай 1
                    node.parent.color = uncle.color = BLACK
                    grand.color = RED
                    node = grand
                else:                                     # случай 2
                    if node is node.parent.right:
                        node = node.parent
                        self._rotate_left(node)
                    node.parent.color = BLACK
                    grand.color = RED
                    self._rotate_right(grand)
            else:
                # зеркальный случай
                uncle = grand.left
                if uncle.color == RED:
                    node.parent.color = uncle.color = BLACK
                    grand.color = RED
                    node = grand
                else:
                    if node is node.parent.left:
                        node = node.parent
                        self._rotate_right(node)
                    node.parent.color = BLACK
                    grand.color = RED
                    self._rotate_left(grand)

        self.root.color = BLACK      # правило 2, на всякий случай


tree = RedBlackTree()
for key in [10, 5, 15, 3, 7, 12, 20]:
    tree.insert(key)

print(tree.root.key, 'чёрный' if tree.root.color == BLACK else 'красный')
# 10 чёрный

Приём с общим фиктивным NIL-узлом вместо None избавляет от бесконечных проверок на пустоту — тот же принцип, что фиктивные головы в связных списках.

Сравнение с АВЛ

Правило выбора то же, что и раньше: много чтений — АВЛ, много записей — красно-чёрное.

Где встречается на практике

• C++: std::map, std::set, std::multimap
• Java: TreeMap, TreeSet, а также HashMap — при восьми и более коллизиях в одной корзине список превращается в красно-чёрное дерево
• Linux: планировщик CFS хранит процессы в красно-чёрном дереве, менеджер виртуальной памяти — тоже
• Базы данных: индексы в некоторых движках

Причина популярности прагматична: сбалансированный компромисс между скоростью чтения и записи плюс предсказуемое число поворотов.

Частые ошибки

Вставка чёрного узла. Мгновенно ломает правило 5 — чёрная высота одного пути станет больше остальных. Новый узел всегда красный.

Отдельные NIL-объекты для каждого листа. Работать будет, но память расходуется впустую. Общий фиктивный узел решает задачу.

Забытая покраска корня в чёрный. После перекрасок корень может оказаться красным. Последняя строка _fix_insert это исправляет.

Попытка написать удаление с наскока. Там шесть случаев вместо двух и две симметричные ветки. Если нужно в проде — берите готовую библиотеку.

Что запомнить

• Баланс поддерживается цветом узлов, а не хранением высоты.
• Ключевое правило: все пути от узла до листьев содержат одинаковое число чёрных узлов.
• Высота не превышает 2·log₂(n+1) — вдвое хуже идеала, но всё ещё логарифм.
• Красный дядя лечится перекраской, чёрный — поворотом; поворотов при вставке не больше двух.
• Стоит в стандартных библиотеках C++ и Java именно из-за баланса чтения и записи.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→