Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 72
Текст из файла (страница 72)
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 [з] = = г(дМ [з] = хн.. Кроме того, полагаем, что 6 [з] = О. Таким образом, для вставки узла з в АЧ1.-дерево Т мы должны осуществить вызов АЧ1. 1нзнкт(гоо1 [Т], г).
г) Покажите, что время работы операции АЧЬ 1нзнкт для АЧ1.-дерева с и узлами равно О (1бп), и она выполняет О(1) поворотов. 360 Часть 111. Структуры данных 13-4. Дерамидыз Если мы вставляем в бинарное дерево поиска набор из и элементов, то получающееся в результате дерево может оказаться ужасно несбалансированным, что приводит к большому времени поиска. Однако, как мы видели в разделе 12.4, случайные бинарные деревья поиска обычно оказываются достаточно сбалансированными. Таким образом, стратегия построения сбалансированного дерева для фиксированного множества элементов состоит в случайной их перестановке с последующей вставкой в дерево.
Но что делать, если все элементы недоступны одновременно? Если мы получаем элементы по одному, можем ли мы построить из них случайное бинарное дерево поиска? Рассмотрим структуру данных, которая позволяет положительно ответить на этот вопрос. Дерамида представляет собой бинарное дерево поиска с модифицированным способом упорядочения узлов. Пример дерамиды показан на рис. 13.9. Как обычно, каждый узел х в дереве имеет значение йеу [х]. Кроме того, мы назначим каждому узлу значение приоритета рпоп1р [х], которое представляет собой случайное число, выбираемое для каждого узла независимо от других.
Мы считаем, что все приоритеты и все ключи в дереве различны. Узлы дерамиды упорядочены таким образом, чтобы ключи подчинялись свойству бинарных деревьев поиска, а приоритеты — свойству неубывающей пирамиды. ° Если н является левым потомком и, то Йеу [о] < Йеу [и]. ° Если зг является правым потомком и, то йер [зз] > йеу [зз]. ° Если о является потомком и, то ргзоп1у [и] > ргзогйд [и]. Именно эта комбинация свойств дерева и пирамиды и дала название "дерамида" (пеар).
Помочь разобраться с дерамидами может следующая интерпретация. Предположим, что мы вставляем в дерамиду узлы хы хз,..., х„со связанными с ними ключами. Тогда получающаяся в результате дерамида представляет собой дерево, которое получилось бы в результате вставки узлов в обычное бинарное дерево поиска в порядке, определяемом (случайно выбранными) приоритетами, те. рг1огз1у [х;] < рпоп~у [х ] означает, что узел х; был вставлен до узла х .. а) Покажите, что для каждого заданного множества узлов хы хз,..., х„ со связанными с ними ключами и приоритетами (все ключи и приоритеты различны) существует единственная дерамида.
В оригинале — ггеарз; слово, образованное из двух — ггее и Ьеар. Аналогично, из "дерева" и "пирамиды" получился русский зквивалент. — Прим. ред. Глава 13. Красно-черные деревья 361 Рис. 13.9. Дерамила. Каждый узел имеет метку Йеу [х]: ргзогду [х] б) Покажите, что математическое ожидание высоты дерамиды равно 9 (1К и) и, следовательно, время поиска заданного значения в дерамиде составляет О (1я и). Рассмотрим процесс вставки нового узла в существующую дерамиду. Первое, что мы делаем — это назначаем новому узлу случайное значение приоритета. Затем мы вызываем процедуру ТкнАР 1нзнкт, работа которой показана на рис. 13.10.
На рис. 13.10а показана исходная дерамида; на рис. 13.10б — та же дерамида после вставки узла с ключом С и приоритетом 25. Рис. 13.10в-г изображают промежуточные стадии вставки узла с ключом Р и приоритетом 9, а рис. 13.10д — получившуюся в результате дерамиду. На рис. 13.10е показана дерамида после вставки узла с ключом Е и приоритетом 2. в) Объясните, как работает процедура ТкнАР 1нзнкт. Поясните принцип ее работы обычным русским языком и приведите ее псевдокод. (Указание: выполните обычную вставку в бинарное дерево поиска, а затем выполните повороты для восстановления свойства неубывающей пирамиды.) г) Покажите, что математическое ожидание времени работы процедуры Ткнлг 1нзнкт составляет О (1к и). Процедура ТкнАР 1хзнкт выполняет поиск с последующей последовательностью поворотов.
Хотя эти две операции имеют одно и то же математическое ожидание времени работы, на практике стоимость этих операций различна. Поиск считывает информацию из дерамиды, никак не изменяя ее. Повороты, напротив, приводят к изменению указателей на дочерние и родительские узлы в дерамиде. На большинстве компьютеров операция чтения существенно более быстрая, чем операция записи. Соответственно, желательно, чтобы поворотов при выполнении процедуры ТкнАг 1нзнкт было как можно меньше. Мы покажем, что ожидаемое количество выполняемых процедурой поворотов ограничено константой.
Часть 111. Структуры данных 362 ««Л 9« Рис. 13.10. Работа алгоритма Таеле !Мзеат Для этого нам надо дать несколько определений, проиллюстрированных на рис. 13.1!. Левый хребет бинарного дерева поиска Т представляет собой путь от корня к узлу с минимальным значением ключа.
Другими словами, левый хребет представляет собой путь, состоящий только из левых ребер. Соответственно, правый хребет представляет собой путь, состоящий только из правых ребер. Длина хребта — это количество составляющих его узлов. д) Рассмотрите дерамиду Т после того, как в нее при помощи процедуры ТкеАЕ !неект вставляется узел х. Пусть С вЂ” длина правого ''61. .5 ' .' 23:7 2 6К65 5 ) — «, А~!О) (Е ф 6А;65) «! 733 Я! Ф:4) 6БЗ .'65 1'2 ~Л'.5 фЯ~ (65 65 «6::26 3 (1732 Г,,6' ! и: ~05 «л:9. ЕК 651 5 7 «, «б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
