Алгоритмы - построение и анализ (1021735), страница 69
Текст из файла (страница 69)
Структуры данных Нооыах1 л гг ,4В. Сэ оог ~ — о ~о )г Созоао 4 — о ~л ~,. '~6~, о 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Зееете Р!х!!Р. Если профессор прав, то строки 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 и). 13-2. Операция объединения красно-черных деревьев Операция объединения Оо1п) применяется к двум динамическим множествам Яг и Яг н элементу х (такому, что для любых хз е Яз и хг Е Яг выполняется неравенство Леу [хг] < Ьеу «х] < Ьеу [хг]). Результатом операции является множество Я = Яд О 1х) О Яг. В данной задаче мы рассмотрим реализацию операции объединения красно-черных деревьев.
а) Будем хранить черную высоту красно-черного дерева Т как атрибут ЬЬ [Т]. Покажите, что этот атрибут может поддерживаться процедурами КВ 1нзнкт и ВВ 13н.рте без использования дополнительной памяти в узлах дерева и без увеличения асимптотического времени работы процедур. Покажите, что при спуске по дереву Т можно определить черную высоту каждого посещаемого узла за время О [1) на каждый посещенный узел. Мы хотим реализовать операцию ВВ 10~и(Ты х, Тг), которая, разрушая деревья Тз и Тг, возвращает красно-черное дерево Т = Тг 0 1х) О Тг. Пусть и — общее количество узлов в деревьях Тг и Тг. б) Считая, что ЬЬ [Тг] > ЬЬ [Тг], разработайте алгоритм, юторый за время О (18 и) находит среди черных узлов дерева Ты черная высота которых равна ЬЬ [Тг], узел у с наибольшим значением ключа.
в) Пусть Т, — поддерево с корнем у. Опишите, как заменить Тд на Тк 0 [х) 0 Тг за время О (1) с сохранением свойства бинарного дерева поиска. Глава 13. Красно-черные деревья 359 г) В какой цвет надо окрасить х, чтобы сохранились красно-черные свойства 1, 3 и 5? Опишите, как восстановить свойства 2 и 4 за время О (!яп). д) Докажите, что предположение в пункте б) данной задачи не приводит к потере общности. Опишите симметричную ситуацию, возникающую при ЬБ.
[Т~] < ЬЬ [Тз]. е) Покажите, что время работы процедуры ВВ 10пч равно О (1йп). 13-3. АЧЬ-деревья АИ:дерево представляет собой бинарное дерево поиска со сбалансированной высогиой: для каждого узла х высота левого и правого поддеревьев х отличается не более чем на 1. Для реализации АЧЬ-деревьев мы воспользуемся дополнительным полем в каждом узле дерева Ь [х], в котором хранится высота данного узла. Как и в случае обычных деревьев поиска, мы считаем, что тоо1 [Т] указывает на корневой узел. а) Докажите, что АЧ1.-дерево с п узлами имеет высоту О (1б п). (Указание: докажите, что в АЧЬ-дереве высотой л имеется как минимум Гь узлов, где Е~ — 6-е число Фибоначчи.) б) Для вставки узла в АЧ1.-дерево он сначала размещается в соответствующем месте бинарного дерева поиска.
После этого дерево может оказаться несбалансированным, в частности, высота левого и правого потомков некоторого узла может отличаться на 2. Разработайте процедуру Вльлнсе(х), которая получает в качестве параметра поддерево с корнем в узле х, левый и правый потомки которого сбалансированы по высоте и имеют высоту, отличающуюся не более чем на 2 (т е. [6 [тъдМ [х]] — Ь [1ефх]] [ < 2), и изменяет его таким образом, что поддерево с корнем в узле х становится сбалансированным по высоте. (Указание: воспользуйтесь поворотами.) в) Используя решение подзадачи б, разработайте рекурсивную процедуру АЧЬ 1мзнкт(х, з), которая получает в качестве параметров узел х в АЧЬ-дереве и вновь созданный узел г (с заполненным полем ключа) и вставляет з в поддерево, корнем которого является узел х, сохраняя при этом свойство, заключающееся в том, что х — корень АЧЬ-дерева. Как и в случае процедуры Ткнн азият из раздела 12.3, считаем, что поле йеу [х] заполнено и что 1е11 [з] = = г(дМ [з] = хн..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
