Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 71
Текст из файла (страница 71)
13.7. Перед тем как приступить к детальному рассмотрению каждого случая, убедимся, что в каждом из случаев преобразования сохраняется свойство 5. Ключевая идея заключается в необходимости убедиться, что при преобразованиях в каждом случае количество черных узлов (включая дополнительную черноту в х) на пути от корня включительно до каждого из поддеревьев ск,,З, ..., ~ остается неизменным. Таким Как и в проиелуре йВ 1нзякт Вхов, случаи ие являются взвимоискл|очающими. 354 Часть 1П. Структуры данных Нооыах1 л гг ,4В. Сэ оог ~ — о ~о )г Со оооо 4 ,.Ф о 11 г о Иовом г = гож ~71 Рис.
13.7. Возможные ситуации, возникающие в цикле и Ы1е процедуры КВ 0вьвта Яхин Темные узлы имеют цвет вьАск, темно-серые — квп, а светлые могут иметь любой цвет (на рисунке показан как с и с'). Греческими буквамн показаны произвольные поддеревья образом, если свойство 5 выполнялось до преобразования, то оно выполняется и после него. Например, на рис.
13.7а, который иллюстрирует случай 1, количество черных узлов на пути от корня до поддеревьев гз и )3 равно 3, как до, так и после преобразования (не забудьте о том, что узел х — дважды черный). Аналогично, количество черных узлов на пути от корня до любого из поддеревьев 7, б„е и г, равно 2, как до, так и после преобразования. На рис. 13.7б подсчет должен включать значение с, равное значению атрибута со1ог корня показанного поддерева, которое может быть либо кап, либо вьАск. Так, на пути от корня до поддерева а количество черных узлов равно 2 плюс величина, равная 1, если с равно ньлск, и О, если с равно инп; эта величина одинакова до и после выполнения преобразований.
В такой ситуации после преобразования новый узел х имеет атрибут со1от, равный с, но реально это либо красно-черный узел (если с = КЕ13), Глава 13. Красно-черные деревья 355 либо дважды черный (если с = В1.АСК). Прочие случаи могут быть проверены аналогичным способом (см. упражнение 13.4-5). Случай 1: узел ю красный. Случай 1 (строки 5-8 процедуры КВ Рн.ЕТЕ г!Х!!Р и рнс. 13.7а) возникает, когда узел ю (" брат'* узла х) — красный. Поскольку ю должен иметь черных потомков, можно обменять цвета ю и р [х], а затем выполнить левый поворот вокруг р [х] без нарушения каких-либо красно-черных свойств.
Новый "брат" х, до поворота бывший одним из потомков ю, теперь черный. Таким путем случай 1 приводится к случаю 2, 3 илн 4. Случаи 2, 3 и 4 возникают при черном узле ю и отличаются друг от друга цветами дочерних по отношению к ю узлов. Случай 2: узел ю черный, оба его дочерних узла черные. В этом случае (строки 10-11 процедуры КВ Реьете г!х!л и рис. 13.7б) оба дочерних узла ю черные. Поскольку узел ю также черный, мы можем забрать черную окраску у х и ю, сделав х единожды черным, а ю — красным.
Для того чтобы компенсировать удаление черной окраски у х и ю, мы можем добавить дополнительный черный цвет узлу р [х], который до этого мог быть как красным, так и черным. После этого будет выполнена следующая итерация цикла, в которой роль х будет играть текущий узел р [х]. Заметим, что если мы переходим к случаю 2 от случая 1, новый узел х — красно-черный, поскольку исходный узел р [х] был красным. Следовательно, значение с атрибута со1от нового узла х равно ке!э и цикл завершается при проверке условия цикла. После этого новый узел х окрашивается в обычный черный цвет в строке 23. Случай 3: узел ю черный, его левый дочерний узел красный, а правый— черный.
В этом случае (строки 13-16 процедуры КВ 13еьете Р!хпР и рис. 13.7в) узел ю черный, его левый дочерний узел красный, а правый — черный. Мы можем обменять цвета ю и 1ег! [ю], а затем выполнить правый поворот вокруг ю без нарушения каких-либо красно-черных свойств. Новым "братом" узла х после этого будет черный узел с красным правым дочерним узлом, и таким образом мы привели случай 3 к случаю 4.
Случай 4: узел ю черный, его правый дочерний узел красный. В этом случае (строки 17-21 процедуры КВ 13еьете Р!хпР и рис. 13.7г) узел ю черный, а его правый дочерний узел — красный. Выполняя обмен цветов и левый поворот вокруг р [х], мы можем устранить излишнюю черноту в х, делая его просто черным, без нарушения каких-либо красно-черных свойств. Присвоение х указателя на корень дерева приводит к завершению работы при проверке условия цикла при следующей итерации. Часть 1П.
Структуры данных 356 Анализ Упражнения Покажите, что после выполнения процедуры КВ Ре!.ете Р!хг!Р корень дерева должен быть черным. Покажите, что если в процедуре ВВ 1зеьете и х, и р [х] красные, то прн вызове КВ 13ЕЕЕТЕ Р!Х!Л*(Т, х) свойство 4 будет восстановлено. В упражнении 13.3-2 вы построили красно-черное дерево, которое яв- ляется результатом последовательной вставки ключей 41, 38, 31, 12, 19 и 8 в изначально пустое дерево.
Покажите теперь, что в результате по- следовательного удаления ключей 8, 12, 19, 31, 38 и 41 будут получаться красно-черные деревья. В каких строках кода процедуры ВВ Рн.ЕТЕ Р!х!!Р мы можем обращать- ся к ограничителю пп [2'] или изменять его? Для каждого из случаев, показанных на рис. 13.7, подсчитайте количе- ство черных узлов на пути от корня показанного полдерева до каждого из поддеревьев о, !3,..., С и убедитесь, что оно не меняется при выпол- нении преобразований. Если узел имеет атрибут со1от, равный с или с', воспользуйтесь функцией соип1 (с), которая для красного узла равна О, а для черного — 1. Профессор озабочен вопросом, не может ли узел р [х] не быть черным в начале случая 1 в процедуре КВ 1Зееете Р!х!!Р. Если профессор прав, то строки 5-6 процедуры ошибочны.
Покажите, что в начале случая 1 узел р [х] не может не быть черным, так что профессору нечего волно- ваться. 13.4-1. 13.4-2. 13.4-3. 13.4-4. 13.4-5. 13.4-6. 13.4-7. Предположим, что узел х вставлен в красно-черное дерево при помощи процедуры ВВ 1!чзект, после чего немедленно удален из этого дерева. Будет ли получившееся в результате вставки и удаления красно-черное дерево таким же, как и исходное? Обоснуйте ваш ответ. Чему равно время работы процедуры КВ 0е!.ете? Поскольку высота дерева с и узлами равна О(18п), общее время работы процедуры без выполнения вспомогательной процедуры ВВ Оееете Р!хт!Р равно О (18п).
В процедуре ВВ 13а.ете Р!х!!Р в случаях 1, 3 и 4 завершение работы происходит после выполнения постоянного числа изменений цвета и не более трех поворотов. Случай 2— единственный, после которого возможно выполнение очередной итерации цикла М!1!е, причем указатель х перемещается вверх по дереву не более чем О (18п) раз, и никакие повороты при этом не выполняются. Таким образом, время работы процедуры КВ Ое!.ете Р!х!!Р составляет О (18п), причем она выполняет не более трех поворотов.
Общее время работы процедуры ВВ !зенте, само собой разумеется, также равно О (18 и). Глава 13. Красно-черные деревья 357 / / '>--- 2 7 (а Рис. 13.8. Бинарное дерево поиска с ключами 2, 3, 4, 7, 8 и 1О (а) и перманентное бинарное дерево поиска, получающееся в процессе вставки ключа 5 (б) Задачи 13-1. Перманентные динамические множества Иногда полезно сохранять предыдущие версии динамического множества в процессе его обновления. Такие множества называются перманенпьчыми (регз)з1еп1).
Один из способов реализации перманентного множества состоит в копировании всего множества при внесении в него изменений, однако такой подход может существенно замедлить работу программы и вызвать перерасход памяти. Зачастую эту задачу можно решить гораздо более эффективно.
Рассмотрим перманентное множество Я с операциями 1нзнит, Рнытн и ЯБАнсн, которое реализуется с использованием бинарных деревьев поиска, как показано на рис. 13.8а. Для каждой версии множества мы храним отдельный корень. Для добавления ключа 5 в множество создается узел с ключом 5, который становится левым дочерним узлом нового узла с ключом 7, так как менять существующий узел с ключом 7 мы не можем. Аналогично, новый узел с ключом 7 становится левым потомком нового узла с ключом 8, правым потомком которого является существующий узел с ключом 10. Новый узел с ключом 8 становится, в свою очередь, правым потомком нового корня г' с ключом 4, левым потомком которого является существующий узел с ключом 3.
Таким образом, мы копируем только часть дерева, а в остальном используем старое дерево, как показано на рис. 13.8б. Предположим, что каждый узел дерева имеет поля кеу, 1е7г и тюдор, но не имеет поля с указателем на родительский узел (см. также упражнение 13.3-6). 358 Часть 111. Структуры данных а) Определите, какие узлы перманентного бинарного дерева поиска должны быть изменены при вставке в него ключа /с или удалении узла у в общем случае.
б) Напишите процедуру Рекязтнчт Ткеп 1нзнкт, которая для данного перманентного дерева Т и вставляемого ключа Л возвращает новое перманентное дерево Т', получающееся в результате вставки й в Т. в) Если высота перманентного бинарного дерева поиска Т равна Л, сюлько времени будет работать ваша реализация Рекязтнчт Ткее 1нзпкт и какие требования к памяти она предъявляет? (Количество требуемой памяти пропорционально количеству новых узлов.) г) Предположим, что в каждом узле имеется поле указателя на родительский узел. В этом случае процедура Рекытент Тине 1нзект должна выполнять дополнительное копирование. Докажите, что в этом случае время работы процедуры и объем необходимой памяти равны й [и), где и — количество узлов в дереве. д) Покажите, как можно использовать красно-черные деревья для того, чтобы при вставке и удалении в наихудшем случае время работы процедуры и объем необходимой памяти были равны О (18 и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
