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

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

История

Красно-чёрное дерево было предложено Рудольфом Байером в 1972 году в его работе «Symmetric binary B-trees: data structure and maintenance algorithms». Изначально структура называлась «симметричные бинарные B-деревья». Позднее, в 1978 году, Леонид Ландерс и Гвидо ван Россум (в рамках разработки языка программирования Python) независимо описали аналогичную структуру, которая получила широкое распространение. В 1993 году Роберт Седжвик опубликовал работу, в которой предложил упрощённую версию красно-чёрных деревьев, известную как «левосторонние красно-чёрные деревья».

Свойства

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

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

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

Устройство и операции

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

Каждый узел красно-чёрного дерева содержит:

• Ключ (данные) — значение, по которому осуществляется поиск.
• Цвет — красный или чёрный.
• Ссылки на левого и правого потомка.
• Ссылку на родительский узел (необязательно, но часто используется для упрощения алгоритмов).

Вставка

Вставка нового элемента в красно-чёрное дерево происходит в два этапа:

1. Стандартная вставка — элемент добавляется как в обычное двоичное дерево поиска, при этом новый узел окрашивается в красный цвет.
2. Балансировка — если после вставки нарушаются свойства красно-чёрного дерева (например, два красных узла подряд), выполняется серия перекрашиваний и поворотов (левых и правых) для восстановления баланса.

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

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

Удаление

Удаление элемента сложнее вставки, так как может потребовать более сложной балансировки. Алгоритм включает:

1. Поиск удаляемого узла.
2. Если у узла два потомка, замена его на минимальный элемент из правого поддерева (или максимальный из левого).
3. Удаление узла и последующая балансировка, которая может включать до нескольких поворотов и перекрашиваний.

Поиск

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

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

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

Красно-чёрные деревья чаще используются в библиотеках общего назначения (например, в реализации std::map в C++ STL или TreeMap в Java), где важна скорость вставки и удаления. AVL-деревья предпочтительны для задач с частым поиском, а B-деревья — для работы с большими объёмами данных на диске.

Применение

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

• Стандартные библиотеки языков программирования: в C++ (контейнер std::map), в Java (класс TreeMap), в Python (модуль bisect не использует красно-чёрные деревья, но в некоторых реализациях словарей используется).
• Операционные системы: планировщики задач (например, в ядре Linux для управления очередями процессов).
• Базы данных: в некоторых системах управления базами данных (СУБД) для индексации данных.
• Компиляторы и интерпретаторы: для хранения таблиц символов и оптимизации кода.

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

• В реализации красно-чёрных деревьев в стандартной библиотеке C++ (GCC) используется упрощённая версия, где NIL-узлы не хранятся явно, а заменяются специальным значением.
• Название «красно-чёрное» было предложено Робертом Седжвиком в 1978 году, который также ввёл термин «левостороннее красно-чёрное дерево».
• Существует вариант красно-чёрного дерева, называемый «AA-дерево» (по имени Арне Андерссона), который использует только один цвет и упрощает алгоритмы балансировки.

Источники

1. Bayer, R. (1972). Symmetric binary B-trees: data structure and maintenance algorithms. Acta Informatica, 1(4), 290-306.
2. Sedgewick, R. (1993). Left-leaning red-black trees. Princeton University.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
4. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
5. Документация к стандартной библиотеке C++ (ISO/IEC 14882:2014).