Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 122
Текст из файла (страница 122)
и в строке 11 и возвратом указателя на удаленный узел х в строке 12. Теперь мы готовы показать, что амортизированная стоимость извлечения минимального узла из фибоначчиевой пирамиды с и узлами равна 0(х7(п)). Обозначим через Н фибоначчиеву пирамиду непосредственно перед выполнением операции Г!в-НеАР-ЕхткАст-Мцч. Начнем с подсчета фактической стоимости извлечения минимального узла.
Вклад 0(О(п)) вносит обработка не более 0(п) дочерних узлов минимального узла в процедуре Р!в-НеАР-ЕхткАст-М!х, а также операции в строках 2 и 3 и 16 — 23 процедуры Со!чвое!оАте. Остается проанализировать вклад цикла Гог в строках 4-14 той же процедуры, для чего применим амортизационный анализ. Размер списка корней при вызове процедуры СонзошоАте не превышает Р(п) + 1(Н) — 1, поскольку он состоит из исходного списка корней с 1(Н) узлами, минус извлеченный узел и плюс дочерние узлы извлеченного узла, мэличество которых не превышает Р(п). В заданной итерации цикла 1ог в строках 4-14 количество итераций цикла и ЬИе в строках 7 — 13 зависит от списка корней. Но мы знаем, что при каждом проходе цикла иЫ1е один из корней связывается с другим, так что общее количество итераций цикла иЬИе во всех итерациях цикла Гог не превышает количества элементов списка корней.
Следовательно, об- 555 Глава 1К Фидапаичиевы пирамиды шее количество работы, выполняемой в цикле Гог, не более чем пропорционально Ю(п)+г(Н). Таким образом, фактическая работа по извлечению минимального узла равна О(0(п) + г(Н)). Потенциал перед извлечением минимального узла равен г(Н) + 2тп(Н), а после — не превышает (0(п) + 1) + 2т(Н), поскольку остается не более Гз(п) + 1 корней, и нет узлов, которые были бы помечены во время выполнения этой операции.
Таким образом, амортизированная стоимость не превосходит величину 0(11(п) + 1(Н)) + ((15(п) + 1) + 2 т(Н)) — (г(Н) + 2 т(Н)) = 0(0( )) + 0(с(Н)) - г(Н) = 0(Х) (п) ), поскольку можно масштабировать единицы потенциала таким образом, чтобы можно было пренебречь константой, скрытой в О(8(Н)). Интуитивно понятно, что стоимость выполнения каждого связывания является платой за снижение потенциала из-за уменьшения количества корней на 1 при связывании. В разделе 19.4 мы увидим, что 11(п) = 0(1к и), так что амортизированная стоимость извлечения минимального узла равна 0(1я п).
Упражнения 19.2.1 Изобразите фибоначчиеву пирамиду, которая получается в результате применения процедуры Р1в-НеАР-ЕхткАст-М1м к фибоначчиевой пирамиде, показанной на рис. 19.4, (н). 19.3. Уменьшение ключа и удаление узла В этом разделе будет показано, как уменьшить ключ узла фибоначчиевой пирамиды за амортизированное время 0(1) и как удалить произвольный узел из фибоначчиевой пирамиды с п узлами за амортизированное время О(.0(п)). В разделе 19.4 будет показано, что максимальная степень 11(п) равна О(1я п), откуда вытекаег, что амортизированное время работы процедур Р1в-НеАР-ЕхткАст-Мпч и Вв-НЕАР-ПЕНЯЕТЕ составляет 0(1я п).
Уменьшение ключа В приведенном далее псевдокоде операции Р!в-НеАР-ВескеАБе-Кеу, как и ранее, предполагается, что при удалении узла из связанного списка никакие его структурные атрибуты не изменяются. 55б Часть К Снежные структуры данные Р1В-НВАР-ОебкеАБЕ-КЕЧ(Н,х, И) 1 11 И > х.Иеу 2 еггог "Новый ключ больше текузцего" 3 х.Иеу = И 4 у=х.р 5 Ыу ф 1ч1е и х.Иеу ( у.Иеу 6 С15т(Н, х, у) 7 САБслппчб-Сбт(Н, у) 8 11' х. Иеу ( Н. ттип. Иеу 9 Н.ттп = х Сит(Н, х, у) 1 Удалить х из дочернего списка у, уменьшая у. Иедгее 2 Добавить х в список корней Н 3 х.р = 1С1с 4 х.тпагИ = РАьЕЕ САЕЕАВ1хб-Сбт(Н, у) 1 =у.р 2 ИгфХ1Е 3 !т у.тагИ == БАЕВЕ 4 у,татИ = ти15Е 5 еЬе Сит(Н, у, г) б САЯсАВ1хб-Сбт(Н, х) Процедура Р1в-НВАР-Оесиелее-Кеу работает следующим образом.
В строках 1-3 проверяется, не окажется ли новый ключ больше старого, и если нет, то х патучает новое значение ключа. Если х — корень или если х. Иеу > у. Иеу, где у — родитель х, то никакие структурные изменения не нужны, поскольку свойство неубывающих пирамид не нарушено. Это условие проверяется в строках 4 и 5. Если же свойство неубываклцих пирамид оказывается нарушенным, может потребоваться внести множество изменений. Мы начинаем с вырезания (сцц(пй) х в строке б.
Процедура С15т "вырезает" связь между х и его родительским узлом у, делая х корнем. Атрибуты татИ используются для получения желаемого времени работы. В них хранится маленькая часть истории каждого узла. Предположим, что с узлом х произошли следующие события. 1.
В некоторый момент х был корнем. 2. х был связан с другим узлом (стал его дочерним узлом). 3. Два дочерних узла х были вырезаны. Как только х теряет второй дочерний узел, мы вырезаем х у его родителя, делая х новым корнем. Атрибут х. татИ равен твбЕ, если произошли события 1 Глава 19. Фибаиаччиевы иираииды 557 и 2 и у х вырезан только один дочерний узел. Процедура Спт, таким образом, в строке 4 очищает атрибут х. тпагМ, поскольку произошло событие 1.
(Теперь становится понятно, почему в строке 3 процедуры Е~в-НеАР-аничк выполняется сброс у. 7лаг)е: узел у оказывается связанным с другим узлом, т.е. выполняется событие 2. Затем, когда будет вырезаться дочерний узел у узла у, у. гпаг(е получит значение тисе.) Выполнена еще не вся работа, поскольку х может быть вторым дочерним узлом, вырезанным у его родительского узла у с того момента, когда у был привязан к другому узлу. Поэтому в строке 7 процедуры Е1в-НЕАР-ВЕСкЕАЕЕ-КЕу предпринимается попытка выполнить операцию каскадного вырезания (сазсаош8-сШ) над у. Если у — корень, то проверка в строке 2 процедуры САзсА171ыс-С1гг заставляет последнюю прекратить работу.
Если у не помечен, процедура помечает его в строке 4, поскольку его первый дочерний узел был только что вырезан, после чего также прекращает работу. Однако если узел уже был помечен, значит, только что он потерял второй дочерний узел. Тогда у вырезается в строке 5, и процедура САзсАп1мс-С17т в строке б рекурсивно вызывает себя для узла г, родительского по отношению к узлу у. Процедура САесАппчс-Сцт рекурсивно поднимается вверх по дереву до тех пор, пока не достигает корня или непомеченного узла. После того как выполнены все каскадные вырезания, в строках 8 и 9 процедуры р1в-НеАР-ВескеАзе-Кеу при необходимости обновляется величина Н.
7пт. Единственным узлом, ключ которого изменяется в процессе работы процедуры, является узел х, так что минимальным узлом может быть только исходный минимальный узел или узел к. На рис. 19.5 показано выполнение двух вызовов Е1е-НеАР-ОескеАзе-Кет над фибоначчиевой пирамидой, приведенной на рис. 19.5, (а). Первый вызов, показанный на рис. 19.5,(б), выполняется без каскадного вырезания. При втором вызове (рис. 19.5,(в)-(д)) выполняются два каскадных вырезания. Покажем теперь, что амортизированная стоимость процедуры Р1в-НеАРПескеАзе-Кет составляет лишь О(1).
Начнем с определения фактической стоимости. Процедура Еа-НЕАР-(лЕСкЕАЯЕ-КЕУ выполняется за время 0(1), плюс время, необходимое для каскадного вырезания. Предположим, что процедура САзсАшип-Сст в данном вызове йв-НеАР-ОескеАзе-Кеу рекурсивно вызывается с раз (вызов выполняется в строке 7 процедуры Е[в-НеАР-ОескеАзеКЕу, за которым следует с — 1 рекурсивный вызов САЕСАппчс-С17т).
Каждый вызов САзсАппчп-Сцт без учета рекурсии требует времени 0(1). Следовательно, фактическая стоимость процедуры Р1в-НеАР-ОескеАзе-Кет с учетом всех рекурсивных вызовов составляет 0(с). Вычислим теперь изменение потенциала. Обозначим через Н фибоначчиеву пирамиду непосредственно перед вызовом процедуры Р1В-НеАР-гзескеАБеКеу. Вызов Спт в строке 6 процедуры Р~е-НеАР-ОескеАее-Кет создает новое дерево с корнем в узле х и сбрасывает бит метки (который уже может иметь значение РАезе).
Каждый вызов САзсАппчс-С17т, за исключением последнего, вырезает помеченный узел и сбрасывает бит метки. После этого в фибоначчиевой пирамиде имеется 1(Н) + с деревьев (исходные 1(Н) деревьев, с — 1 деревьев, по- 556 Часть Г Слалгнме структуры Ьалнъгл Н. гл(п г (65) (Ззт Н, тпг й. глгп (л) (аб)-ф; '%3 ф". '~!~ —. ф " рц) 'Йр ~Зс) ~~~ © ~~4) лученных при каскадном вырезании, и дерево, корнем которого является х) и не более гп(Н) — с+ 2 помеченных узла (у с-1 узлов пометка была снята при каскадном вырезании, а последний вызов процедуры САЕсА()17(0-С()т может привести к пометке узла).
Таким образом, изменение потенциала не превышает величины ((((Н) + с) + 2(гп(Н) — с+ 2)) — (1(Н) + 2т(Н)) = 4 — с . Таким образом, амортизированная стоимость Р(В-НВАр-Рескедйе-КВУ не превышает О(с) + 4 — с = О(1), поскольку мы можем соответствующим образом масштабировать единицы потенциала для доминирования над константой, скрытой в О(с). Теперь вы видите, почему функция потенциала определена таким образом, что включает член, равный удвоенному количеству помеченных узлов. Когда помеченный узел у вырезается в процессе каскадного вырезания, его пометка сни- Рис.
19.5. Два вызова ргв-Нелл-Весдяаае-Кет. (а) Ислсднаа фибоналчиева пирамида (б) Ключ узла уменьшаетса с 46 до 15. Узел становится корнем, а его родительский узел (с ключом 24), который ранее был непомеченным, птчечастгл. (вНд) Ключ узла уменьшаетса с 35 до 5. В части (в) узел, теперь имеющий кточ 5, становится юрием. Его родгпельскнй узел, с ключом 26, помечен, так что осуществляетса касющиое вырезание. Узел с ключом 26 вырезается у родителя и делается непомеченным корнем в части (г). Выполняегся н другое каскадное вырезание, посюльку узел с ключом 24 глюке помечен. Этот узел вырезаетсл у родимая и деластса непомеченным юрием в части (д).
В зтог момент каскадные вырезания прекращаются, поскольку узел с ключом 7 является корнем. (Дане если бы этот узел не был корнем, каскадные вырезания остановились бы, так как он непомеченный.) В части (д) показан результат выполнения операции ргв-НЕАЕ-))еслеллЕ-КЕт, с Н. тгп, указывающим на новый минимальный узел. 559 Глава!9. Фибаиаччиевы аирамиды мается, что приводит к снижению потенциала на 2. Одна единица потенциала служит платой за вырезание и снятие пометки, а вторая компенсирует увеличение потенциала нз-за того, что у становится корнем. Удаление узла Приведенный далее псевдокод выполняет удаление узла из фибоначчиевой пирамиды с п узлами за амортнзированное время 0(Р(п)). Предполагается, что в настоящий момент в фибоначчиевой пирамиде нет ключа со значением — оо. Р!В-НЕАР-РЕ1,ЕТЕ(Н, х) 1 Р!В-НеАР-РескеАБВ-Кеу(Н, х, — оо) 2 Р1В-НеАР-ЕхткАст-Мцч (Н) Процедура Р1в-НВАР-Рееете делает х минимальным узлом фибоначчиевой пирамиды, присваивая ему уникальное минимальное значение ключа — оо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
