14.3. Добавление вершины

Добавление вершины в красно-чёрное дерево проводится за время О (lgra). Сначала мы применяем процедуру Tree-Insert, как делалось для двоичных деревьев поиска, и красим новую вершину в красный цвет. После этого надо восстановить RB-свойства, для чего приходится перекрасить некоторые вершины и произвести вращения. При этом возможны различные ситуации, с которыми надо аккуратно разобраться.

RB-Insert(T, ж) 1 Tree-Insert (Г, ж)

2color[x] <- red

3while ж ф root[T] и со/ог[р[ж]] = red

4do if р[х] = left\p[p[x]]]

5then у <- ггд/г£[р[р[ж]]]

6if Color[y] = red

7then со/ог[р[ж]] <- black> Случай 1

8color[y] <- black> Случай 1

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

10ж <- р[р[ж]]> Случай 1

11else ]£ х = right\p[x]]

12then ж <- р[х]> Случай 2

13Left-Rotate(T, ж) > Случай 2

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

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

16Right-Rotate(T,р[р[ж]]) о Случай 3

17else (аналогичный текст с

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

18 color[root[T]] - black

На рисунке 14.4 показан пример применения процедуры RB-Insert.

Процедура RB-Insert проще, чем кажется на первый взгляд. После выполнения строк 1-2 выполняются все RB-свойства, кроме одного: красная вершина ж может иметь красного родителя, (см. рис. 14.4а). В остальном всё в порядке - другие свойства «не замечают» добавления красной вершины (отметим, что новая красная вершина имеет двух чёрных nil-детей).

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

Рис. 14.4 Работа процедуры RB-INSERT. (а) Добавлена вершина х; при этом нарушилось свойство 3: £ и его родитель красные. Вершина у (которую можно назвать «дядей» вершины х) красная, поэтому имеет место случай 1. После перекрашивания вершин получается дерево (б). Новая вершина i и её родитель красные, но дядя у чёрный. Так как х - правый ребёнок, имеет место случай 2. Производится левое вращение, которое дает дерево (в). Теперь уже х является левым ребёнком, и это - случай 3. После правого вращения получаем корректное красно-чёрное дерево (г).

Рис. 14.5 Случай 1. Нарушено свойство 3: £ и его родитель - красные. Наши действия не зависят от того, является ли х правым (а) или левым (б) сыном. Все поддеревья а, /3, у, S и е имеют чёрный корень и одинаковую чёрную высоту. Процедура меняет цвет вершины р[р[ж]] и её детей. Цикл продолжается после присваивания х <- р[р[ж]]; свойство 3 может быть нарушено только между красной вершиной р[р[ж]] и её родителем (если он тоже красный).

Внутри цикла рассматриваются шесть случаев, но три из них симметричны трём другим, различия лишь в том, является ли родитель вершины ж левым или правым ребёнком своего родителя. Эти случаи разделяются в строке 4. Мы выписали фрагмент процедуры для случая, когда р[х] - левый ребёнок своего родителя. (Симметричные случаи относятся к строке 17.)

Мы будем предполагать, что во всех рассматриваемых нами красно-чёрных деревьях корень чёрный (и поддерживать это свойство - для этого используется строка 18). Поэтому в строке 4 красная вершина р[х] не может быть корнем (р[р[ж]] существует).

Операции внутри цикла начинаются с нахождения вершины у, которая является «дядей» вершины х (имеет того же родителя, что и вершина р[ж]). Если вершина у красная, имеет место случай 1, если чёрная - то один из случаев 2 и 3. Во всех случаях вершина р[р[ж]] чёрная, так как пара ж-р[ж] была единственным нарушением RB-свойств.

Случай 1 (строки 7-10) показан на рис. 14.5. Эта часть текста исполняется, если и р[х], и у красные. При этом вершина р[р[ж]] - чёрная. Перекрасим р[х] и у в чёрный цвет, а р[р[ж]] - в красный. При этом число чёрных вершин на любом пути из корня к листьям останется прежним. Нарушение RB-свойства возможно в единственном месте нового дерева: у р[р[ж]] может быть красный родитель. Поэтому надо продолжить выполнение цикла, присвоив х значение р[р[ж]].

В случаях 2 и 3 вершина у чёрная. Эти два случая различаются тем, каким ребёнком ж приходится своему родителю - левым