Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 75
Текст из файла (страница 75)
Наконец, если узел у был черным, в свойства красно-черного дерева может быть внесено одно или несколько нарушений, так что для восстановления свойств красно-черного дерева в строке 22 выполняется вызов КВ-РкькткГ1ХВГ. Если узел у был красным, при переименовании или удалении узла Р красно-черные свойства сохраняются по следующим причинам. 1. Ни одна черная высота в дереве не меняется. 2. Никакие красные узлы не делаются смежными.
Поскольку у занимает в дереве место г вместе с цветом узла г, мы не можем получить два смежных красных узла в новой позиции узла у в дереве. Кроме того, если у не бьш правым дочерним узлом г, исходный правый дочерний узел х узла у заменяет последний в дереве. Если у красный, то к должен быть черным, так что замена р на х не может привести к тому, что два красных узла станут смежными. 3. Поскольку узел у не может быть корнем, если он был красным, корень остается черным.
Если узел у был черным, то могут возникнуть три проблемы, которые исправит вызов КВ-Ркьктк-Р1хиг. Во-первых, если у был корнем, а теперь новым корнем стал красный потомок у, нарушается свойство 2. Во-вторых, если и .г. и к. р красные, то нарушается свойство 4. И в-третьих, перемещение у в дереве Глава!3. Красно-черные деревья КВ-РЕьЕТЕ-р!ХОР (Т, Х) ! иййе х ф Т.
тоо1 и х. со1от == ВЕАСК 2 1Тх==х.р.1е/! 3 и = х.р.~дЫ 4 И и. со1от == КЕ0 5 и.со1от = В1.АСК 6 х.р.со!от = КЕ0 7 ЬЕЕТ-КОТАТЕ(Т, х.р) 8 и = х.р.пдЫ 9 11 и.1е/1, со!от == В1.АСК и и. т!дЫ. со!от == ВЬАСК !О и. со1ог = КЕ0 !! х=хр !2 е1зе И и. т!дЫ. со1от == ВЕАСК !3 и. 1е/1. со1ог = ВЬАСК и !4 пи.со1от = КЕ0 !5 к1Онт-кОТАте(Т, и) !б и = х.р.пдЫ !7 и. со1ог = х.р. со1от !8 х,р. со1от = ВоАСК !9 и, пдЫ, со1от = ВЬАСК 20 ЬЕЕТ-!СотАтЕ(Т,х.р) 2! х = Т.тоо1 22 е!яе (то же, что и в части зйеп, но с заменой "правого" (пяЫ) "левым" (!ей) и наоборот) 23 х.со1ог = ВЬАСК // Случай 1 // Случай 1 // Случай 1 // Случай 1 // Случай 2 // Случай 2 // Случай 3 // Случай 3 // Случай 3 // Случай 3 // Случай 4 // Случай 4 // Случай 4 // Случай 4 // Случай 4 Процедура ВВ-Реьете-Р1хир восстанавливает свойства 1, 2 и 4.
В упр. 13.4.1 я !3.42 требуется показать, что эта процедура восстанавливает свойства 2 и 4, приводит к тому, что любой простой путь, ранее содержавший у, теперь имеет на один черный узел меньше. Таким образом, для всех предков у оказывается нарушенным свойство 5.
Мы можем исправить ситуацию, утверждая, что узел х, ныне занимающий исходную позицию у, — "сверхчерный", т.е. при рассмотрении любого простого пути, проходящего через х, следует добавлять дополнительную единицу к количеству черных узлов. При такой интерпретации свойство 5 остается выполняющимся. При удалении или перемещении черного узла у мы передаем его "черноту" узлу х. Проблема заключается в том, что теперь узел х не является ни черным, ни красным, что нарушает свойство 1.
Вместо этого узел х окрашен либо "двалсды черным", либо "красно-черным" цветом, что дает при подсчете черных узлов на простых путях, содержащих х, вклад, равный соответственно 2 или 1. Атрибут со!от узла х при этом остается равным либо КЕ0 (если узел красно-черный), либо ВЕАск (если узел дважды черный). Другими словами, цвет узла х не соответствует его атрибуту со1от. Теперь рассмотрим процедуру !сВ-Реьете-Р1хце и то, как она восстанавливает красно-черные свойства дерева поиска. Часть Ш. Струюиуры данньи Збо так что в оставшейся части раздела мы обратим свое внимание на свойство 1.
Цель цикла угпйе в строках 1 — 22 заключается в перенесении дополнительной "черноты" вверх по дереву до тех пор, пока не выполнится одно из следующих условий. 1. х указывает на красно-черный узел — в этом случае мы просто делаем узел х "единожды черным" в строке 23. 2. х указывает на корень — в этом случае мы просто убираем излишнюю черноту. 3.
Выполнив некоторые повороты и перекраску, мы выходим из цикла. Внутри цикла ууййе х всегда указывает на дважды черный узел, не являющийся корнем. В строке 2 мы определяем, является ли х левым или правым дочерним узлом своего родителя х.р. (Приведен подробный код для ситуации, когда х— левый потомок. Для правого потомка код аналогичен, симметричен и скрыт за описанием в строке 22.) Поддерживается указатель ал, который указывает на второй потомок родителя х.
Поскольку узел з дважды черный, узел ю не может быть Т. па(; в противном случае количество черных узлов на простом пути от х. р к (единожды черному) листу ю было бы меньше, чем количество черных узлов на простом пути от х. р к х. Четыре разных возможных случаяз показаны на рис. 13.7. Перед тем как приступить к детальному рассмотрению каждого случая, убедимся, что в каждом из случаев преобразования сохраняется свойство 5.
Ключевая идея заключается в необходимости убедиться, что применяемые преобразования в каждом случае сохраняют количество черных узлов (включая дополнительную черноту в з) на пути от корня включительно до каждого из поддеревьев су, 13,..., с,. Таким образом, если свойство 5 выполнялось до преобразования, оно выполняется и после него. Например, на рис. 13.7, (а), который иллюстрирует случай 1, количество черных узлов на пути от корня до поддеревьев ся и ф равно 3 как до, так и после преобразования (не забудьте о том, что узел х — дважды черный).
Аналогично количество черных узлов на пути от корня до любого из поддеревьев 7, б, г и ~ равно 2 как до, так и после преобразования. На рис. 13.7,(б) подсчет должен включать значение с, равное значению атрибута со1ог корня показанного поддерева, которое может быть либо ккп, либо вьАск.
Если определить соип1(кпп) = О и соила(ВЬАСК) = 1, то на пути от корня до поддерева са количество черных узлов равно 2 + соип$(с); эта величина одинакова до и после выполнения преобразований. В такой ситуации после преобразования новый узел х имеет атрибут со1ог, равный с, но реально зто либо красно-черный узел (если с = ккп), либо дважды черный (если с = ВьАск). Прочие случаи могут быть проверены аналогично (см. упр. 13.4.5). как и а процедуре квпнаият-р!хну, случаи а процедуре кв-пиьиуи-р!хце ие яюиючся иааимоискчючающими. Часть дк Структуры данны» збг Случай Б Брат зо узла х — красный Случай 1 (строки 5 — 8 процедуры КВ-Рееете-Г!х~л и рис. 13.7, (а)) возникает, когда узел ю ("брат" узла х) — красный.
Поскольку ш должен иметь черные потомки, можно обменять цвета зе и х, р, а затем выполнить левый поворот вокруг х.р без нарушения каких-либо красно-черных свойств. Новый "брат" х, до поворота бывший одним из дочерних узлов и~, теперь черный. Таким путем случай 1 приводится к случаю 2, 3 или 4. Случаи 2, 3 и 4 возникают при черном узле ю и отличаются один от другого цветами дочерних по отношению к зс узлов. Случай 2. Узел то — черный, оба его дочерна» узла — черные В этом случае (строки 1О и 11 процедуры КВ-!3н.ете-р!хл' и рис. 13.7, (б)) оба дочерних узла щ — черные. Поскольку узел ю также черный, мы можем забрать черную окраску у х и зс, сделав х единожды черным, а ш — красным.
Для того чтобы компенсировать удаление черной окраски х и ю, мы можем добавить дополнительный черный цвет узлу х. р, который до этого мог быть как красным, так и черным. После этого будет выполнена следующая итерация цикла, в которой роль х будет играть текущий узел х.р. Заметим, что если мы переходим к случаю 2 от случая 1, новый узел х — красно-черный, поскольку исходный узел х, р был красным. Следовательно, значение с атрибута со!от нового узла х равно ке!э и цикл завершается при проверке условия цикла. После этого новый узел х окрашивается в обычный черный цвет в строке 23.
Случай 3. Брат и узла х — черный, левый дочерний узел узла то — красный, а правый — черный В этом случае (строкн 13-16 процедуры КВ-Рееете-Р!хце и рис. 13.7,(в)) узел щ — черный, его левый дочерний узел — красный, а правый — черный. Мы можем обменять цвета ы и его левого дочернего узла ю. 1е(1, а затем выполнить правый поворот вокруг ш без нарушения каких-либо красно-черных свойств. Новым "братом'* узла х после этого будет черный узел с красным правым дочерним узлом, и, таким образом, случай 3 приводится к случаю 4.
'Случай 4. Брат зо узла х черный, а правый дочерний узел узза то красный В этом случае (строки 17-21 процедуры КВ-Пееете-Р!хп' и рис. 13.7,(г)) узел щ — черный, а его правый дочерний узел — красный. Выполняя обмен цветов и левый поворот вокруг х. р, мы можем устранить излишнюю черноту в х, делая его просто черным, без нарушения каких-либо красно-черных свойств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
