Алгоритмы - построение и анализ (1021735), страница 68
Текст из файла (страница 68)
Когда мы приходим к случаю 3 (либо непосредственно, либо поворотом из случая 2), узел у имеет черный цвет (поскольку иначе мы бы получили случай 1). Кроме того, обязательно существует узел Глава 13. Красно-черные деревья 349 а ууя а р о ~л,'у д о Случвй 2 случай 3 Рис. 13.6. Случаи 2 н 3 процедуры КВ 1ньввт Р~хиг р [р [я]], так как мы доказали, что этот узел существовал при выполнение строк 2 и 3, а также что после перемещения узла я на один узел вверх в строке 10 с последующим опусканием в строке 11 узел р [р [з]] остается неизменным. В случае 3 мы выполняем ряд изменений цвета и правых поворотов, которые сохраняют свойство 5.
После этого, так как у нас нет двух идущих подряд красных узлов, работа процедуры завершается. Больше тело цикла иЫ1е не выполняется, так как узел р [я] теперь черный. Теперь покажем, что случаи 2 и 3 сохраняют инвариант цикла. (Как мы только что доказали, перед следующей проверкой в строке 1 узел р [з] будет черным и тело цикла больше выполняться не будет.) а) В случае 2 выполняется присвоение, после которого г указывает на красный узел р [я]. Никаких других изменений г или его цвета в случаях 2 и 3 не выполняется.
б) В случае 3 узел р[а] делается черным, так что если р[-] в начале следующей итерации является корнем, то этот корень — черный. в) Как и в случае 1, в случае 2 и 3 свойства 1, 3 и 5 сохраняются. Поскольку узел л в случаях 2 и 3 не является корнем, нарушение свойства 2 невозможно. Случаи 2 и 3 не могут приводить к нарушению свойства 2, поскольку при повороте в случае 3 красный узел становится дочерним по отношению к черному.
Таким образом, случаи 2 и 3 приводят к коррекции нарушения свойства 4, при этом не внося никаких новых нарушений красно-черных свойств. Показав, что при любой итерации инвариант цикла сохраняется, мы тем самым показали, что процедура ВВ 1ньеит Р~х22Р корректно восстанавливает красно-черные свойства дерева. Часть 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'] — в противном случае количество черных узлов на пути от р [х] к (единожды черному) листу было бы меньше, чем количество черных узлов на пути от р[х] к х. Четыре разных возможных случая' показаны на рис.
13.7. Перед тем как приступить к детальному рассмотрению каждого случая, убедимся, что в каждом из случаев преобразования сохраняется свойство 5. Ключевая идея заключается в необходимости убедиться, что при преобразованиях в каждом случае количество черных узлов (включая дополнительную черноту в х) на пути от корня включительно до каждого из поддеревьев ся,,З, ..., ~ остается неизменным. Таким Как и в проиелуре йВ 1нзякт Вхов, случаи ие являются взвимоискл|очающими. 354 Часть 1П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
