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

Пример красно-чёрного дерева.

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

При этом все листья дерева являются фиктивными и не содержат данных.

Свойства

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

1. Каждый узел промаркирован красным или чёрным цветом
2. Корень и конечные узлы (листья) дерева – чёрные
3. У красного узла родительский узел – чёрный
4. Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов – black-height(x)
5. Чёрный узел может иметь чёрного родителя

Высота красно-черного дерева

Теорема:

Красно-чёрное дерево с [math]n[/math] ключами имеет высоту [math]h \geqslant \log(n + 1) = O(\log n)[/math].

Доказательство:

[math]\triangleright[/math]

1. Совмещаем все красные узлы с родительскими чёрными (они существуют по свойству 2) начиная с корня 2. В результате получим дерево, каждый узел котрого имеет 2, 3 или 4 потомка 3. В следствии свойства 4 красно-чёрного дерева, все листья 2-3-4 дерева будут иметь одинаковую глубину – black-height корня исходного дерева 4. Пусть дерево из п.2 имеет высоту [math]h'[/math]. Тогда [math]h' \geqslant h/2[/math], т.к. не более половины узлов на каждом пути – красные 5. Количество листьев не изменяется и равно [math]n + 1[/math] для обоих деревьев, т.к. в красно-чёрном дереве все внутренние узлы имеют ровно два листа 6. В 2-3-4 дереве высоты [math]h'[/math] количество листьев [math]n + 1[/math] ограничено: [math]2^{h'} \leqslant n + 1 \leqslant 4^{h'}[/math] 7. Тогда: [math]n + 1 \geqslant 2^{h'}[/math] [math]\log(n + 1) \geqslant h' \geqslant h/2[/math] [math]h \leqslant 2\log(n + 1)[/math]

[math]\triangleleft[/math]

Операции

Вставка элемента

Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын - лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то достаточно рассмотреть только два случая:

1. "Дядя" этого узла тоже красный. Тогда просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" - в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.

2. "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком.

Удаление вершины

При удалении вершины могут возникнуть три случая в зависимости от количества её детей:

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

Проверим балансировку дерева. Т.к. при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.

1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца - в красный цвет.

2. Если брат текущей вершины был чёрным, то получаем три случая:

• Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины.

• Если у брата правый ребёнок чёрный,а левый красный, то перекрашиваем брата и его левого сына и делаем вращение.

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

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

Объединение красно-чёрных деревьев

Объединение двух красно-чёрных деревьев [math]T_{1}[/math] и [math]T_{2}[/math] по элементу x выполняется, когда [math]key[T_{1}] \leqslant x[/math] и [math]x \leqslant key[T_{2}][/math]. Найдём чёрные высоты деревьев. Предположим также, что [math]hb[T_{1}] \geqslant hb[T_{2}][/math]. Тогда в дереве [math]T_{1}[/math] ищем среди чёрных вершин, имеющих чёрную высоту [math]hb[T_{2}][/math], вершину y с наибольшим ключом. Пусть [math]T_{y}[/math] — поддерево с корнем y. Объединяем это дерево с [math]T_{2}[/math] в одно с красным корнем x. Теперь родителем вершины x становится бывший отец вершины y. Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.

Т.к. общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за [math]O(\log{n})[/math].

Рассмотрим пример объединения два красно-чёрных дерева и вершины (35):

Узнаём чёрную высоту левого и правого дерева. Чёрная высота левого и правого деревьев равна 2 и 1 соответственно. Т.к. чёрная высота левого дерева больше, то ищем в левом дереве чёрную вершину, имеющую чёрную высоту правого дерева, с наибольшим ключом. Чёрная высота вершины (8) левого дерева равна высоте правого дерева и ключ является наибольшим. Поэтому вершина (8) становится левым сыном вершины (35), а правое дерево будет правым сыном. Вершина (35) станет правым сыном вершины (0):

Далее прверяем: не наришили ли мы свойства красно-чёрного дерева. Т.к. прсутствует нарушение (у красной вершины есть красный сын), то перекрасим вершины и сделаем поворот:

Преимущество красно-чёрных деревьев

Одно из основных преимуществ красно-чёрных деревьев заключается в том, что процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, т.к. алгоритм поиска не зависит от аттрибута цвета узлов. Вращение поддеревьев не может выполнятся одновременно с поиском, но при вставке выполняется не более [math]O(1)[/math] вращений.

Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL (map, set, multiset, multimap) основаны на красно-чёрных деревьях. Легко видеть, что красно-чёрные деревья изометричны 2-3-4 B-деревьям. Каждый чёрный узел можно объединить с его красными потомками. Результирующий узел будет иметь не более трех ключей и не более четырех потомков.

Ссылки

• Визуализатор
• Википедия
• algolist.manual.ru
• lectures.stargeo.ru
• nord.org.ua