Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 70
Текст из файла (страница 70)
Часть 111. Структуры данных 350 Анализ Чему равно время работы процедуры КВ 1мзнит? Поскольку высота красно- черного дерева с и узлами равна О (18п), выполнение строк 1 — 16 процедуры КВ 1нзект требует О (1бп) времени. В процедуре КВ 1ыеект Р!АР цикл ттЫ!е повторно выполняется только в случае 1, и в этом случае указатель з перемещается вверх по дереву на два уровня. Таким образом, общее количество возможных выполнений тела цикла ттй1!е равно О (18 и).
Таким образом, общее время работы процедуры КВ 1ызект равно О (18и). Интересно, что в ней никогда не выполняется больше двух поворотов, поскольку цикл и ййе в случаях 2 и 3 завершает работу. Упражнения 13.3-1. В строке 16 процедуры КВ 1ызект мы окрашиваем вновь вставленный узел в красный цвет. Заметим, что если бы мы окрашивали его в черный цвет, то свойство 4 не было бы нарушено. Так почему же мы не делаем этого? 13.3-2. Изобразите красно-черные деревья, которые образуются при последовательной вставке ключей 41, 38, 31, 12, 19 и 8 в изначально пустое красно- черное дерево.
13.3-3. Предположим, что черная высота каждого из поддеревьев а,,В, у, 6 и е на рис. 13.5 и 13.6 равна Й. Найдите черные высоты каждого узла на этих рисунках, чтобы убедиться, что свойство 5 сохраняется при показанных преобразованиях. 13.3-4. Профессор озабочен вопросом, не может ли в процедуре КВ 1ызеит Р~хг1Е произойти присвоение значение ке0 узлу пг1[Т] — ведь в этом случае проверка в строке 1 не вызовет окончания работы цикла в случае, если г — корень дерева. Покажите, что страхи профессора безосновательны, доказав, что процедура КВ 1ызект йхиг никогда не окрашивает пи [Т[ в красный цвет. 13.3-5. Рассмотрим красно-черное дерево, образованное вставкой и узлов при помощи процедуры КВ 1ыьект.
Докажите, что если п > 1, то в дереве имеется как минимум один красный узел. 13.3-6. Предложите эффективную реализацию процедуры КВ 1ызнкт в случае, когда представление красно-черных деревьев не включает указатель на родительский узел. Глава 13. Красно-черные деревья 351 13.4 Удаление Как и остальные базовые операции над красно-черными деревьями с и узлами, удаление узла выполняется за время 0 (1ки). Удаление оказывается несколько более сложной задачей, чем вставка. Процедура КВ Редеете представляет собой немного измененную процедуру Ткее !За.ете из раздела 12.3. После удаления узла в ней вызывается вспомогательная процедура КВ 13ет.ете Ртхиг, которая изменяет цвета и выполняет повороты для восстановления красно-черных свойств дерева: КВ !Знаете(Т,з) 1 !Г 1ет2(з] = и!1(Т] или пдйф] = и11[Т] 2 г!теп у — з 3 е1зе у — Ткее Бгтссеззок(г) 4 !!' 1е71[у] ф ий[Т] 5 Феп х — 1ефу] 6 е!зе х — пди1[у] 7 р[х] — р(у] 8 !!' р[у] = и!1(Т] 9 !!зеп тоо1(Т] +- х 10 е1зе !!' у = 1еГ1(р[у]] 11 Феп 1е7г(р[у]] — х 12 е!зе пдМ[р[у]] — х 13 гауфа 14 Феп йеу[з] ~ — Йеу[у] 15 Копируем сопутствующие данные у в з 16 !! со1от'[у] = В1.Аск 17 !!теп КВ !Зеваете Р!АР(Т, х) 18 ге!ига у Имеется три различия между процедурами Ткее !Зеваете и КВ Ре1ете.
Вопервых, все ссылки на ми. в Ткее !Зенте заменены в КВ !Зеваете ссылками на ограничитель и!! [Т]. Во-вторых, удалена проверка в строке 7 процедуры Ткее !Зеваете (равно ли х н1е), и присвоение р(х] — р(у] выполняется в процедуре КВ 13ЕЕЕтЕ безусловно. Таким образом, если х является ограничителем и!! [Т], то его указатель на родителя указывает на родителя извлеченного из дерева узла у. В-третьих, в строках 16-17 процедуры КВ Рн.втн в случае, если узел у — черный, выполняется вызов вспомогательной процедуры КВ 13е~.ете Р1хнк Если узел у — красный, красно-черные свойства при извлечении у из дерева сохраняются в силу следующих причин: ° никакая черная высота в дереве не изменяется; ° никакие красные узлы не становятся соседними; 352 Часть П1.
Структуры данных ° так как у не может быть корнем в силу своего цвета, корень остается черным. Узел х, который передается в качестве параметра во вспомогательную процедуру КВ !3а.ЕТЕ Р!ХОР, является одним из двух узлов: либо это узел, который был единственным потомком у перед извлечением последнего из дерева (если у у был дочерний узел, не являющийся ограничителем), либо, если у узла у нет дочерних узлов, х является ограничителем и!1 [Т]. В последнем случае безусловное присвоение в строке 7 гарантирует, что родительским по отношению к х узлом становится узел, который ранее был родителем у, независимо от того, является ли х внутренним узлом с реальным ключом или ограничителем и!! [Т]. Теперь мы можем посмотреть, как вспомогательная процедура КВ 1мзеет р!ХОР справляется со своей задачей восстановления красно-черных свойств дерева поиска. КВ !Зеваете Р!хОР(Т, х) ! е!з!!е х Ф тооЯ[Т] и со1от[х] = вьАск 2 !!о !Т х = 1е71[р[х]] 3 г!зеп ю — пдй1[р[х)) 4 !! со!от(ю] = КЕО 5 т!яеп со1от[ю] вьАск > Случай ! 6 со1от(р[х]] — КЕО !> Случай 1 7 ЬЕРТ КОТАТЕ(Т, р[х]) с Случай 1 8 ю — пдМ[р[х)] с Случай 1 9 !Г со1от[1е1! [ю]] = В!.АСК и со1от[пдй![ю]] = В!.АСк !О 1!!еп со1от[ю] — КЕО с Случай 2 !! х — р[х] !> Случай 2 !2 е!зе !Т со1от(пдЫ[ю)] = В! Аск !3 т!зеп со!от [1еЯиЦ вЂ” в!.Аск !> Случай 3 !4 со1от[ю] — КЕО с Случай 3 !5 К!ОНТ КОТАТЕ(Т, ю) с> Случай 3 !6 ю — ад!!1[р[х]] !> Случай 3 !7 со 1 от [ю] — со1от !р[х]] !> Случай 4 !8 со1от[р[х]] < — ВЬАСК !> Случай 4 !9 со1от [тядЩиф — В!.АСК !> Случай 4 20 ЬЕРТ КОТАТЕ(Т, р[х)) !> Случай 4 2! х — таодТ] с Случай 4 22 е!зе (то же, что и в "!!зеп", с заменой 1е7г на пдву и наоборот) 23 со1от[х] — В!.АСК Если извлекаемый из дерева в процедуре КВ 13н.ЕТЕ узел у черный, то могут возникнуть три проблемы.
Во-первых, если у был корнем, а теперь корнем стал красный потомок у, нарушается свойство 2. Во-вторых, если и х, и р(у) (который теперь является также р [х)) были красными, то нарушается свойство 4. И, в-третьих, удаление у приводит к тому, что все пути, проходившие через у, Глава 13. Красно-черные деревья 353 теперь имеют на один черный узел меньше. Таким образом, для всех предков у оказывается нарушенным свойство 5. Мы можем исправить ситуацию, утверждая, что узел х — "сверхчерный", т.е. при рассмотрении любого пути, проходящего через х, добавлять дополнительную 1 к количеству черных узлов. При такой интерпретации свойство 5 остается выполняющимся. При извлечении черного узла у мы передаем его "черноту" его потомку.
Проблема заключается в том, что теперь узел х не является ни черным, ни красным, что нарушает свойство 1. Вместо этого узел х окрашен либо "дважды черным", либо "красно-черным" цветом, что дает при подсчете черных узлов на пути, содержащем х, вклад, равный, соответственно, 2 или 1. Атрибут со1ог узла х при этом остается равен либо вг.лск (если узел дважды черный), либо кнп (если узел красно-черный). Другими словами, цвет узла не соответствует его атрибуту со1ог. Процедура КВ РньнтЕ Рахов восстанавливает свойства 1, 2 и 4.
В упражнениях 13.4-1 и 13.4-2 требуется показать, что данная процедура восстанавливает свойства 2 и 4, так что в оставшейся части данного раздела мы сконцентрируем свое внимание на свойстве 1. Цель цикла угй11е в строках 1-22 состоит в том, чтобы переместить дополнительную черноту вверх по дереву до тех пор, пока не выполнится одно из перечисленных условий. 1. х указывает на красно-черный узел — в этом случае мы просто делаем узел х "единожды черным" в строке 23. 2. х указывает на корень — в этом случае мы просто убираем излишнюю черноту. 3.
Можно выполнить некоторые повороты и перекраску, после которых двойная чернота будет устранена. Внутри цикла зу)н)е х всегда указывает на дважды черную вершину, не являющуюся корнем. В строке 2 мы определяем, является лн х левым или правым дочерним узлом своего родителя р [х]. Далее приведен подробный код для ситуации, когда х — левый потомок. Для правого потомка код аналогичен и симметричен, и скрьгг за описанием в строке 22. Указатель ш указывает на второго потомка родителя х. Поскольку узел х дважды черный, узел ш не может быть п11 [2'] — в противном случае количество черных узлов на пути от р [х] к (единожды черному) листу было бы меньше, чем количество черных узлов на пути от р[х] к х. Четыре разных возможных случая' показаны на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
