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

Красно-чёрное дерево — это самобалансирующееся двоичное дерево поиска, один из типов деревьев в информатике, используемый для хранения упорядоченных данных. Оно гарантирует, что основные операции — вставка, удаление и поиск — выполняются за логарифмическое время O(log n), где n — количество узлов. Балансировка достигается за счёт дополнительного атрибута каждого узла — цвета (красный или чёрный), а также набора правил, которые поддерживают приблизительную сбалансированность дерева. Красно-чёрные деревья были предложены в 1972 году Рудольфом Байером и получили широкое распространение в компьютерных науках, в частности, в реализации ассоциативных массивов и множеств во многих языках программирования.

История

Концепция красно-чёрных деревьев была впервые описана немецким учёным Рудольфом Байером в 1972 году в его работе «Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms». Байер ввёл понятие «сбалансированных деревьев», которые позже стали известны как красно-чёрные. В 1978 году Леонид Либерман и Роберт Седжвик опубликовали модифицированную версию, в которой использовали цветовую схему (красный и чёрный) для упрощения понимания алгоритмов. С тех пор красно-чёрные деревья стали стандартной структурой данных во многих библиотеках, включая стандартную библиотеку шаблонов (STL) языка C++ (контейнеры std::map и std::set) и реализацию TreeMap в Java.

Свойства и правила

Красно-чёрное дерево удовлетворяет следующим пяти свойствам, которые гарантируют его сбалансированность:

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

Эти правила гарантируют, что самый длинный путь от корня до листа не более чем вдвое длиннее самого короткого, что обеспечивает логарифмическую сложность операций. Если бы не было балансировки, дерево могло бы выродиться в линейный список (например, при вставке отсортированных данных).

Операции

Основные операции с красно-чёрным деревом включают вставку, удаление и поиск. Все они начинаются с обычного алгоритма для двоичного дерева поиска, но после изменения структуры (вставки или удаления) могут потребоваться дополнительные корректировки для восстановления свойств красно-чёрного дерева.

Поиск

Поиск элемента в красно-чёрном дереве выполняется так же, как и в обычном двоичном дереве поиска: начиная с корня, алгоритм сравнивает искомое значение с ключом текущего узла и переходит в левое или правое поддерево. Цвет узлов при поиске не учитывается. Сложность поиска — O(log n).

Вставка

Вставка нового узла начинается с его добавления как красного узла (чтобы не нарушать свойство 5). Затем, если нарушаются свойства, выполняются операции перекрашивания и поворотов. Возможны три случая нарушения:

1. Дядя (брат родителя) красный: перекрашиваются родитель, дядя и дедушка. Проверка продолжается от дедушки.
2. Дядя чёрный и узел — внутренний потомок (например, левый потомок правого родителя): выполняется поворот, чтобы преобразовать ситуацию в случай 3.
3. Дядя чёрный и узел — внешний потомок (например, левый потомок левого родителя): выполняется поворот и перекрашивание.

После всех корректировок корень дерева окрашивается в чёрный цвет.

Удаление

Удаление узла сложнее вставки. Если удаляемый узел красный, то свойства не нарушаются. Если чёрный, то возникает «двойная чернота» (узел, который нужно удалить, оставляет после себя чёрный след, нарушающий свойство 5). Для исправления используются повороты и перекрашивания, включая несколько случаев в зависимости от цвета брата удаляемого узла и его потомков. Алгоритм удаления требует тщательной реализации, но в итоге также выполняется за O(log n).

Повороты

Повороты — это локальные операции, изменяющие структуру дерева без нарушения порядка ключей. Существуют два типа поворотов:

• Левый поворот: узел становится правым потомком своего левого потомка.
• Правый поворот: узел становится левым потомком своего правого потомка.

Повороты используются для перераспределения узлов и восстановления баланса после вставки или удаления. Они выполняются за константное время O(1).

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

Красно-чёрные деревья часто сравнивают с другими самобалансирующимися деревьями, такими как AVL-деревья и B-деревья.

• AVL-деревья обеспечивают более строгий баланс (разница высот поддеревьев не более 1), что даёт более быстрый поиск, но требует больше поворотов при вставке и удалении. Красно-чёрные деревья, в свою очередь, быстрее при операциях вставки и удаления, так как допускают большую несбалансированность.
• B-деревья (в частности, B+-деревья) оптимизированы для работы с дисковыми накопителями и базами данных, так как хранят множество ключей в одном узле, уменьшая количество обращений к памяти. Красно-чёрные деревья, напротив, ориентированы на оперативную память и обеспечивают более простую реализацию.

Применение

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

• Ассоциативные массивы и множества: в стандартной библиотеке C++ (std::map, std::set), в Java (TreeMap, TreeSet), в .NET (SortedDictionary, SortedSet).
• Планировщики задач: в операционных системах (например, в Linux для управления процессами).
• Компиляторы: для хранения таблиц символов.
• Графические движки: для быстрого поиска объектов по пространственным координатам.
• Базы данных: в некоторых реализациях индексов (хотя чаще используются B-деревья).

Интересные факты

• В языке C++ красно-чёрные деревья используются в контейнерах std::map и std::set с версии C++98.
• Алгоритм вставки в красно-чёрное дерево можно реализовать итеративно, что позволяет избежать рекурсии и снизить накладные расходы.
• Существует вариант красно-чёрных деревьев, называемый «левосторонними красно-чёрными деревьями», предложенный Робертом Седжвиком, который упрощает реализацию за счёт использования только левых поворотов.
• В некоторых реализациях (например, в Java) для экономии памяти цвет узла может храниться как один бит (0 или 1), а не как отдельный объект.

Критика

Несмотря на популярность, красно-чёрные деревья не лишены недостатков. Основная критика связана со сложностью реализации, особенно операции удаления, которая требует обработки множества случаев. Альтернативные структуры, такие как AVL-деревья или B-деревья, могут быть предпочтительнее в зависимости от конкретных требований к производительности. Кроме того, красно-чёрные деревья не гарантируют идеального баланса, что может привести к незначительному снижению скорости поиска по сравнению с AVL-деревьями.

Источники

• Байер Р. «Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms» (1972).
• Седжвик Р. «Algorithms in C++» (1998).
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (2005).
• Стандартная библиотека шаблонов C++ (STL), документация.
• Java Platform, Standard Edition, документация классов TreeMap и TreeSet.