Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 124
Текст из файла (страница 124)
Сделайте вывод, что Н состоит не более чем из (1й и)' + 1 биномиальных деревьев. Предположим, что мы представляем биномиальную пирамиду следующим образом. Каждое биномиальное дерево в биномиальной пирамиде представлено с использованием схемы с левым потомком и праввам братом из раздела 10.4. Каждый узел содержит свой ключ, указатель на родительский узел, на крайний слева дочерний узел и на брата, следующего непосредственно справа за ним (эти указатели могут иметь значения мп. в соответствующих ситуациях), а также степень (количество дочерних узлов, как и в фибоначчиевых пирамидах). Корни образуют односвязный список, упорядоченный по степеням корней (в порядке возрастания). Обращение к биномиальной пирамиде выполняется с помощью указателя на первый узел в списке корней.
в. Завершите описание представления биномиальной пирамиды (именуйте атрибуты, опишите, когда они имеют значения ып., и определите организацию списка корней), а также покажите, как реализовать над биномиальными пирамидами семь операций, которые в разделе были реализованы над фибоначчиевыми пирамидами. Каждая операция должна выполняться в наихудшем случае за время 0(!кп), где и — количество узлов в биномиальной пирамиде (или, в случае операции 1)ьцОм, в двух объединяемых биномиальных пирамидах).
Операция МАКЕ-НЕАР должна выполняться за константное время. к Предположим, что нужно реализовать для фибоначчиевой пирамиды только операции над объединяемыми пирамидами (т.е. не нужно реализовывать операции ОескеАзе-Кеу и Пеняете). В чем деревья в фибоначчиевой пирамиде схожи с деревьями в биномиальной пирамиде? Чем они различаются? Покажите, что максимальная степень в фибоначчиевой пирамиде с и узлами не превышает ~1й п~. д.
Профессор разработал новую структуру данных, основанную на фибоначчиевых пирамидах. Его пирамида имеет ту же структуру, что и фибоначчиева пирамида, и поддерживает только операции над объединяемыми пирамидами. Реализации этих операций те же, что и в фибоначчиевых пирамидах, однако вставка и объединение уплотняют список корней в качестве своего последнего 5б6 Часть и Снежные структуры данных шага. Каковы времена работы операций над пирамидой профессора в наихудшем случае? 19.3. Дополнительные операции над ерибоначчиеоыми пирамидами Мы хотим реализовать поддержку двух новых операций над фибоначчиевыми пирамидами, при этом не изменяя амортизированное время работы прочих операций над фибоначчиевыми пирамидами.
а. Операция Я~в-Нвлу-Снлмвв-Кву(Н,х,й) изменяет ключ узла х, присваивая ему новое значение?с. Приведите эффективную реализацию процедуры Р5в-НвАу-Снлмав-Кву и проанализируйте амортизированное время работы вашей реализации для случаев, югда й больше, меньше или равно х. кеу. б. Разработайте эффективную реализацию процедуры Р|в-НвАг-Ркглчв(Н, г), которая удаляет д = ппп(г, Н.
и) узлов из Н. Для удаления могут быть выбраны любые д узлов. Проанализируйте амортизированное время работы вашей реализации. (Указанное вам может потребоваться изменение структуры данных и функции потенциала.) 1К4. 2-3-4-пирамиды В главе 18 рассматривались 2-3-4-деревья, в юторых каждый внутренний узел (кроме, возможно, корня) имеет два, три или четыре дочерних узла, и все листья таких деревьев располагаются на одной и той же глубине.
В данной задаче мы реализуем 2-3-4-пирамиды, поддерживающие операции над обьединяемыми пирамидами. 2-3-4-пирамиды отличаются от 2-3-4-деревьев следующим. В 2-3-4-пирамидах ключи хранятся только в листьях, и в каждом листе х хранится ровно один ключ в атрибуте х. кеу. Никаюй порядок ключей в листьях не соблюдается, т.е. при перечислении слева направо ключи могут располагаться в произвольном порядке.
Каждый внутренний узел х содержит значение х, ото(1, которое равно минимальному значению среди ключей листьев поддерева„корнем которого является х. Корень г содержит атрибут г. Ьегд1х1, в котором хранится высота дерева. И наконец 2-3-4-пирамиды предназначены для хранения в оперативной памяти, так что при работе с ними не требуются никакие операции чтения или записи на диск. Реализуйте перечисленные далее операции над 2-3-4-пирамидами.
Каждая из операций (а) — (д) должна выполняться за время О(1кп) при работе с 2-3-4-пирамидой, в которой содержится и элементов. Операция Шчюм в п. (е) должна выполняться за время О(1кп), где и — количество элементов в двух входных пирамидах. а. Операция Мппмцм возвращает указатель на лист с наименьшим значением ключа. б. Операция 13всквлзв-Кву уменьшает значение ключа в данном листе х до указанного значения Й ( х. Йеу.
о. Операция 1мзвкт вставляет в пирамиду лист х с ключом lс. 5б7 Глава ! Я Фибоначчиееы яирамиды а Операция О~.нтн удаляет из пирамиды лист к. д. Операция Ехтклст-Мпч извлекает из пирамиды лист с наименьшим значением ключа. в Операция Умом объединяет две 2-3-4-пирамиды, возвращая полученную в результате слияния 2-3-4-пирамиду и уничтожая при этом входные пирамиды. Заключительные замечании Фибоначчиевы пирамиды были введены Фредманом (Ргебшап) и Таржаном (Таг)ап) [113].
В их статье описано также приложение фибоначчиевых пирамид к задачам о кратчайших путях из одной вершины, о кратчайших путях между всеми вершинами, о взвешенных паросочетаниях и о минимальном остовном дереве. Впоследствии Дрисколл (спасо!1), Габон (ОаЬозч), Шрейрман (БйЬга~ппап) и Таржан [95] разработали так называемые "ослабленные пирамиды" (ге1ахеб Ьеара) в качестве альтернативы фибоначчиевым пирамидам. Они разработали два варианта ослабленных пирамид. Один дает то же амортизированное время работы, что и фибоначчиевы пирамиды, второй же позволяет выполнять операцию Рнснвлзн-Кнт в наихудшем случае за (не амортизированное) время 0(1), а процедуры Ехтклст-Мпч и Рн|нтн в наихудшем случае за время 0(!я и).
Ослабленные пирамиды имеют также преимущество перед фибоначчиевыми пирамидами в параллельных алгоритмах. Обратитесь также к заключительным замечаниям к главе б, где рассмотрены другие структуры данных, которые поддерживают быстрое выполнение операции Рнскнлзн-Кнт, когда последовательность значений, возвращаемых вызовами процедуры Ехтнлст-Мпч, монотонно растет со временем, а данные представляют собой целые числа в определенном диапазоне.
Глава 20. Деревья ван Эмде Боаса В предылущих главах вы познакомились со структурами данных, поддерживающими операции над очередями с приоритетами — бинарными пирамидами в главе б, красно-черными деревьями в главе 13' и фибоначчиевыми пирамидами в главе 19. В каждой из этих структур данных как минимум одна важная операция выполняется за время 0(18 п) — либо в худшем случае, либо в случае амортизированного времени. Фактически, поскольку каждая из указанных структур данных основывается на сравнении ключей, нижняя граница времени сортировки П(п 18 и) из раздела 8.1 говорит о том, что по меньшей мере одна из операций должна выполняться за время П(18 и). Почему? Если бы мы были способны выполнить и операцию 1ызпкт, и операцию Ехткдст-М1р1 за время о(18 п), то мы могли бы отсортировать и ключей за время о(п 18 п), сначала выполнив и операций 1ызккт, а затем и операций Ехткуьст-М1м.
В главе 8 мы, однако, видели, что иногда можно воспользоваться дополнительной информацией о ключах, чтобы отсортировать их за время о(п18п). В частности, сортировка подсчетом позволяет отсортировать и ключей, каждый из которых является целым числом в диапазоне от О до 1е, за время В(п + к), которое представляет собой Е1(п) при lс = 0(п). Поскольку нижняя граница сортировки П(п 18п) может быть превзойдена, когда ключи представляют собой целые числа из ограниченного диапазона, закономерно возникает вопрос — нельзя ли при том же условии выполнять каждую из операций очереди с приоритетами за время о(18п)? Из данной главы вы узнаете, что это возможно: деревья ван Эмде Боаса поддерживают операции очередей с приоритетами и несколько других операций, со временем работы каждой из них, в наихудшем случае равным 0(18 18 п).
Условием для этого является то, что ключи должны быть целыми числами в диапазоне от О до и — 1 и не должно быть двух одинаковых ключей. В частности, деревья ван Эмде Боаса поддерживают все операции над динамическими множествами, перечисленные на с. 2б1, — Бпдксн, 1р1зпкт, Опьптв, М1р11м11м, Мдх1мим, Яисспззок и Ркп1уеспззок. Время работы каждой из них составляет 0(18 18п). В данной главе мы опустим рассмотрение сопугству- 'В главе 13 пе обсуидалса вопрос реализации операций Ехткаст-Мгц и Рескелае-кеу, по их легко построить длл любой структуры дапиых, изгораа подаержиаает операции М1п!мцм, Рекете и 1пзект. Глава лд Деревья вав Эмде Баева 569 ющих данных и сосредоточимся только на хранении ключей. Поскольку нас интересуют только ключи, и запрещено наличие одинаковых ключей, вместо операции ЯеАксн мы реализуем более простую операцию Меывек(Я, х), которая возвращает булево значение, указывающее, имеется ли в настоящий момент в динамическом множестве Я значение х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
