Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 106
Текст из файла (страница 106)
Установите для каждого случая, встречающегося в процедурах КВ 1нзект Рвал' и КВ Рн.ете Р!х~л', какой из них является завершающим, а какой — нет. (Указание: обратитесь к рис. 13.5-! 3.7.) Сначала мы проанализируем структурные модификации для случая, когда выполняются только вставки. Пусть Т вЂ” красно-черное дерево. Определим для него функцию Ф (Т) как количество красных узлов в дереве Т. Предположим, что одной единицы потенциала достаточно для оплаты структурной модификации, выполняющейся в любом из трех случаев процедуры КВ 1нзект Р!хор. в) Пусть Т' — результат применения случая 1 процедуры КВ 1НЗЕКт Р[хоР к дереву Т.
Докажите, что Ф (Т') = Ф (Т) — 1. г) Операцию вставки узла в красно-черное дерево с помощью процедуры КВ 1нзект можно разбить на три части. Перечислите структурные модификации и изменения потенциала, которые происходят в результате выполнения строк 1 — 1б процедуры КВ 1нзект для Глава 17. Амортизационный анализ 509 незавершающих случаев процедуры КВ 1нзект Р~хор и для завер- шающих случаев этой процедуры.
д) Воспользовавшись результатами, полученными в части г), докажите, что амортизированное количество структурных модификаций, которые выполняются при любом вызове процедуры ВВ 1нзнкт„ равно О (1). Теперь нам нужно доказать, что если выполняются и вставки, и удаления, то производится О (пз) структурных модификаций. Для каждого узла х определим величину О если т красный, 1 если х черный и не имеет красных дочерних узлов, О если х черный и имеет один красный дочерний узел, 2 если т черный и имеет два красных дочерних узла.
ю(х) = Теперь переопределим потенциал красно-черного дерева в виде Ф(Т) = ~) ю(х), хЕТ е) Покажите, что для всех незавершающих случаев процедуры КВ 1нзнктйхиг выполняется неравенство Ф (Т') < Ф (Т) -1. Докажите, что амортизированное количество структурных модификаций, которые выполняются в произвольном вызове процедуры ЙВ 1нзнкт Р~хи', равно 0 (1). ж) Покажите, что для всех незавершающих случаев процедуры КВ Рн.нтн Р~хн' выполняется неравенство Ф(Т') < Ф(Т) — 1.
Докажите, что амортизированное количество структурных модификаций, которые выполняются в произвольном вызове процедуры йВ Рн.нтн Риал, равно 0(1). з) Завершите доказательство того, что в наихудшем случае в ходе выполнения произвольной последовательности т операций КВ 1нзлкт и КВ Ра.нтн производится 0 (т) структурных модификаций. и обозначим через Т' дерево, получающееся в результате применения любого незавершающего случая процедуры КВ 1нзЕнт Р~хы' или КВ Пньнтн Р~хш к дереву Т. Часть 1Ч. Усовершенствованные методы разработки и анализа 510 Заключительные замечания Групповой анализ был использован Ахо (АЬо), Хопкрофтом (Норсгой) и Ульманом (1Л!шап) [5!.
Таржан (Тат)ап) [293! представил обзор разновидностей метода бухгалтерского учета и метода потенциала, использующихся в амортизационном анализе, а также некоторые их приложения. Метод бухгалтерсюго учета он приписывает нескольким авторам, включая Брауна (М.К. Вгозчп), Таржана, Хаддельстона (Б. НшЫе!згоп) и Мельхорна (К.
МеЬ1Ьогл). Метод потенциала он приписывает Слитору (Р.Р. Б1еагог). Термин "амортизационный" вошел в обиход благодаря Слитору и Таржану. Потенциальные функции оказываются полезными также при доказательстве нижних границ в задачах определенных типов. Для каждой конфигурации, возникающей в такой задаче, определяется потенциальная функция, отображающая эту конфигурацию на действительное число. После этого определяется потенциал Фган начальной конфигурации, потенциал Ф г;„,! юнечной конфигурации и максимальное изменение потенциала сзФ в результате выполнения произвольного шага.
Таким образом, число шагов должно быть не меньше г*"," '"" . При~~п~вх меры использования потенциальных функций для обоснования нижних границ при оценке сложности ввода-вывода представлены в работах Кормена (Сопиев) [711, Флойда (г!суй) [9!1, а также Аггарвала (Аяяапча1) и Витгера (Ч!цег) [4). Крумм (Кгшшпе), Цыбеню (СуЬетйо) и Венкатараман (Чеп1сагагашап) [194] воспользовались потенциальными функциями для оценки нижних границ скорости раслрося1раяения слухов (яозз1ршя): передачи единственного элемента из каждой вершины графа во все другие вершины.
Введение Эта часть возвращает нас к изучению структур данных, поддерживающих операции над динамическими множествами, но уже на более высоком уровне по сравнению с частью 111. В двух главах этой части мы, например, будем испольювать технологии амортизационного анализа, которые рассматриваются в главе 17. В главе 18 мы рассмотрим В-деревья, которые представляют собой сбалансированные деревья поиска, разработанные специально для хранения информации на дисках.
Поскольку дисковые операции существенно медленнее, чем работа с оперативной памятью, производительность В-деревьев определяется не только временем, необходимым для проведения вычислений, но и количеством необходимых дисковых операций. Для каждой операции с В-деревом количество обращений к диску растет с ростом высоты В-дерева, так что мы должны поддерживать ее невысокой.
В главах 19 и 20 рассматриваются различные реализации объединяемых пирамид, которые поддерживают операции 1)чзект, Меч)м!)м, Ехтклст М!)ч и 1))ч)он (операция 17)ч)от! обьединяет две пирамиды). Структуры данных в этих главах, кроме того, поддерживают операции Рн.ете и Пескелзе Кеу. Биномиальные пирамиды, о которых речь пойдет в главе 19, поддерживают все перечисленные операции со временем выполнения О (18 п) в худшем случае (и — общее количество элементов в пирамиде (или в двух пирамидах в случае операции 1))ч)о!ч).
При необходимости поддержки операции 11)ч)о)ч биномиальные пирамиды превосходят бинарные пирамиды из главы 6, поскольку последним в наихудшем случае требуется для объединения двух пирамид время г=г (гг). Фибоначчиевы пирамиды (глава 20) представляют собой усовершенствованные биномиальные пирамиды — по крайней мере, теоретически. Для оценки производительности Фибоначчиевых пирамид используется амортизированное время выполнения операций.
Операции 1)чзект, Мп п)мим и 1))ч)о)ч у Фибоначчиевых пирамид имеют амортизированное (а также фактическое) время работы, равное О (1), а операции Ехтклст Мпч и Редеете — О (18 гз). Главное преимущество Фибоначчиевых пирамид, однако, заключается в том, что операция Пескелзе Кет имеет амортизированное время О (1). Именно это свойство делает Фибоначчиевы пирамиды ключевым компонентом ряда наиболее быстрых асимптотических алгоритмов для работы с графами. И наконец, в главе 21 представлены структуры данных для хранения непересекающихся множеств. У нас имеется универсум из и элементов, сгруппированных ! Как и в задаче !0-2, мы определяем обьединяемые пирамиды как поддерживающие операции Мгюмим н Ехтклст Мги, так что мы можем называть их обьединнемыми неубывающими пирамидами !тсгясаые пнп-)геарз).
Если в пирамиде поддерживаются операции Млхгмпм и Ехтклст Млхгмом, ее можно называть обьеднннемой невозрастающей пирамидой (тегяеаые гпах-ьсар). Часть Ч. Сложные структуры данных 513 в динамические множества. Изначально каждый элемент принадлежит своему собственному множеству. Операция Бьлон позволяет объединить два множества, а запрос Рпчп Яет определяет множество, в котором в данный момент находится искомый элемент. Представляя каждое множество в виде простого корневого дерева, мы получаем возможность удивительно производительной работы: последовательность из гп операций выполняется за время О (та (и)), где а (и)— исключительно медленно растущая функция и не превышает 4 для всех мыслимых приложений. Амортизационный анализ, который позволяет доказать эту оценку, столь же сложен, сколь проста сама используемая структура. Рассмотренные в этой части книги структуры данных — не более чем примеры "сложных" структур данных, и множество интересных структур сюда не вошли.
Хотелось бы упомянуть следующие из ннх. ° Динамические деревья (бупаш1с ггеев), разработанные Слитором (81еагог) и Таржаном (Тат)ап) 1281, 2921, поддерживают лес из непересекающихся деревьев. Каждое ребро каждого дерева имеет некоторую стоимость, выраженную действительным числом. Динамические деревья поддерживают запросы поиска родителя, корня, стоимости ребра и минимальной стоимости ребра на пути от узла к корню.
У деревьев могут удаляться ребра, может изменяться стоимость на пути от узла к корню, корень может связываться с другим деревом, а также делать узел корнем дерева, в котором он находится. Имеется реализация динамических деревьев, которая обеспечивает амортизированное время работы каждой операции, равное О (18 и); другая, более сложная реализация обеспечивает время работы О (18 и) в наихудшем случае.
° Расширяющиеся деревья (вр1ау ггеев), также разработанные Слитором (81еагог) и Таржаном (Тат)ап) 1282, 292], представляют собой версию бинарных деревьев поиска, в которых операции поиска имеют амортизированное время работы О (18 и). Одно из применений расширяющихся деревьев — упрощение реализации динамических деревьев. ° Перманентные стРуктуры (регв(всеп~ бага всгиспзгев), которые обеспечивают возможность выполнения запроса о предшествующих версиях структуры данных, а иногда и их обновления. Соответствующие методы с малыми затратами времени и памяти были предложены в работе [821 Дрисколлом (13пвсо1!), Сарнаком (Багпак), Слитором (81еаГог) и Таржаном (Тат)ап). В задаче 13-1 приведен простой пример перманентного динамического множества.
° Ряд структур данных обеспечивает более быстрое выполнение словарных операций (1мвект, 1)ег.его, Яелксн) для ограниченных универсумов ключей. Использование ограничений позволяет получить лучшее асимптотическое время работы, чем для структур данных, основанных на сравнении. 514 Часть Ч. Сложные структуры даннмт Структура данных, предложенная Ван Эмде Боасом (чап Епн1е Воаз) [301], обеспечивает в наихудшем случае время выполнения операций М~ямни, МАхтмнм, 1нзект, 13ет.ете, ЯеАксн, ЕхткАст М!и, ЕхткАст МАх, Ркепесеззок и Бттссеззок, равное 0(1к1ктт), если ключи ограничены миске.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
