Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 114
Текст из файла (страница 114)
Операции 1р!еект, Мич!Мсм и У!ч2о!ч в пирамидах Фибоначчи обладают фактическим и амортизированным временем выполнения, равным 0(1), а операции Ехтклст-М!р! и Рееете обладают амортизированным временем работы 0(оп). Однако основное преимущество пирамид Фибоначчи в том, что !как н в задаче ! 02, мы определяем пирамиды как подлержввающне операции Мзщмцм л ЕХткллтМ!н, твк что лв можно называть ойъеднляемымн леубыеающмнв пнрямндямн. Еслн пнрамндой поддерживаются опералнн Мах!мою н Ехтклст-Млх, то такая пнрвмнда является одведнняеней нееозрасюающей янрамядей. Еслн не укюано иное, по умслчанню под объеднняемымн пнрамлдамл мы будем по!чзазумевать объединяемые неубываюшне пнрамнды. 5!9 Часть К Скажиые структуры даккык амортизированное время работы процедуры 13вскнлвн-Кву составляет всего лишь 0(1).
Именно зто свойство делает фибоначчиевы пирамиды ключевым компонентом ряда наиболее быстрых асимптотических алгоритмов для работы с графами. С учетом того, что нижняя граница времени сортировки П(п 18 и) может быть превзойдена в случае, когда ключи представляют собой целые числа из ограниченного диапазона, в главе 20 выясняется, можно ли разработать структуру данных, югорая поддерживает операции над динамическим множеством Белксн, 1ггвнкт, Пньнтн, Мцчгмим, Млх~мим, Биссеввок и Ркюеснввок со временем работы о(18п) для ключей, являющихся целочисленными значениями из ограниченного диапазона.
Оказывается, что ответ на этот вопрос положительный, если воспользоваться рекурсивной структурой данных, известной как дерево ван Эмде Боаса (чап Епн1е Впав). Если ключи представляют собой уникальные целые числа из множества (О, 1, 2,..., и — 1), где и является точной степенью 2, то деревья ван Эмде Боаса поддерживают выполнение всех перечисленных выше операций за время 0(18 18 и). И наконец в главе 21 представлены структуры данных для хранения непересекающихся множеств. У нас имеется универсум из и элементов, сгруппированных в динамические множества.
Изначально каждый элемент принадлежит своему собственному множеству. Операция 1)ьцом позволяет объединить два множества, а запрос Рпчп-Бет определяет множество, в котором в данный момент находится искомый элемент. Представляя каждое множество в виде простого корневого дерева, мы получаем возможность удивительно производительной работы: последовательность из тп операций выполняется за время 0(гл гк(п)), где се(п) — исключительно медленно растущая функция и не превышает 4 для всех мыслимых приложений.
Амортизационный анализ, который позволяет доказать эту оценку, столь же сложен, сколь проста сама используемая структура. Рассмотренные в этой части книги структуры данных — не более чем примеры "сложных" структур данных, и множество интересных структур сюда не вошли. Хотелось бы упомянуть следующие из них. Динамические деревья (дупапнс пеев), разработанные Слитором (8!еагог) и Таржаиом (Таг)ап) [317) и детально рассмотренные в [328), поддерживают лес из непересекающихся корневых деревьев. Каждое ребро каждого дерева имеет некоторую стоимость, выраженную действительным числом.
Динамические деревья поддерживают запросы поиска родителя, корня, стоимости ребра и минимальной стоимости ребра на пути от узла к корню. У деревьев могут удаляться ребра, может изменяться стоимость на простом пути от узла к корню, корень может связываться с другим деревом, можно также делать узел корнем дерева, в котором он находится. Имеется реализация динамических деревьев, которая обеспечивает амортизированное время работы каждой операции, равное 0(18 п); другая, более сложная, реализация обеспечивает время работы 0(18 п) в наихудшем случае. Расширяющиеся деревья (вр1ау ггеев), также разработанные Слитором (Я!еагог) и Таржаном (Таг)ал) [318) и также детально описанные в упоми- 520 Часть И Еложные структуры данных навшейся выше работе [328], представляют собой версию бинарных деревьев поиска, в которых операции поиска имеют амортизированное время работы 0(18п).
Одно из применений расширяющихся деревьев — упрощение реализации динамических деревьев. Перманенньные сглрукглурм (регяяепг бага впззспцев) обеспечивают возможность выполнения запросов о предшествующих версиях структуры данных, а иногда и их обновления. Соответствующие методы с малыми затратами времени и памяти были предложены в работе [96] Дрисколлом (1)пвсо!1), Сарнаком (Яагпак), Слитором (8!еагог) и Таржаном (Таг]ап). В задаче 13.1 приведен простой пример перманентного динамического множества.
Как и рассматриваемые в главе 20, ряд структур данных обеспечивает более быстрое выполнение словарных операций (1мввкт, !3вьвтк, 88Аксн) для ограниченных универсумов ключей. Такие ограничения позволяют получить лучшее асимптотическое время работы, чем для структур данных, основанных на сравнении. Фредман (Егейпап) и Виллард (М!1агб) [114] предложили использовать деревья слияний (йгв!оп !геев), которые были первыми структурами данных, обеспечивавшими повышение скорости словарных операций за счет ограничения пространства целыми числами.
Они показали, как можно реализовать зти операции, чтобы нх время работы составляло 0(18 и/ 18 18 и). Ряд других структур данных, включая экслоненниольные деревья лоиска (ехропепйа! веагс!г !геев) [16], также обеспечивают улучшение всех (нли некоторых) словарных операций и упоминаются в заключительных замечаниях в некоторых главах книги. Динамические графы (ь)упаппс 8гар!з) поддерживают различные запросы, позволяя структуре графа изменяться в процессе операций добавления или удаления вершин или ребер. Примеры поддерживаемых запросов включают связность вершин [165], связность ребер, минимальные остовные деревья [164], двусвязность и транзитивное замыкание [163].
В заключительных замечаниях к различным главам данной книги упоминаются, помимо описанных, некоторые другие структуры данных. Глава 18. В-деревья В-деревья представляют собой сбалансированные деревья поиска, созданные специально для эффективной работы с дисковой памятью (и другими типами вторичной памяти с непосредственным доступом). В-деревья похожи на красно- черные деревья (см. главу 13), но отличаются более высокой оптимизацией дисковых операций ввода-вывода.
Многие СУБД используют для хранения информации именно В-деревья или их разновидности. В-деревья отличаются от красно-черных деревьев тем, что узлы В-дерева могут иметь много дочерних узлов — от нескольких штук до тысяч, так что степень ветвления В-дерева может быть очень большой (хотя обычно она определяется характеристиками используемых дисков). В-деревья схожи с красно-черными деревьями в том, что все В-деревья с и узлами имеют высоту 0(18п), хотя само значение высоты В-дерева существенно меньше, чем у красно-черного дерева за счет более сильного ветвления.
Таким образом, В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время 0(18 п). В-деревья представляют собой естественное обобщение бинарных деревьев поиска. На рис. 18.1 показан пример простого В-дерева. Если внутренний узел х В-дерева содержит х. п ключей, то у него х. п + 1 дочерних узлов. Ключи в узле х используются как разделители диапазона ключей, с которыми имеет дело данный узел, на х.
п + 1 поддиапазонов, каждый из которых относится к одному из дочерних узлов х. При поиске ключа в В-дереве мы выбираем один из (х. п + 1) дочерних узлов путем сравнения искомого значения с х. и ключами, хранящимися в узле х. Структура листьев В-дерева отличается от структуры внутренних узлов; мы рассмотрим эти отличия в разделе 18.1. В разделе 18.1 приведено точное определение В-деревьев и доказан логарифмический рост высоты В-дерева в зависимости от количества его узлов.
В разделе 18.2 описаны процессы поиска в В-дереве н вставки элемента в В-дерево, а в разделе 18.3 рассматривается процесс удаления из В-дерева. Однако перед тем как приступить к работе с В-деревьями, давайте выясним, почему структуры данных, созданные для работы с дисковой памятью, так отличаются от структур для работы с оперативной памятью. 525 Глава /8.
В-дерееьл называется дгтргажкой (4гасх). Наличие нескольких дисков в одном накопителе увеличивает его емкость, но не его производительность. Хотя диски существенно дешевле оперативной памяти и имеют высокую емюсть, из-за механически движущихся частей они гораздо, гораздо медленнее оперативной памяти.' Механическое движение головки относительно диска определяется двумя компонентами — перемещением головки по радиусу и вращением днсюв.
Когда были написаны зти строки, типичная скорость вращения дисюв составляла 5400-15 000 об/мин (гргп). Обычно диски со скоростью 15 000 об/мин можно встретить в мощных серверах, скорость 7200 обычна для настольных систем, а 5400 — для переносных. Хотя скорость 7200 об/мин может показаться очень большой, один оборот требует примерно 8.33 мс, что более чем на 5 порядков превышает время обращения к оперативной памяти (которое обычно составляет примерно 50 нс). Другими словами, пока мы ждем оборота диска, чтобы считать необходимые нам данные, из оперативной памяти мы могли бы получить зги данные почти 100000 раз! В среднем приходится ждать только половину оборота диска, но это практически ничего ие меняет. Радиальное перемещение головок также требует времени. Одним словом, во время написания этих строк среднее время доступа к дисковой памяти для распространенных дисков составляло 8-11 мс, Для того чтобы сократить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение сразу к нескольким элементам, хранящимся на диске.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
