Алгоритмы - построение и анализ (1021735), страница 104
Текст из файла (страница 104)
Затем опишите корректное красно- черное дерево с и узлами, в котором вызов процедуры КВ 13еьете для удаления определенного узла приводит к Й (!8п) изменениям цвета. Несмотря на то, что в наихудшем случае количество модификаций цветов, приходящихся на одну операцию, может определяться логарифмической функцией, мы докажем, что произвольная последовательность гл операций КВ 1нзект и КВ 1)е!.ете, выполняемых над изначально пустым красно-черном деревом, в наихудшем случае приводит к 0(т) структурным модификациям.
б) Некоторые из случаев„обрабатываемых в основном цикле кода процедур КВ 1хзект Р!хаев и КВ 0н.ете Рий3Р, являются завершающими (гепшпайп8): однажды случившись, они вызовут завершение цикла после выполнения фиксированного количества дополнительных операций. Установите для каждого случая, встречающегося в процедурах КВ 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 для всех мыслимых приложений. Амортизационный анализ, который позволяет доказать эту оценку, столь же сложен, сколь проста сама используемая структура.
Рассмотренные в этой части книги структуры данных — не более чем примеры "сложных" структур данных, и множество интересных структур сюда не вошли. Хотелось бы упомянуть следующие из ннх. ° Динамические деревья (бупаспсс сгеев), разработанные Слитором (81еасог) и Таржаном (Тат)ап) 1281, 2921, поддерживают лес из непересекающихся деревьев. Каждое ребро каждого дерева имеет некоторую стоимость, выраженную действительным числом. Динамические деревья поддерживают запросы поиска родителя, корня, стоимости ребра и минимальной стоимости ребра на пути от узла к корню. У деревьев могут удаляться ребра, может изменяться стоимость на пути от узла к корню, корень может связываться с другим деревом, а также делать узел корнем дерева, в котором он находится.
Имеется реализация динамических деревьев, которая обеспечивает амортизированное время работы каждой операции, равное О (18 и); другая, более сложная реализация обеспечивает время работы О (18 сс) в наихудшем случае. ° Рассниряющиеся деревья (вр1ау сгеев), также разработанные Слитором (81еасог) и Таржаном (Тагсап) 1282, 292], представляют собой версию бинарных деревьев поиска, в которых операции поиска имеют амортизированное время работы О (18 и). Одно из применений расширяющихся деревьев — упрощение реализации динамических деревьев. ° Перманентные стРуктуры (регсйвсепс ссаса всгпсспгев), которые обеспечивают возможность выполнения запроса о предшествующих версиях структуры данных, а иногда и их обновления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
