Красно-Чёрное дерево (Red-Black Tree)

Красно-чёрное дерево — это самобалансирующееся бинарное дерево поиска, где каждый узел имеет цвет (красный или чёрный), и соблюдаются правила, гарантирующие логарифмическую высоту дерева.

Правила (инварианты)

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

Структура узла

class RBNode:
    def __init__(self, key):
        self.key   = key
        self.color = "RED"      # новые узлы всегда красные
        self.left  = None       # NIL-лист
        self.right = None
        self.parent = None

Визуализация

graph TD 13B["🔲 13"]:::black 8R["🔴 8"]:::red 17B["🔲 17"]:::black 1B["🔲 1"]:::black 11B["🔲 11"]:::black 15R["🔴 15"]:::red 25R["🔴 25"]:::red 6R["🔴 6"]:::red 13B --> 8R 13B --> 17B 8R --> 1B 8R --> 11B 17B --> 15R 17B --> 25R 1B --> 6R classDef black fill:#2d2d2d,color:#fff,stroke:#000 classDef red fill:#c0392b,color:#fff,stroke:#8e1a0e

Сложность операций

Операция	Среднее	Худшее
Поиск	O(log n)	O(log n)
Вставка	O(log n)	O(log n)
Удаление	O(log n)	O(log n)
Память	O(n)	O(n)

Высота дерева ≤ 2 · log₂(n+1) — гарантированный потолок.

Вставка — алгоритм

def insert(self, key):
    # 1. Обычная вставка BST (новый узел — RED)
    node = RBNode(key)
    self._bst_insert(node)

    # 2. Восстановление инвариантов
    self._fix_insert(node)

def _fix_insert(self, z):
    while z.parent and z.parent.color == "RED":
        if z.parent == z.parent.parent.left:
            uncle = z.parent.parent.right

            if uncle and uncle.color == "RED":
                # Case 1: дядя красный → перекраска
                z.parent.color         = "BLACK"
                uncle.color            = "BLACK"
                z.parent.parent.color  = "RED"
                z = z.parent.parent
            else:
                if z == z.parent.right:
                    # Case 2: узел — правый потомок → левый поворот
                    z = z.parent
                    self._rotate_left(z)
                # Case 3: узел — левый потомок → правый поворот
                z.parent.color        = "BLACK"
                z.parent.parent.color = "RED"
                self._rotate_right(z.parent.parent)
        else:
            # Симметричные случаи (right side)
            ...

    self.root.color = "BLACK"   # правило 2

Повороты

Левый поворот (x):          Правый поворот (y):

    x                               y
   / \          →                  / \
  A   y                           x   C
     / \                         / \
    B   C                       A   B

def _rotate_left(self, x):
    y = x.right
    x.right = y.left
    if y.left:
        y.left.parent = x
    y.parent = x.parent
    if not x.parent:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

Сравнение с другими деревьями

Критерий	RB-Tree	AVL-Tree	B-Tree
Балансировка	Менее строгая	Строгая	По степени
Вставка/удаление	Быстрее	Медленнее	Быстро на диске
Поиск	Чуть медленнее	Быстрее	Медленнее в памяти
Применение	`std::map`, `TreeMap`	БД-индексы	Файловые системы

Применение в реальных системах

🔴 Linux Kernel — планировщик CFS (Completely Fair Scheduler)
🔴 Java — TreeMap, TreeSet, HashMap (при коллизиях)
🔴 C++ STL — std::map, std::set
🔴 Nginx — таймеры событий
🔴 PostgreSQL — внутренние структуры памяти

💡 Совет: Если вам нужно использовать RB-дерево в DataPlayer-запросах, такие структуры уже встроены в индексы PostgreSQL и MySQL — вам не нужно реализовывать их вручную.

Поиск по Красно-Чёрному дереву

Алгоритм поиска

Поиск в КЧ-дереве идентичен поиску в обычном BST — раскраска полностью игнорируется:

def search(node, key):
    if node is NIL or node.key == key:
        return node          # нашли или дошли до листа

    if key < node.key:
        return search(node.left, key)   # идём влево
    else:
        return search(node.right, key)  # идём вправо

flowchart TD A["Начало: корень"] --> B{"key == node.key?"} B -- "Да" --> C["✅ Найдено"] B -- "key < node.key" --> D["Идём влево"] B -- "key > node.key" --> E["Идём вправо"] D --> F{"node == NIL?"} E --> F F -- "Да" --> G["❌ Не найдено"] F -- "Нет" --> B

Главный вопрос: раскраска ускоряет поиск?

Короткий ответ: нет, напрямую — не ускоряет

Цвет узла при поиске не проверяется и не влияет на направление движения по дереву.

Тогда зачем цвета?

Раскраска — это косвенный механизм: она обеспечивает баланс дерева при вставках и удалениях, а баланс уже гарантирует быстрый поиск.

Цвета → соблюдение инвариантов
     → дерево остаётся сбалансированным
     → высота h = O(log n)
     → поиск работает за O(log n)

Как инварианты ограничивают высоту

Из правил 4 и 5 вместе следует жёсткое ограничение:

Высота КЧ-дерева не превышает 2 · log₂(n+1)

Почему именно так:

Правило 5 → все пути до NIL содержат одинаковое количество чёрных узлов (black-height = bh)
Правило 4 → между двумя чёрными узлами может быть не более одного красного
Значит, самый длинный путь (чёрный-красный-чёрный-красный-...) в 2 раза длиннее самого короткого (только чёрные)
Отсюда: h ≤ 2 · bh ≤ 2 · log₂(n+1)

{
  "title": { "text": "Максимальная высота дерева при n узлах", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["Несбалансированный BST (худший случай)", "Красно-чёрное дерево (2·log₂n)", "AVL дерево (1.44·log₂n)"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "name": "n (узлов)",
    "data": ["1", "10", "50", "100", "500", "1000", "10000", "100000"]
  },
  "yAxis": { "type": "value", "name": "Высота" },
  "series": [
    {
      "name": "Несбалансированный BST (худший случай)",
      "type": "line",
      "data": [1, 10, 50, 100, 500, 1000, 10000, 100000],
      "lineStyle": { "color": "#e74c3c" }
    },
    {
      "name": "Красно-чёрное дерево (2·log₂n)",
      "type": "line",
      "data": [0, 7, 11, 13, 18, 20, 27, 34],
      "lineStyle": { "color": "#e67e22" }
    },
    {
      "name": "AVL дерево (1.44·log₂n)",
      "type": "line",
      "data": [0, 5, 8, 10, 13, 14, 19, 24],
      "lineStyle": { "color": "#2ecc71" }
    }
  ]
}

AVL vs КЧ-дерево: поиск

	AVL	Красно-чёрное
Макс. высота	`1.44 · log₂n`	`2 · log₂n`
Поиск (теория)	Чуть быстрее	Чуть медленнее
Поиск (практика)	Сравнимо	Сравнимо
Баланс после вставки	Строгий	Мягкий
Ротаций при вставке	Больше	Меньше
Где применяется	Read-heavy	Универсально

На практике разница в скорости поиска между AVL и КЧ незначительна и часто перекрывается кэш-эффектами и реализацией. Поэтому КЧ-дерево чаще выбирают как универсальную структуру — оно быстрее при записи, не сильно проигрывая при чтении.

Итог

Поиск в КЧ-дереве — обычный BST-поиск, цвета игнорируются
Раскраска нужна не для поиска, а для поддержания баланса при изменениях
Баланс гарантирует высоту O(log n) → поиск всегда O(log n) даже в худшем случае
Это главное преимущество перед обычным BST, который деградирует до O(n) на отсортированных данных