← назад к разделу

Обычное дерево поиска хорошо, пока сбалансировано, но вырождается в список, если данные вставлять по порядку, — и поиск падает с O(log N) до O(N). Красно-чёрное дерево решает эту проблему: оно само себя балансирует при каждой вставке и удалении, гарантируя O(log N) при любом порядке данных. Плата — усложнение алгоритма.

Идея: не дать дереву перекоситься

Балансировка означает, что дерево не должно становиться слишком «однобоким» — глубина ветвей должна оставаться примерно одинаковой. Полностью выравнивать дерево при каждой вставке дорого. Красно-чёрное дерево идёт на компромисс: оно не идеально сбалансировано, но гарантирует, что самая длинная ветвь не более чем вдвое длиннее самой короткой. Этого достаточно, чтобы удержать O(log N).

Чтобы отслеживать баланс, каждому узлу приписывают цвет — красный или чёрный. Цвет — это не данные, а служебная пометка, по которой дерево понимает, когда пора перестраиваться.

Красно-чёрные правила

Дерево считается сбалансированным, пока соблюдаются пять правил:

  1. каждый узел либо красный, либо чёрный;
  2. корень всегда чёрный;
  3. концы веток — пустые «заглушки» вместо отсутствующих потомков — считаются чёрными;
  4. у красного узла оба потомка чёрные (красные узлы не идут подряд);
  5. на любом пути от узла вниз до края число чёрных узлов одинаково.

Третье правило выглядит формальностью, но без него не работает пятое: если бы концы веток не считались узлами, было бы непонятно, до чего именно мы считаем чёрные узлы на пути. В реализациях эти заглушки обычно не хранят как отдельные объекты — просто договариваются, что null чёрный.

Смысл в последнем правиле: оно не даёт одной ветви стать намного длиннее другой. Как только вставка нарушает правила, дерево восстанавливает их — и заодно баланс.

Два инструмента восстановления

Перекраска (color flip) — просто смена цветов узлов. Дешёвая операция: иногда достаточно перекрасить родителя и «дядю» узла, чтобы устранить два красных подряд.

Поворот (rotation) — перестройка формы дерева. При повороте узел «опускается», а его потомок «поднимается» на его место, при этом правило «левый меньше, правый больше» сохраняется. Повороты бывают левые и правые; они физически выравнивают перекошенную ветвь, делая дерево ниже и ровнее.

левый поворот вокруг 10 корень 20 — чёрный 10 30 20

Поворот выравнивает высоту (3 → 2), перекраска возвращает пять красно-чёрных правил, поиск остаётся O(log N).

Как это работает при вставке

Новый узел всегда вставляют красным (чтобы не нарушить правило о числе чёрных узлов) на обычное место дерева поиска. Если его родитель чёрный — всё в порядке, готово. Если красный — возникают два красных подряд (нарушение правила 4), и дерево чинит это перекрасками и поворотами, поднимаясь от места вставки к корню. В конце корень при необходимости красят в чёрный. Число таких исправлений невелико — пропорционально высоте дерева, то есть O(log N).

Это легко посчитать: дадим дереву компаратор со счётчиком сравнений, зальём тысячу ключей по возрастанию — худший вход для дерева поиска — и поищем последний из них.

живой пример

import java.util.Comparator;
import java.util.TreeMap;

public class SortedInsert {
    static int compares = 0;

    public static void main(String[] args) {
        Comparator<Integer> counting = (a, b) -> { compares++; return Integer.compare(a, b); };
        TreeMap<Integer, String> tree = new TreeMap<>(counting);
        for (int key = 1; key <= 1000; key++) tree.put(key, "заказ " + key);
        compares = 0;
        tree.get(1000);
        System.out.println("сравнений при поиске последнего из " + tree.size() + " ключей: " + compares);
    }
}
Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Неделя бесплатно →

Семнадцать сравнений вместо тысячи: путь до самого дальнего ключа уложился примерно в два логарифма. Обычное дерево поиска на таком входе выродилось бы в список и прошло бы все 1000 узлов.

Как это сделано в Java

Красно-чёрное дерево — не учебная экзотика: на нём построены упорядоченные словари и множества стандартных библиотек. И при этом — тот редкий случай, когда «напишите сами» плохой совет даже для тренировки: в поворотах и перекрасках десяток симметричных случаев, ошибиться легко, а заметить ошибку трудно — дерево продолжит отвечать правильно, просто потихоньку перестанет быть сбалансированным. Разбираться в устройстве всё равно нужно: иначе непонятно, за что вы доплачиваете, когда берёте упорядоченную коллекцию вместо хеш-таблицы.

Эталонная реализация — TreeMap (и TreeSet, который внутри просто TreeMap без значений). Это буквально то дерево, что разобрано выше: у каждого узла, кроме ключа, значения и трёх ссылок (левый, правый, родитель), есть поле цвета — один булев флаг. Вставка идёт как в обычном дереве поиска, а потом поднимается к корню, починяя нарушения теми же перекрасками и левыми-правыми поворотами. Наружу цвет не виден: ни настроек, ни методов у балансировки нет — она просто есть.

Сложность отсюда честная, без оговорки «в среднем»: get, put, remove — гарантированные O(log n) при любом порядке вставки. Интереснее цена самой балансировки. Перекрасок при вставке может быть до O(log n) — они поднимаются к корню, — а вот поворотов не больше двух, при удалении — не больше трёх. Поворот дороже перекраски: он переставляет ссылки и трогает сразу несколько узлов. То, что поворотов всегда единицы, и есть причина, по которой в библиотеках прижилось именно красно-чёрное дерево, а не более строго сбалансированное (например, AVL): то было бы чуть ниже и чуть быстрее на поиске, но платило бы поворотами на каждой записи.

За упорядоченность вы платите памятью и константой. Каждая запись TreeMap — отдельный объект с шестью полями, разбросанный по куче, и путь к нему — это несколько прыжков по ссылкам. На точечном доступе по ключу хеш-таблица заметно быстрее. Поэтому TreeMap берут не «на всякий случай», а когда порядок или диапазонные запросы действительно нужны.

Грабля. Загружать в дерево уже отсортированные данные поштучно — самый дорогой способ его построить: каждая вставка сначала ищет место, потом запускает балансировку. Если источник уже упорядочен, дерево можно собрать сразу готовым:

SortedMap<Long, Order> source = ...;
Map<Long, Order> copy = new TreeMap<>(source);

Конструктор от SortedMap (и putAll в пустую TreeMap) обходит источник по порядку и раскладывает узлы сразу правильно, не сравнивая ключи вообще: линейный проход вместо n вставок с перестройками. Поштучно те же 1000 ключей обходятся примерно в 14 500 сравнений, копия целиком — в ноль. На сотне записей разница незаметна, на миллионе — вполне.

Коротко

  • Обычное дерево поиска вырождается на отсортированных данных; красно-чёрное дерево балансируется само и держит O(log N) при любом порядке вставки.
  • Баланс отслеживают через цвет узлов (красный/чёрный) и пять правил; ключевое — одинаковое число чёрных узлов на всех путях вниз.
  • Нарушенные вставкой правила чинят перекраской и поворотами, поднимаясь к корню; это стоит O(log N).
  • Дают быстрые поиск/вставку/удаление с сохранением порядка; сложны в реализации — обычно берут готовые из библиотек.

Что почитать дальше