Левостороннее красно-чёрное дерево¶

Левостороннее красно-чёрное дерево (англ. Left-leaning red–black tree, LLRB) — это самобалансирующееся бинарное дерево поиска, вариант красно-чёрного дерева, в котором все красные рёбра (связи между узлами) наклонены влево. Оно было предложено Робертом Седжвиком в 2008 году как упрощение реализации красно-чёрных деревьев, сохраняющее их логарифмическую сложность операций поиска, вставки и удаления. Основное отличие от классического красно-чёрного дерева — введение дополнительного ограничения, что красный узел всегда является левым потомком чёрного родителя, что позволяет записать алгоритмы балансировки в более компактной форме.

¶История

Красно-чёрные деревья были впервые описаны Рудольфом Байером в 1972 году (под названием «симметричные бинарные B-деревья») и получили широкую известность после работы Леонидаса Гибаса и Роберта Седжвика (1978). Однако их реализация считалась сложной для программирования, особенно операций удаления. В 2008 году Роберт Седжвик в статье «Left-leaning Red-Black Trees» (опубликована в журнале Dr. Dobb’s) предложил модификацию, в которой все красные рёбра направлены строго влево. Это позволило сократить количество случаев, которые необходимо обрабатывать при балансировке, и сделать код более лаконичным, особенно для рекурсивных реализаций.

¶Свойства

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

Цвет узлов: каждый узел окрашен в красный или чёрный цвет. Красный цвет интерпретируется как часть связи с родителем: красный узел означает, что ребро от родителя к нему является красным.
Корень: корень дерева всегда чёрный.
Красные рёбра только слева: если узел красный, то он обязательно является левым потомком своего чёрного родителя. Это означает, что в дереве нет красных правых потомков и не может быть двух последовательных красных узлов на левой стороне (красный узел не может иметь красного левого потомка).
Чёрная высота: для любого узла все пути от него до листьев (NULL-узлов) содержат одинаковое количество чёрных узлов (чёрная высота).
Листья: листьями считаются NULL-узлы, которые всегда чёрные (по определению).

Эти свойства гарантируют, что высота дерева не превышает \(2 \log_2 (n+1)\), где \(n\) — количество узлов, что обеспечивает время выполнения операций \(O(\log n)\).

¶Устройство и представление

Каждый узел дерева содержит:

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

В реализации часто используется отдельный тип для цвета (например, RED и BLACK). NULL-узлы считаются чёрными. Для удобства в коде обычно вводятся вспомогательные функции: isRed(node), flipColors(node), rotateLeft(node), rotateRight(node).

¶Основные операции

¶Поиск

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

¶Вставка

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

Поворот влево (rotateLeft): если правый потомок красный, а левый — чёрный (или NULL), выполняется левый поворот, чтобы перенести красное ребро на левую сторону.
Поворот вправо (rotateRight): если левый потомок красный и его левый потомок тоже красный (два последовательных красных слева), выполняется правый поворот.
Смена цветов (flipColors): если оба потомка красные, цвет текущего узла меняется на красный, а потомков — на чёрный.

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

¶Удаление

Удаление узла в LLRB сложнее вставки, но также может быть реализовано рекурсивно. Основная идея — поддерживать инвариант, что текущий узел (кроме корня) всегда красный или имеет красного левого потомка, чтобы можно было безопасно удалять узел из листа или из узла с одним потомком. Для этого используются операции:

moveRedLeft: если левый потомок и его левый потомок чёрные, выполняется смена цветов и, возможно, правый поворот, чтобы сделать левое поддерево «красным».
moveRedRight: аналогично для правого поддерева.
deleteMin и deleteMax: удаление минимального или максимального узла.
delete(key): рекурсивный поиск узла с заданным ключом, его удаление и последующая балансировка.

После удаления корень также делается чёрным.

¶Преимущества и недостатки

¶Преимущества

Простота реализации: по сравнению с классическим красно-чёрным деревом, код для LLRB короче и легче для понимания. Особенно это заметно при написании рекурсивных алгоритмов на языках типа Java, C++ или Python.
Меньше случаев для обработки: в классическом красно-чёрном дереве при вставке и удалении рассматривается до 6 различных конфигураций, в LLRB — всего 3 основных (левый поворот, правый поворот, смена цветов).
Наглядность: структура LLRB легче визуализируется, так как красные рёбра всегда направлены влево.

¶Недостатки

Скорость: из-за дополнительных проверок и поворотов LLRB может быть немного медленнее классического красно-чёрного дерева в некоторых реализациях (особенно при вставке и удалении). Однако разница обычно невелика и составляет константный множитель.
Ограниченная применимость: LLRB не является стандартным вариантом для библиотек, так как классические красно-чёрные деревья (например, в std::map в C++ или TreeMap в Java) более распространены и лучше протестированы.
Сложность удаления: хотя код удаления в LLRB компактнее, чем в классическом варианте, он всё равно остаётся нетривиальным и требует аккуратной реализации.

¶Применение

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

¶Сравнение с другими сбалансированными деревьями

Характеристика	LLRB	Классическое красно-чёрное дерево	AVL-дерево
Балансировка	Цветовая с дополнительным ограничением	Цветовая	По высоте
Высота	≤ 2 log₂(n+1)	≤ 2 log₂(n+1)	≤ 1.44 log₂(n+1)
Сложность вставки	O(log n)	O(log n)	O(log n)
Сложность удаления	O(log n)	O(log n)	O(log n)
Количество поворотов при вставке	≤ 2	≤ 2	≤ 2
Простота реализации	Высокая	Средняя	Средняя
Распространённость	Низкая	Очень высокая	Высокая

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

Роберт Седжвик, автор LLRB, также является соавтором классической работы по красно-чёрным деревьям (1978) и автором популярного учебника «Алгоритмы на Java» / «Алгоритмы на C++».
Термин «левостороннее» означает, что красные рёбра могут быть только левыми. Существует также симметричный вариант — правостороннее красно-чёрное дерево, но он менее распространён.
LLRB можно рассматривать как представление 2-3-4 дерева (B-дерева порядка 4) с помощью бинарного дерева, где красные узлы кодируют слияние ключей в одном узле 2-3-4 дерева.

¶Источники

Sedgewick, R. (2008). "Left-leaning Red-Black Trees". Dr. Dobb's Journal.
Sedgewick, R., Wayne, K. (2011). "Algorithms, 4th Edition". Addison-Wesley.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). "Introduction to Algorithms, 3rd Edition". MIT Press.
Okasaki, C. (1999). "Red-Black Trees in a Functional Setting". Journal of Functional Programming.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →