Красно-черные деревья
Исторически AVL-деревья, изобретенные в 1962 г., были одной из первых схем реализации почти сбалансированных деревьев. В настоящее время, однако, более популярна другая схема: красно-черные деревья, или RB-деревья, от англ. Red-Black Trees. Красно-черные деревья были введены Р. Байером в 1972 г. В стандартной библиотеке классов языка C++ исполнители множество и нагруженное множество — классы set и map — реализованы именно как красно-черные деревья.
Вместо баланс-фактора, применяемого в AVL-деревьях, RB-деревья используют цвета вершин. Каждая вершина окрашена либо в красный, либо в черный цвет. (В реализации за цвет отвечает логическая переменная.) При этом выполняется несколько дополнительных условий:
- каждая внешняя (или нулевая) вершина считается черной;
- корневая вершина дерева черная;
- у красной вершины дети черные;
- всякий путь от корня дерева к произвольной внешней вершине имеет одно и то же количество черных вершин.
Последний пункт определения означает сбалансированность дерева по черным вершинам.
Ниже приведен пример красно-черного дерева. Черные вершины изображены темно-серым цветом, красные — белым.
Из пункта 3) определения следует, что в произвольном пути от корня к терминальной вершине не может быть двух красных вершин подряд. Это означает, что, поскольку число черных вершин в любом пути одинаково, длины разных путей к терминальным вершинам отличаются не более чем вдвое. Это свойство близко по своей сути к сбалансированности. Несложно показать, что для красно-черного дерева справедлива следующая оценка сверху на высоту дерева в зависимости от числа вершин:
h <= 2 log2 (n+1)
Из этого следует, что поиск в красно-черном дереве также выполняется за логарифмическое время.
Новая вершина добавляется в красно-черное дерево как терминальная после процедуры поиска (этим RB-дерево ничем не отличается от других упорядоченных деревьев). Новая вершина окрашивается в красный цвет. При этом пункт 3) в определении красно-черного дерева может нарушиться. Поэтому после добавления, а также удаления вершины выполняется процедура восстановления структуры красно-черного дерева, играющая ту же роль, что и восстановление балансировки AVL-дерева. Преимущество красно-черных деревьев состоит в том, что процедура восстановления более простая. Во многих случаях она ограничивается перекрашиванием вершин. В ней также могут выполняться операции вращения вершины влево и вправо, но число вращений может быть не больше двух при добавлении элемента и не больше четырех при удалении. Всего число операций при восстановлении структуры RB-дерева оценивается сверху через высоту дерева:
число операций <= K · h
где h — высота дерева, K — константа. Поскольку для высоты RB-дерева справедлива приведенная выше логарифмическая оценка от числа вершин n, получаем оценку
число операций <= C log2 n
где C - константа. Таким образом, добавление и удаление элементов выполняется в случае красно-черных деревьев за логарифмическое время в зависимости от числа вершин дерева.
