JavaNotes

Красно черное дерево

3 min read

Красно-чёрное дерево

Красно-чёрное дерево — binary search tree с дополнительным цветом узла и правилами балансировки. Правила ограничивают высоту, поэтому поиск, вставка и удаление занимают O(log n) в худшем случае.

Инварианты

Удобно считать отсутствующих детей чёрными NIL-листьями:

  1. каждый реальный узел красный или чёрный;
  2. root чёрный;
  3. все NIL-листья чёрные;
  4. у красного узла оба ребёнка чёрные;
  5. от любого узла до каждого нижележащего NIL проходит одинаковое число чёрных узлов.

Число чёрных узлов на таком пути называют black height. Красные узлы не могут стоять подряд, поэтому самый длинный путь ограничен удвоенной длиной самого короткого. Отсюда высота не превосходит 2 * log2(n + 1).

          8B
        /    \
      4R      12R
     /  \     /  \
    2B  6B  10B  14B

Цвет не меняет BST-инвариант: слева остаются меньшие ключи, справа — большие. Основа дерева разобрана в Бинарное дерево.

Чем восстанавливают баланс

  • recolor меняет цвета, не затрагивая порядок ключей;
  • left rotation поднимает правого ребёнка;
  • right rotation поднимает левого ребёнка.

Поворот меняет локальную форму за O(1) и сохраняет in-order порядок.

Вставка

Новый узел обычно добавляется красным: это не меняет black height путей. Если родитель чёрный, работа закончена. При красном родителе нарушено правило «нет двух красных подряд»:

  1. красный uncle — родитель и uncle становятся чёрными, grandparent красным, проверка продолжается выше;
  2. чёрный uncle и «угол» — первый поворот превращает конфигурацию в линию;
  3. чёрный uncle и «линия» — поворот grandparent и recolor завершают локальное исправление.

В конце root окрашивается в чёрный.

Удаление

Удаление сложнее, потому что исчезновение чёрного узла меняет black height. Реализация переносит проблему «лишней черноты» вверх либо устраняет её поворотами и recolor относительно sibling и его детей. Практический код лучше брать из проверенной библиотеки: число граничных случаев велико.

Где встречается

TreeMap и TreeSet в JDK основаны на красно-чёрном дереве. Они дают сортированный порядок и O(log n) для основных операций. HashMap Java 8+ также может превращать перегруженный бакет в древовидную форму; это локальное дерево внутри hash-таблицы, а не сортировка всей map.

Сравнение

СтруктураПоиск в худшем случаеПорядок
обычный BSTO(n)сортированный обход
красно-чёрное деревоO(log n)сортированный обход
HashMapO(n), дерево бакета O(log n)не гарантирован

Красно-чёрное дерево не идеально выравнивает высоту. Более мягкий баланс уменьшает число поворотов при обновлениях по сравнению с более строгими вариантами.

Связанные темы: Big O, Comparator Java, HashMap.

Вопросы для собеседования

  1. Зачем нужен цвет? Кодирует ограничения, удерживающие высоту O(log n).
  2. Может ли красный узел иметь красного ребёнка? Нет.
  3. Что одинаково на путях к NIL? Число чёрных узлов.
  4. Почему новый узел делают красным? Чтобы сразу не увеличить black height.
  5. Что сохраняет rotation? BST-порядок ключей.
  6. Почему удаление сложнее вставки? Удаление чёрного узла нарушает black height.
  7. Где дерево используется в JDK? В TreeMap, TreeSet и древовидных бакетах HashMap.

Graph View

Backlinks