Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 118
Текст из файла (страница 118)
Следовательно, общая фактическая работа по извлечению минимального узла равна О (Р (и) + 1(Н)). Потенциал перед извлечением минимального узла равен 1 (Н) + 2т (Н), а после — не превышает (Р (и) + 1) + 2т (Н), поскольку остается не более Р (и) + 1 корней, и не имеется узлов, которые были бы помечены во время выполнения этой операции.
Таким образом, амортизированная стоимость не превосходит величину 0 (Р (и) + 1(Н)) + ((Р (и) + 1) + 2гп (Н)) — (Г (Н) + 2т (Н)) = = О (Р (и)) + 0 (т (Н) ) — т (Н) = О (Р (п) ), поскольку можно масштабировать единицы потенциала таким образом, чтобы можно было пренебречь константой, скрытой в 0 (1(Н)). Интуитивно понятно, что стоимость выполнения каждого связывания является платой за снижение потенциала из-за уменьшения количества корней на 1 при связывании. В разделе 20.4 мы увидим, что Р (и) = 0 (1я и), так что амортизированная стоимость извлечения минимального узла равна 0 (1я и). Глава 20. Фибоначчиевы пирамиды 571 Упражнения 20.2-1. Изобразите фибоначчиеву пирамиду, которая получается в результате применения процедуры Рш НеАЕ ЕхткАст Мпч к фибоначчиевой пирамиде, показанной на рис.
20.3к. 20.2-2. Докажите, что лемма 19.1 выполняется для неупорядоченных биномиальных деревьев, если свойство 4 заменить свойством 4Е 20.2-3. Покажите, что при поддержке только операций над сливаемыми пирамидами максимальная степень 27 (и) в фибоначчиевой пирамиде с и узлами не превышает ~1й п1. 20.2 $. Профессор разработал новую структуру данных, основанную на фибоначчиевых пирамидах. Пирамида имеет ту же структуру, что и фибоначчиева пирамида, и поддерживает операции над сливаемыми пирамидами.
Реализация операций такая же, как и в фибоначчиевых пирамидах, но с тем отличием, что в качестве последнего шага при вставке узла и объединении пирамид выполняется уплотнение списка корней. Чему равно наихудшее время выполнения операций над пирамидами профессора? Насколько нова предложенная им структура данных? 20.2-5. Считая, что единственная доступная нам операция над ключами состоит в их сравнении (как в случае всех реализаций в данной главе), докажите, что невозможно обеспечить выполнение всех операций над сливаемыми пирамидами за амортизированное время О (1). 20.3 Уменьшение ключа и удаление узла В этом разделе будет показано, как уменьшить ключ узла фибоначчиевой пирамиды за амортизированное время 0(1) и как удалить произвольный узел из фибоначчиевой пирамиды с и узлами за амортизированное время О (17 (и)).
Эти операции нарушают свойство фибоначчиевых пирамид, которое заключается в том, что все деревья в фибоначчиевых пирамидах являются неупорядоченными биномиальными деревьями. Однако они остаются достаточно близки к таковым„ так что мы можем ограничить максимальную степень 13 (и) величиной О (!б и). Этот факт, который будет доказан в разделе 20.4, приводит к тому, что операции йв НеАР Ехтклст Мпч и Р!в НеАР Пееете имеют амортизированное время работы, равное О (1й и). Уменьшение ключа В приведенном далее псевдокоде для операции Ргв НеАР Пескелзе Кеу, как и ранее, предполагается, что при удалении узла из связанного списка никакие его поля не изменяются.
572 Часть Ч. Сложные структуры данных г!В НеАР 13ескеАБе Кеу(Н, х, Й) 1 !АЙ > Йеу[х] 2 Феп еггог "Новый ключ больше текущего" 3 Йеу[х] — Й 4 у -р[х) 5 И' у ~ мй. и Йеу[х] ( Йеу[у] б И!ел С!!Т(Н, х, у) 7 САБсА!з!ыб-Сг!т(Н, у) 8 11' Йеу[х) ( Йеу[тзп[Н]) 9 Игеп тяп [Н] — х С!П(Н, х, у) 1 Удаление х из списка дочерних узлов у, уменьшение аедгее[у] 2 Добавление х в список корней Н р[х] нп.
4 тагк[х] - ГАЬ8Е САзсАВ!ыб Сг!т(Н, у) р[у) 2 11зф!ч!ь 3 И!ел 11 тоги[у] = РАезе 4 И!ел таге [у) + — ТК!3Е 5 е1яе С!!Т(Н,у,х) 6 САБСА0!ХО С!!Т(Н, з) Процедурар!В НВАР 13есиеАзе Кеуработаетследующимобразом. Встроках 1-3 проверяется, не является ли новый ключ больше старого, и если нет, то полю йеу [х) присваивается значение нового ключа. Если х — корень или если Йеу[х] > йеу [у], где у — родитель х, то никакие структурные изменения не нужны, поскольку свойство неубывающих пирамид не нарушено. Это условие проверяется в строках 4-5.
Если же свойство неубывающих пирамид оказывается нарушенным, требуется внести множество изменений. Мы начинаем с вырезания (сипшя) х в строке б. Процедура С!!т "вырезает" связь между х и его родительским узлом у, делая х корнем. Поле тагк используется для получения желаемого времени работы. В нем хранится маленькая часть истории каждого узла. Предположим, что с узлом х произошли следующие события. 1. В некоторый момент времени х был корнем, 2. затем х был привязан к другому узлу, 3.
после чего два дочерних узла х были вырезаны. Глава 20. Фибоначчиеаы пирамиды 573 Как только х теряет второй дочерний узел,мы вырезаем х у его родителя, делая х новым корнем. Поле тагк [х] равно тите, если произошли события 1 и 2 и у х вырезан только один дочерний узел. Процедура Сст, следовательно, в строке 4 должна очистить поле тагес [х], поскольку произошло событие 1. (Теперь становится понятно, почему в строке 3 процедуры Р1в НелР Печк выполняется сброс поля тагй [у]: узел у оказывается связан с другим узлом, т.е.
выполняется событие 2. Затем, когда будет вырезаться дочерний узел у узла у, полю тагк [у] будет присвоено значение тисе.) Мы сделали еще не всю работу, поскольку х может быть вторым дочерним узлом, вырезанным у его родительского узла у с того момента, когда у был привязан к другому узлу. Поэтому в строке 7 процедуры Р~в Нелл 1)ескелзе Кеу делается попытка выполнить операцию каскадного вырезания (сазсарйпй-сш) нал у.
Если у — корень, то проверка в строке 2 процедуры Слзслвпчс С11т заставляет ее прекратить работу. Если у не помечен, процедура помечает его в строке 4, поскольку его первый дочерний узел был только что вырезан, после чего также прекращает работу. Однако если узел уже был помечен, значит, только что он потерял второй дочерний узел. Тогда у вырезается в строке 5, и процедура Слзслвпчб Сст в строке 6 рекурсивно вызывает себя для узла г, родительского по отношению к узлу у. Процедура Слзсл1злчс Сст рекурсивно поднимается вверх по дереву до тех пор, пока не достигает корня или непомеченного узла.
После того как выполнены все каскадные вырезания, в строках 8 — 9 процедуры Р1в НелР 13ескелзе Кеу при необходимости обновляется величина лип [Н]. Единственным узлом, чей ключ изменяется в процессе работы процедуры, является узел х, так что минимальным узлом может быть толью исходный минимальный узел или узел х. На рис. 20.4 показано выполнение двух процедур йв НелР 13ескелзе Кет над фибоначчиевой пирамидой, показанной на рис.
20.4а. Первый вызов, показанный на рис. 20.46 и уменьшающий ключ 46 до 15, выполняется без каскадного вырезания. При втором вызове (рис. 20.4в-д), уменьшающем ключ 35 до 5, выполняются два каскадных вырезания. Покажем теперь, что амортизированная стоимость процедуры Р[в Нелр 1)ескелзе Кеу составляет только О (1). Начнем с определения фактической стоимости. Процедура Р[в Нелв 13ескелзе Кеу занимает 0 (1) времени, плюс время, необходимое для каскадного вырезания.
Предположим, что процедура Слзслввча Сит в данном вызове Р~в Нелр 13ескелзе Кеу рекурсивно вызывается с раз. Каждый вызов Слзсл1эвчс Сст без учета рекурсии требует О (1) времени. Следовательно, фактическая стоимость процедуры Р~в Нелр 13ескелзе Кв' составляет 0 (с) с учетом всех рекурсивных вызовов. Вычислим теперь изменение потенциала. Обозначим через Н фибоначчиеву пирамиду непосредственно перед вызовом процедуры Р1в Нелг 13ескелзе Кеу. Каждый рекурсивный вызов Слзслцвчс Сит, за исключением последнего, Часть Ч. Сложные структуры данных 574 ппп) Л) пип) Л) ф4, )))77) (273) )2)- ф (4)п) ф (455 (35) (353 п„п) ))) ппп) Л ~) 1Е5745 ~3252..
--) 7)-.—.- .ф--. (35) ©' ,)7., ~23, п2)» © (4)7 7 '~' ) и 5 © "' 6~) п52) и! ф) )з5'7' - — 47) . †. -. —. ф- - п357 ф® 7253') Щ ф пцп ©'~;) Й Рнс. 20.4. Два вызова процедуры Р)в НеАе ЭескеАзе Кет вырезает помеченный узел и сбрасывает бит метки. После этого имеется 5 (Н) + с деревьев (исходные 5 (Н) деревьев, с — 1 деревьев, полученных при каскадном вырезании, н дерево, корнем юторого является х) и не более т(Н) — с+ 2 помеченных узла (у с — 1 узлов пометка была снята при каскадном вырезании, и последний вызов процедуры Слзсл)3)74а С))т может привести к пометке узла). Таким образом, изменение потенциала не превышает величины (($ (Н) + с) + 2 (774 (Н) — с+ 2)) — (5 (Н) + 2т (Н)) = 4 — с.
Следовательно, амортизированная стоимость Р)в НеАе РескеАзе Кеу не превышает О (с) + 4 — с = О (1), поскольку мы можем соответствующим образом масштабировать единицы. Теперь вы видите, почему потенциальная функция определена таким образом, что включает член, равный удвоенному количеству помеченных узлов. Когда помеченный узел у вырезается в процессе каскадного вырезания, его пометка снимается, что приводит к снижению потенциала на 2. Одна единица потенциала служит платой за вырезание и снятие пометки, а вторая компенсирует увеличение потенциала из-за того, что у становится корнем. тК)Г) и) ))5) ® (26) пп24) $773. - ..
ф )357) 7)75 )23) (2)) ф ® (35) (5'.) 5) )И5)-- — )7~) -- — ф 4~) з 3 ф® (2)7 ф (4)1 (355 Глава 20. Фибоначчиевы пирамиды 575 Удаление узла Удаление узла из фибоначчиевой пирамиды с и узлами за амортизированное время О (Р (и)) легко выполняется при помощи приведенного ниже псевдокода. Предполагается, что в фибоначчиевой пирамиде нет ни одного ключа со значением — оо. Р1В НЕАР РЕЬЕТЕ(Н, х) 1 Р!В НЕАР РЕСКЕАЗЕ Кву(Н,х, — оо) 2 Р!В НеАР ЕхткАст М!ы(Н) ПроцедураРЕВ НеАР Реьетеаналогична процедуре Впчом!Аь НВАР Реьете. Она делает х минимальным узлом фибоначчиевой пирамиды, присваивая его ключу значение — со, после чего узел х удаляется из фибоначчиевой пирамиды при помощи процедуры Р!в НВАР ЕхткАст М!ы. Амортизированное время работы Р!в НеАР Реьете представляет собой сумму амортизированного времени работы О (1) процедуры Р!в НеАР РескеАзе Кеу и амортнзированного времени работы 0(Р(и)) процедуры Р!в НеАР ЕхткАст М!ьь Поскольку в разделе 20.4 мы увидим, что .Р (и) = 0(1яи), амортизированное время работы процедуры Р!в НВАР Реьете равно 0(1яи).
Упражнения 20.3-1. Предположим, что корень х в фибоначчиевой пирамиде помечен. Поясните, как узел х мог стать помеченным корнем. Покажите, что тот факт, что х помечен, не имеет никакого значения для анализа, даже если это не корень, который сначала был привязан к другому узлу, а потом потерял один дочерний узел. 20.3-2. Докажите оценку О (1) амортизнрованного времени работы процедуры Р!в НВАР РескеАзе Ки' как средней стоимости операции с использованием группового анализа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
