Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 76
Текст из файла (страница 76)
Присвоение х указателя на корень дерева приводит к завершению работы цикла при проверке условия при следующей итерации. Анализ Чему равно время работы процедуры КВ-ПЕСЕТЕ? Поскольку высота дерева с п узлами равна 0(18 ц), общая стоимость процедуры без вызова вспомога- дева !3. КРоено-черные деревне 363 тельной процедуры КВ-Рееете-Р1хБР равна 0(18 и). В процедуре КВ-РееетеГш~г в случаях 1, 3 и 4 завершение работы происходит после выполнения фиксяроваиного числа изменений цвета и не более трех поворотов. Случай 2— единственный, после которого возможно выполнение очередной итерации цикла иййе, причем указатель х перемещается вверх по дереву не более чем 0(18 и) раз и никакие повороты при этом не выполняются. Таким образом, время работы процедуры КВ-Рн.ете-г3Х33 составляет О(18 и), причем она выполняет не более трех поворотов.
Общее время работы процедуры КВ-Рееете, само собой разумеется, также равно 0(18 и). Упражнения !3,4.1 Покажите, что после выполнения процедуры КВ-РЕ~.ЕтЕ-Е~Х~Л' корень дерева должен быть черным. 33.43 Покажите, что если в процедуре КВ-Рееете и х, и х, р красные, то при вызове КВ-РН.ЕтЕ-Р~ХГЛ'(Т, х) свойство 4 будет восстановлено. 33.4.3 В упр. !3.3.2 вы построили красно-черное дерево, которое является результатом последовательной вставки ключей 41, 38, 31, 12, 19, 8 в изначально пустое дерево. Покажите теперь красно-черные деревья, которые будут получаться в результате последовательного удаления ключей в порядке 8, 12, 19, 31, 38, 41.
!3.44 В каких строках кода процедуры КВ-РЕЕЕтЕ-ЕЗХит мы можем обращаться к ограничителю Т. ий или изменять его? !3.4.5 Для каждого из случаев, показанных на рис. 13.7, подсчитайте количество черных узлов на пути от корня показанного поддерева до каждого из поддеревьев а„б,..., ~ и убедитесь, что оно не меняется при выполнении преобразований.
Если узел имеет атрибут со!ог, равный с нли с', воспользуйтесь символьными обозначениями сопп1(с) или сопит(с'). !3.4.6 Профессор озабочен вопросом, не может ли узел х. р не быть черным в начале случая 1 в процедуре КВ-Рн.ете-а!хит. Если профессор прав, то строки 5 и 6 процедуры ошибочны. Покажите, что в начале случая 1 узел х.р не может не быть черным, так что профессору нечего волноваться.
33.4. 7 Предположим, что узел х вставлен в красно-черное дерево с помощью процедуры КВ-1иеект, после чего немедленно удален из этого дерева процедурой КВ- Часть!П. Струкнуры с)анных 1)Бьете. Будет ли полученное в результате красно-черное дерево таким же, как и исходное? Обоснуйте свой ответ. Задачи 13.1.
Перманентные динамические мнвмсества Иногда полезно сохранять предыдущие версии динамического множества в процессе его обновления. Такие множества называются нернанентными (регз(я(еп1). Один из способов реализации перманентного множества состоит в копировании всего множества при внесении в него изменений, однако такой подход может существенно замедлить работу программы и вызвать перерасход памяти.
Зачастую эту задачу можно решить гораздо более эффективно. Рассмотрим перманентное множество Я с операциями 1)чзеит, 1)Бьете и Белксн, которое реализуется с использованием бинарных деревьев поиска, как показано на рис. 13.8,(а). Для каждой версии множества мы поддерживаем отдельный корень. Для добавления ключа 5 в множество создается новый узел с ключом 5, который становится левым дочерним узлом нового узла с ключом 7, так как менять существующий узел с ключом 7 мы не можем. Аналогично новый узел с ключом 7 становится левым потомком нового узла с ключом 8, правым потомком которого является существующий узел с ключом 10.
Новый узел с ключом 8 становится, в свою очередь, правым потомком нового корня г' с ключом 4, левым потомком которого является существующий узел с ключом 3. Таким образом, мы копируем только часть дерева, а в остальном используем старое дерево, как показано на рис. 13.8, (б). Предположим, что каждый узел дерева имеет атрибуты кеу, 1е1( и пуЬ(, но не имеет атрибута с указателем на родительский узел (см. также упр. 13.3.6). )'-'-) 2 (.7 ) (з)0) (б) (а) Рнс. 13.8. (а) Бинарное дерево поиска с ключами 2, 3, 4, 7, 8, 10. (6) Перманентное бинарное дерево поиска, полученное в результате вставки ключа 5. Последняя версия множества состоит из узлов, достижимых из кориа е', а предыдущая версия состоит из узлов, достижимых из г. Темные узлы добавлены при вставке ключа б.
Глава КК Красно-черные деревья ьь Определите, какие узлы перманентного бинарного дерева поиска должны быть изменены при вставке в него ключа Ь или удалении узла у в общем случае. б. Напишите процедуру Рекязтемт-Ткее-1мзект, которая для данного перманентного дерева Т и вставляемого ключа й возвращает новое перманентное дерево Т', получающееся в результате вставки lс в Т. в. Если высота перманентного бинарного дерева поиска Т равна Ь, сколько времени будет работать ваша реализация Рекз!зтехт-Ткее-1хзект и какие требования к памяти она предъявляет? (Количество требуемой памяти пропорционально количеству новых узлов.) к Предположим, что в каждом узле имеется атрибут, который представляет собой указатель на родительский узел. В этом случае процедура РЕКЫБТЕМТТкее-1мзект должна выполнять дополнительное копирование. Докажите, что в этом случае время работы процедуры и объем необходимой памяти равны Й(п), где п — количество узлов в дереве. д.
Покажите, как можно использовать красно-черные деревья для того, чтобы гарантировать при вставке и удалении в наихудшем случае равенство 0(1я н) времени работы процедуры и объема необходимой памяти. 13.3. Онерация соединения красно-черных деревьев Операция соединения Оо)п) применяется к двум динамическим множествам Бь и Яз и элементу х (такому, что для любых х~ Е Яь и хз е Яз выполняется неравенство хь.йеу < х.йеу < хз. Ьеу).
Результатом операции является множество Я = 51 О (х) 0 Яз. В данной задаче мы рассмотрим реализацию операции соединения красно-черных деревьев. а. Будем хранить черную высоту красно-черного дерева Т как новый атрибут Т. ЬЬ. Покажите, что этот атрибут может поддерживаться процедурами КВ1мзект и КВ-тэееете без использования дополнительной памяти в узлах дерева и без увеличения асимптотического времени работы процедур. Покажите, что при спуске по дереву Т можно определить черную высоту каждого посещаемого узла за время 0(1) на каждый посещенный узел. Мы хотим реализовать операцию ВВ-1опч(ТП х, Тз), которая, разрушая деревья Т1 и Тз, возвращает красно-черное дерево Т = Тт О (х) 0 Тз. Пусть и — общее количество узлов в деревьях Ть и Тз.
6. Считая, что Т1. ЬЬ > Тз. ЬЬ, разработайте алгоритм, который за время 0(1я н) находит в дереве Т1 среди узлов, черная высота которых равна Тз. ЬЬ, черный узел у с наибольшим значением ключа. в. Пусть Тн — поддерево с корнем у. Опишите, как заменить Т„на Тн О (х) О Тз за время 0(1) с сохранением свойства бинарного дерева поиска. Часть Ш.
Структуры дстныл Збб * В какой цвет нужно окрасить х, чтобы сохранились красно-черные свойства 1, 3 и 5? Опишите, как восстановить свойства 2 и 4 за время 0(!пи). д. Докажите, что предположение в и. (б) данной задачи не приводит к потере общности. Опишите симметричную ситуацию, возникающую при Тц ЬЬ ( Т,.ЬЬ. в. Покажите, что время работы процедуры КВ-1опч равно О(1яп). 13.3.
А рХ-деревья АИ:дерево представляет собой бинарное дерево поиска со сбалансированной высотой: для каждого узла х высота левого и правого поддеревьев х отличается не более чем на 1. Для реализации АЧ(.-деревьев мы воспользуемся дополнительным атрибутом х.Ь в каждом узле дерева, в котором хранится высота данного узла. Как и в случае обычных деревьев поиска, мы считаем, что Т.
гоо1 указывает на корневой узел. ьь Докажите, что АЧЕ-дерево с и узлами имеет высоту 0(1я и). (Указание: докажите, что в АЧ1.-дереве высотой Ь имеется как минимум Еь узлов, где сь— Ь-е число Фибоначчи.) б. Для вставки узла в АЧ1.-дерево он сначала размещается в соответствующем месте бинарного дерева поиска. После этого дерево может оказаться несбалансированным, в частности, высота левого и правого потомюв некоторого узла может отличаться на 2, Разработайте процедуру Вм.Аыск(х), которая получает в качестве параметра поддерево с корнем в узле х, левый и правый потомки которого сбалансированы по высоте и имеют высоту, отличающуюся не более чем на 2 (т.е.
(х, гьдЬЬ Ь вЂ” х. 1еЯ.Ь~ ( 2), и изменяет его таким образом, что поддерево с юрием в узле х становится сбалансированным по высоте. (Указание: воспользуйтесь поворотами.) в. Используя решение подзадачи (б), разработайте рекурсивную процедуру АЧ1,-1ызпкт(х,з), которая получает в качестве параметров узел х в АЧЕ- дереве и вновь созданный узел х (с заполненным полем ключа) и вставляет з в поддерево, корнем которого является узел х, сохраняя при этом свойство, заключающееся в том, что х — корень АЧ1.-дерева.
Как и в случае процедуры Тккк-1мзккт из раздела 12.3, считаем, что атрибут з. Йеу заполнен и что з. 1еЬ = мп. и з. пдЬг = мп,. Кроме того, полагаем, что з. Ь = О. Таким образом, для вставки узла з в АЧ1=дерево Т мы должны осуществить вызов АЧ1.-1нзккт(Т. гоо1, х). * Покажите, что время работы операции АЧ1.-1мзккт для АЧ1.-дерева с п узлами равно 0(1я и) и она выполняет 0(1) поворотов. 367 Глава И. Красно-черные деревьв 13.4. Дераммдыа Если мы вставляем в бинарное дерево поиска набор из и элементов, то полученное в результате дерево может оказаться ужасно несбалансированным, что приводит к большому времени поиска.
Однажз, как мы видели в разделе 12.4, случайные бинарные деревья поиска обычно оказываются достаточно сбалансированнымн. Таким образом, стратегия построения сбалансированного дерева для фиксированного множества элементов состоит в их случайной перестановке с последующей вставкой в дерево. Но что делать, если все элементы недоступны одновременно? Если мы получаем элементы по одному, можем ли мы построить из них случайное бинарное дерево поиска? Рассмотрим структуру данных, которая позволяет положительно ответить на этот вопрос. Дерамида представляет собой бинарное дерево поиска с модифицированным способом упорядочения узлов. Пример дерамиды показан на рис.
13.9. Как обычно, каждый узел х в дереве имеет значение ключа х.кеу. Кроме того, мы назначим каждому узлу атрибут х.ряску, который представляет собой случайное число, выбираемое для каждого узла независимо от других. Мы считаем, что все приоритеты и все ключи в дереве различны. Узлы дерамиды упорядочены таким образом, чтобы ключи подчинялись свойству бинарных деревьев поиска, а приоритеты — свойству неубывиощей пирамиды. Если и является левым дочерним узлом узла и, то и.
Йер ( и. йер. ° Если и является правым дочерним узлом узла и, то и. Йед > и. Йеу. Если и является дочерним узлом узла и, то и. рггогзгр > и. ргзогтгр. рис. 1ЗЗ. дервмида. Каидьгй узел х помечен атрибутами х.лерг х.ргзогцр. Например, корень имеет елизч С и приоритет 4. Именно эта комбинация свойств дерева и пирамиды и дала название мдерамидам (псар). Помочь разобраться в дерамидах может следукицая интерпретация. Предположим, что мы вставляем в дерамиду узлы хм ха,...,х„со связанными с ни- зн оригинале — "амар"; елово, образованное нз двуз — "пее" и "Ьеаф. 'Алавогачно из слов дерево" и "пириопи" получилел русский игеивалент. — Примеч.
гну» Часть Ш. Структуры даннык ми ключами. Тогда полученная в результате дерамида представляет собой дерево, которое получилось бы в результате вставки узлов в обычное бинарное дерево поиска в порядке, определяемом (случайно выбранными) приоритетами, .г.е. х,. рпоп1у ( х,. рпоп1у означает, что узел х, был вставлен до узла х . а. Покажите, что для каждого заданного множества узлов хд, хз,..., х„со связанными с ними ключами и приоритетами (все ключи и приоритеты различны) существует единственная дерамида.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
