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

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

Красно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — «цвет». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный». Красно-чёрное дерево обладает следующими свойствами:

1. Корень должен быть чёрным.
2. Потомки красного узла должны быть чёрными.
3. На всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково.

При этом для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных.

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

Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, контейнер map библиотеки STL, также как и многие другие реализации ассоциативного массива в различных библиотеках, основан на красно-чёрных деревьях.

Популярность красно-чёрных деревьев связана с тем, что на них достигается подходящий баланс между степенью сбалансированности и сложностью поддержки сбалансированности. В частности, при сравнении с идеально сбалансированными деревьями обнаруживается, что последние имеют слишком жесткое условие сбалансированности и при выполнении операций модификации дерева много времени тратится на поддержание необходимой сбалансированности.

Связь с B-деревьями

Красно-чёрное дерево можно рассматривать как двоичное дерево, построенное из B-дерева с максимальным количеством потомков у любой вершины = 4, по следующим правилам:

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

Таким образом получаем бинарное дерево, являющееся моделью B-дерева с максимальным количеством потомков у вершины = 4.

В исходном B-дереве (так как оно сбалансировано) все пути от корня до любого листа имеют одинаковую длину. По построению очевидно, что любой путь в RB-дереве возрастает не более чем в два раза. Таким образом, можем получить минимальный путь, равным по длине пути в исходном дереве, и максимальный, превышающий по длине путь в исходном дереве в два раза.

См. также

• Поиск в глубину
• Поиск в ширину
• Сбалансированные (самобалансирующиеся) деревья:

• АВЛ-дерево
• Идеально сбалансированное дерево
• Расширяющееся дерево

Ссылки

• Визуализатор Красно-чёрного дерева
• Томас Ниман Сортировка и поиск: Рецептурный справочник
• Эффективная реализация Красно-Чёрных Деревьев (ENG)
• Красно-чёрные деревья (теория и реализация)