RB-Delete-Fixup (Г, ж)

1while х ф root[T] и color[x] = black

2do if x = left\p[x]]

3then w <- га 1£[р[ж]]

4if color[w] = red

5then color[w] <- black> Случай 1

6со/ог[р[ж]] <- red> Случай 1

7Left-Rotate (Г, p[x])> Случай 1

8w <- пЛ[р[ж]]О Случай 1

9if color[left[w]] = black и

color[right[w]] = black

10then color[w] <- red> Случай 2

11ж <- р[ж]о Случай 2

12else if color[right[w]] = black

13then color[left[w]] <- black > Случай 3

14color[w] <- red> Случай 3

15Right-Rotate(T, w) о Случай 3

16w <- пЛ[р[ж]]> Случай 3

17color[w] <- со/ог[р[ж]]о Случай 4

18со/ог[р[ж]] <- black> Случай 4

19color[right[w]] <- blackо Случай 4

20Left-Rotate (Г, р[ж])о Случай 4

21ж <- гоо[Г]> Случай 4

22else (симметричный фрагмент с

заменой left -и- right)

23со/ог[ж] <- black

Если удалённая процедурой RB-Delete вершина у была чёрной, то любой путь, через неё проходивший, теперь содержит на одну чёрную вершину меньше. Таким образом, свойство 4 нарушилось. Мы можем компенсировать это за счёт вершины ж (занявшей место вершины у). Если ж - красная, сделаем её чёрной (заодно мы избегаем опасности получить красную вершину с красным родителем). Если ж - чёрная, объявим её «дважды чёрной» и будем считать за две при подсчёте числа чёрных вершин на пути от корня к листьям. Конечно, такой выход может быть лишь временным, поскольку определение красно-чёрных деревьев не предусматривает дважды чёрных вершин, и мы должны постепенно от такой вершины избавиться.

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

свойство остаётся верным.

Цикл завершается, если (1) ж указывает на красную вершину (тогда мы в строке 23 красим её в чёрный цвет) или если (2) х указывает на корень (тогда лишняя чернота может быть просто удалена из дерева). Может оказаться также, что (3) внутри тела цикла удаётся выполнить несколько вращений и перекрасить несколько вершин, после чего дважды чёрная вершина исчезнет. В этом случае присваивание х <- root[T] позволяет выйти из цикла.

Внутри цикла х указывает на дважды чёрную вершину, не являющуюся корнем. В строке 2 мы определяем, каким ребёнком является х - левым или правым. (Подробно выписана часть процедуры для первого случая, второй случай симметричен и скрыт в строке 22.) Переменная w (строка 3) указывает на второго ребёнка вершины р[х] («брата» вершины ж). Так как вершина ж - дважды чёрная, w не может быть равно nil[T], поскольку в этом случае вдоль одного пути от р[х] вниз (через w) было бы меньше черных вершин, чем вдоль другого (через ж).

Четыре возможных случая показаны на рис. 14.7. Прежде чем разбираться с ними детально, посмотрим, как проверить, что преобразования не нарушают свойство 4. Достаточно убедиться, что количество чёрных вершин от корня показанного поддерева до каждого из поддеревьев а,(3,...,( не изменилось. Например, на рис. 14.7а, иллюстрирующем случай 1, количество чёрных вершин от корня до каждого из поддеревьев а и /3 равно 3 как до, так и после преобразования. (Напомним, что вершина ж считается за две.) Аналогично, количество чёрных вершин от корня до у, S, е и (, равно 2 до и после преобразования. На рис. 14.76 вершина В может быть и чёрной, и красной. Если она красная, то число чёрных вершин от корня до а (до и после преобразования) равно 2, если чёрная

-то 3. Остальные случаи проверяются аналогично (упр. 14.4-5). Итак, рассмотрим все случаи по порядку. Случай 1 (строки 5-8

процедуры RB-Delete-Fixup, рис. 14.7а) имеет место, когда вершина w, брат ж, красная (в этом случае их родитель, р[х], чёрный). Так как оба ребёнка вершины w чёрные, мы можем поменять цвета w и р[х] и произвести левое вращение вокруг р[х], не нарушая RB-свойств. Вершина ж остаётся дважды чёрной, а её новый брат

-чёрный, так что мы свели дело к одному из случаев 2, 3 или 4. Если вершина w чёрная, имеет место один из случаев 2-4. Они

различаются между собой цветом детей вершины w. В случае 2 (строки 10-11, рис. 14.76) оба ребёнка вершины w чёрные. Так как вершина w тоже чёрная, мы можем снять чёрную окраску с ж (лишнюю) new (сделав её красной), и добавить черноту родителю, р[х]. После этого продолжим выполнение цикла. Заметим, что если мы попали в случай 2 из случая 1, то вершина р[х] - красная, поэтому цикл сразу же завершится (добавив чёрного к красной вершине, мы красим её в обычный чёрный цвет).

В случае 3 (строки 13-16, рис. 14.7в) вершина w чёрная, её левый ребёнок - красный, а правый - чёрный. Мы можем поменять цвета w и её левого ребёнка и потом применить правое вращение так, что RB-свойства будут сохранены. Новым братом вершины ж теперь будет чёрная вершина с красным правым ребёнком, и мы свели случай 3 к случаю 4.

Наконец, в случае 4 (строки 17-21, рис. 17.4г) вершина w (брат вершины ж) является чёрной, а её правый ребёнок - красный. Меняя некоторые цвета и производя левое вращение вокруг р[х], мы можем удалить излишнюю черноту у ж, не нарушая RB-свойств. Присваивание ж <- root[T] выводит нас из цикла.

Каково время выполнения процедуры RB-Delete? Высота красно-чёрного дерева с га вершинами есть О (lgra), поэтому время исполнения RB-Delete без учёта RB-Delete-Fixup есть O(lgra). Сколько времени требует цикл в процедуре RB-Delete-Fixup? Как только обнаруживается случай 1, 3 или 4, мы выходим из цикла (при этом выполняется 0(1) операций и самое большее три вращения). До этого возможно несколько повторений случая 2, но при каждом повторении указатель ж перемещается вверх по дереву и никакие вращения не производятся, так что число таких шагов есть О (lgra). Таким образом, процедура RB-Delete-Fixup требует времени О (lgra), и общее время работы процедуры RB-Delete также есть О (lgra) (отметим ещё раз, что при этом производится не более трёх вращений).

Упражнения

14.4-1 Убедитесь, что после выполнения процедуры RB-Delete корень дерева остаётся чёрным, если он таковым был.

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

14.4-3 В каких строках процедуры RB-Delete-Fixup мы можем читать или изменять фиктивный элемент nil[T]?

14.4-4 Упростите процедуру Left-Rotate, используя фиктивный элемент для представления nil и ещё один фиктивный элемент, содержащий указатель на корень дерева.

14.4-5 Для каждого из случаев на рисунке 14.7 подсчитайте количество чёрных вершин от корня поддерева на рисунке до каждого из поддеревьев а, (3,..., ( и убедитесь, что оно не меняется при преобразованиях. Используйте обозначение count(c) для «степени