Рис. 14.6 Случаи 2 и 3 в процедуре RB-INSERT. Как и для случая 1, нарушено свойство 3 красно-чёрных деревьев, так как вершина i и её родитель р[х] - красные. Корни деревьев а, /3, у и S - чёрные; эти деревья имеют одинаковую чёрную высоту. Оба вращения, показанные на рисунке, не меняют число чёрных вершин на пути от корня к листьям. После этого мы выходим из цикла: RB-свойства выполнены всюду.

или правым. Если правым, исполняются строки 12-13 (случай 2). В этом случае выполняется левое вращение, которое сводит случай 2 к случаю 3. когда ж является левым ребёнком (рис. 14.6), Так как и ж, и р[х] красные, после вращения количества чёрных вершин на путях остаются прежними.

Итак, осталось рассмотреть случай 3: красная вершина ж является левым ребёнком красной вершины р[х], которая является левым ребёнком чёрной вершины р[р[ж]], правым ребёнком которой является чёрная вершина у. В этом случае достаточно произвести правое вращение и перекрасить две вершины, чтобы устранить нарушение й В-свойств. Цикл больше не выполняется, так как вершина р[х] теперь чёрная.

Каково время выполнения процедуры RB-Insert? Высота красно-чёрного дерева есть О (lgra), если в дереве га вершин, поэтому вызов Tree-Insert требует времени 0(lgга). Цикл повторяется, только если мы встречаем случай 1, и при этом ж сдвигается вверх по дереву. Таким образом, цикл повторяется O(lgra) раз, и общее время работы есть О (lgra). Интересно, что при этом выполняется не более двух вращений (после которых мы выходим из цикла).

Упражнения

14.3-1 В строке 2 процедуры RB-Insert мы красим новую вершину ж в красный цвет. Если бы мы покрасили её в черный цвет, свойство 3 не было бы нарушено. Почему же мы этого не сделали?

14.3-2 В строке 18 мы красим корень дерева в чёрный цвет. Зачем это делается?

14.3-3 Нарисуйте красно-чёрные деревья, которое получаются при последовательном добавлении к пустому дереву ключей 41,38,31,12,19,8.

14.3-4 Пусть чёрная высота каждого из поддеревьев а, fi, у, S, е на рисунках 14.5 и 14.6 равна к. Найдите чёрные высоты всех вершин на этих рисунках и проверьте, что свойство 4 действительно не нарушается.

14.3-5 Рассмотрим красно-чёрное дерево, полученное добавлением га вершин к пустому дереву. Убедитесь, что при га > 1 в дереве есть хотя бы одна красная вершина.

14.3-6 Как эффективно реализовать процедуру RB-Insert, если в вершинах не хранятся указатели на родителей?

14.4. Удаление

Как и другие операции, удаление вершины из красно-чёрного дерева требует времени О (lgra). Удаление вершины несколько сложнее вставки.

Чтобы упростить обработку граничных условий, мы используем фиктивный элемент (по-английски называемый sentinel) вместо nil (см. с. ??). Для красно-чёрного дерева Г фиктивный элемент nil[T] имеет те же поля, что и обычная вершина дерева. Его цвет чёрный, а остальным полям (р, left, right и key) могут быть присвоены любые значения. Мы считаем, что в красно-чёрном дереве все указатели nil заменены указателями на nil[T].

Благодаря фиктивным элементам мы можем считать nil-лист, являющийся ребёнком вершины х, обычной вершиной, родитель которой есть х. В принципе можно было бы завести по одной фиктивной вершине для каждого листа, но это было бы напрасной потерей памяти. Чтобы избежать этого, мы используем один элемент nil[T], представляющий все листы. Однако, когда мы хотим работать с листом - ребёнком вершины х, надо не забыть выполнить присваивание р[га/[Т]] <- х.

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

RB-Delete(T, z)

1if left[z] = nil[T] или right[z] = nil[T]

2then у <- z

3else у <- Tree-Successor(2:)

4if left[y] ф nil[T]

5then ж <- left[y]

6else x <- right[y]

7р[ж] f-

8if p[y] = nil[T]

9then root[T] <- ж

10else if у = left[p[y]]

11then /е [р[у]] <- ж

12else right[p[y]] <- ж

13if у ф z

14then key[z] <- fcejy[y]

15о Копируем дополнительные данные из вершины у.

16if color[y] = black

17then RB-Delete-Fixup(T, ж)

18return у

Есть три различия между процедурами RB-Delete и Tree-Delete. Во-первых, вместо nil всюду стоит указатель на фиктивный элемент nil[T]. Во-вторых, проверка ж ф nil в строке 7 процедуры Tree-Delete удалена, и присваивание р[х] <- р[у] выполняется в любом случае. Если ж есть фиктивный элемент nil[T], то его указатель на родителя становится равным родителю удаляемого элемента у. В-третьих, в строках 16-17 вызывается процедура RB-Delete-Fixup, если удаляемая вершина у - чёрная. При удалении красной вершины RB-свойства не нарушаются (чёрные высоты не меняются, и красные вершины не могут стать соседними). Передаваемая процедуре RB-Delete-Fixup вершина ж являлась единственным ребёнком вершины у, если у у был ребёнок (не являющийся листом), или фиктивным элементом nil[T], если вершина у не имела детей. В последнем случае присваивание в строке 7 гарантирует, что р[х] указывает на бывшего родителя у - вне зависимости от того, является ли ж настоящей вершиной или фиктивным элементом.

Посмотрим, как процедура RB-Delete-Fixup восстанавливает RB-свойства дерева.