Как выглядит красно-черное дерево

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

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

Основные свойства

Каждый узел имеет цвет — RED или BLACK, и дерево удовлетворяет пяти правилам:

1. Каждый узел окрашен в RED или BLACK
2. Корень всегда BLACK
3. Все листья (NULL nodes) BLACK
4. Если узел RED, то оба его потомка BLACK (no two red nodes in a row)
5. Все пути от узла до листьев содержат одинаковое количество BLACK узлов

Визуальное представление

Простой пример красно-чёрного дерева с числами 1, 3, 5, 7, 10, 12, 15:

           10 (BLACK)
          /          \
        5 (RED)      12 (BLACK)
       /    \         /       \
    3(B)   7(B)    11(B)    15(B)
   /  \
 1(R) NULL

Каждая строка обозначает глубину, цвет в скобках. NULL узлы (листья) считаются BLACK.

Сложная структура

Более реалистичное красно-чёрное дерево при вставке 10 элементов:

               20 (B)
              /      \
          10 (B)    30 (R)
         /    \      /    \
      5(R)  15(B)  25(B) 35(B)
     /  \
   1(B) 7(B)  

Замечание: RED узлы всегда содержат на одном уровне глубже BLACK узлы.

Почему RED и BLACK?

1. RED узлы — нарушают баланс, их нужно переиндексировать
2. BLACK узлы — поддерживают инвариант глубины
3. Правило 5 гарантирует, что дерево остаётся примерно сбалансированным (глубина всегда O(log n))

Операция вставки (insert)

Вставка элемента 4 в дерево выше:

1. Вставляем как в обычное BST
2. Новый узел окрашиваем в RED
3. Проверяем нарушения и исправляем через rotations и recoloring

После вставки 4:

               20 (B)
              /      \
          10 (B)    30 (R)
         /    \      /    \
      5(R)  15(B)  25(B) 35(B)
     /  \
   1(B) 7(B)  
       /
     4(R)  <- новый узел RED

Если родитель узла тоже RED, это нарушает правило. Выполняем:

• Rotation (поворот) — локальная перестановка узлов
• Recoloring (перекраска) — изменение цветов

Ротации (Rotations)

Left Rotation (левый поворот)

    x                 y
     \               /
      y      =>     x
     /  \          \  \
    T2  T3        T2  T3

Помогает разрешить конфликт, когда два RED узла подряд справа.

Right Rotation (правый поворот)

      y               x
     /               \ 
    x        =>       y
   / \               / \
  T1  T2           T1  T2

Пример балансирования после вставки

Вставляем 6 в дерево:

До:                       После перекраски и ротации:
       10(B)                        10(B)
      /    \                       /    \
    5(R)  15(B)       =>        5(R)  15(B)
   / \                         / \  
 1(B) 7(R)                   1(B) 7(B)
     /                           / \
   6(R)                        6(R) NULL

Удаление (delete)

Удаление сложнее, чем вставка. Требует до 3 ротаций в худшем случае. Алгоритм:

1. Удаляем как в обычном BST
2. Если удалённый узел был RED — готово
3. Если удалённый был BLACK — нужна перебалансировка (может нарушиться правило 5)

Применение в Java

// TreeMap использует красно-чёрное дерево
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "ten");
map.put(5, "five");
map.put(15, "fifteen");
// Все операции: O(log n)

// TreeSet тоже
TreeSet<Integer> set = new TreeSet<>();
set.add(10);
set.add(5);
set.add(15);

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

• Поиск (find): O(log n) — как обычное BST
• Вставка (insert): O(log n) — поиск + ротации
• Удаление (delete): O(log n) — поиск + ротации
• Обход (traverse): O(n)

Сравнение с другими структурами

Red-Black деревья предпочитают AVL, потому что требуют меньше ротаций при вставке/удалении, хотя немного менее сбалансированы.

Визуальная памятка

От худшего к лучшему случаю:

• Несбалансированное BST: глубина может быть O(n)
• AVL Tree: строго сбалансировано, глубина O(log n), но много ротаций
• Red-Black Tree: расслабленный баланс, глубина O(log n), меньше ротаций
• 2-3 Tree (B-Tree): идеальный баланс, но сложнее в реализации