Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 131
Текст из файла (страница 131)
На первый взгляд, можно подумать, что рекуррентное соотношение (20.4) применимо не всегда, поскольку один вызов чЕВТкее-Рекете может сделать два рекурсивных вызова: один в строке 13, и вто- зчг Часть К Сложные структуры данные рой — в строке 15. Хотя процедура может сделать оба рекурсивных вызова, давайте подумаем о том, что произойдет в таком случае. Чтобы был выполнен рекурсивный вызов в строке 15, проверка в строке 14 должна показать, что кластер х пуст. Единственный вариант, при котором кластер х может быть пустым — если х был единственным элементом этого кластера прн выполнении рекурсивного вызова в строке 13. Но если х был единственным элементом своего кластера, то этот рекурсивный вызов выполняется за время О(1), так как в нем выполняются только строки 1 — 3.
Таким образом, есть две взаимоисключающие возможности. Рекурсивный вызов в строке 13 выполняется за константное время. Рекурсивный вызов в строке 15 не осуществляется. В любом случае время выполнения процедуры чЕВ-Ткее-Пееете характеризуется рекуррентным соотношением (20.4), а следовательно, в наихудшем случае оно составляет О(1к 1я и).
Упражнения го.з.г Модифицируйте чЕВ-дерево таким образом, чтобы оно поддерживало дублирующиеся ключи. го.з.г Модифицируйте чЕВ-дерево таким образом, чтобы оно поддерживало ключи со связанными сопутствующими данными. го.з.з Напишите псевдокод процедуры, создающей пустое дерево ван Эмде Боаса. го.з.4 Что произойдет при вызове процедуры чЕВ-Ткее-1нзект с элементом, уже имеющимся в чЕВ-дереве? Что произойдет при вызове процедуры чЕВ-ТкееПн.ете с элементом, которого нет в чЕВ-дереве? Поясните поведение процедур в этих ситуациях. Покажите, как модифицировать чЕВ-деревья н операции над ними, чтобы за константное время можно было убеждаться в наличии в них определенных элементов.
го.з.з Предположим, что вместо ~/и кластеров, каждый с размером универсума Члсй, мы строим чЕВ-деревья с иг?" кластерами, каждый с размером универсума иг '?ь, где lс ) 1 — константа. Каким будет время выполнения операций над таким деревом при нх соответствующей модификации? Для простоты анализа считайте, что и и'?, н и~ 1 ~ всегда являются целыми числами. го.з.б Создание чЕВ-дерева с размером универсума и требует времени еу(и). Предположим, что необходимо явно подсчитать зто время.
Каково минимальное количество !пана 10. деревьв аан Энде Боаса операций и, для которого амортизированное время каждой операции над чЕВ-де- ревом составляет 0(1й 1й и)? Задачи 20.1. Требовання деревьев ван Эмде Бааса и памяти В этой задаче исследуются требования деревьев ван Эмде Боаса к памяти и предлагается способ модификации структуры данных, при котором требуемая память зависит от количества ц фактически хранящихся в дереве элементов, а не от размера универсума и. Для простоты считаем, что ~/й всегда является целым числом.
а Поясните, почему требуемая деревом ван Эмде Боаса с размером универсума и память Р(и) характеризуется следующим рекуррентным соотношением: Р(и) = (ч/и+ 1)Р(ч/й) + гз(чги) . (20.5) б. Докажите, что рекуррентное соотношение (20.5) имеет решение Р(и) = 0(и). Чтобы уменьшить требуемое количество памяти, определим дерево ван Эмде Бааса ео сниженным палачеством помята (гебисеб-арасе чап Етбе Воаз пеев ИЛ-чЕВ-дерево) как чЕВ-дерево ч', но со следующими изменениями. Атрибут ч'. с1ив1ег вместо простого массива указателей на чЕВ-деревья с размером универсума ч/й представляет собой хеш-таблицу (см.
главу 11), сохраненную как динамическая таблица (см. раздел 17.4). Хеш-таблица, соответствующая "массивной" версии К с(ив1ег, хранит указатели на КБ-чЕВ-деревья с размером универсума ч/й. Чтобы найти 1-й кластер, мы ишем в хеш-таблице ключ 1, так что кластер может быть найден с помощью единственной операции поиска в хеш-таблице. В хеш-таблице хранятся указатели только на непустые кластеры. Поиск в хештаблице пустого кластера возврашает значение мп., указывающее, что искомый кластер пуст. Атрибут К виттагу в случае, когда все кластеры пустые, равен ьпь. В противном случае К виттагу указывает на КБ-чЕВ-дерево с размером универсума „/и.
Поскольку хеш-таблица реализована с использованием динамической таблицы, требуемая для нее память пропорциональна количеству непусгых кластеров. Когда нужно вставить элемент в пустое КЯ-чЕВ-дерево, мы создаем последнее с помощью следующей процедуры, где параметр и представляет собой размер универсума Кб-чЕВ-дерева. 594 Часть К Своэсные гтруюпуры даннмг СкеАте-Хе%-КЯ-УЕВ-Ткее(н) 1 Выделить память для нового 9ЕВ-дерева $' 2 (г.и=и 3 Гтт = нп. 4 У.тат = нп. 5 У.виттагу = нп.
6 Создать (г, с1ив1ег как пустую динамическую таблицу 7 ге$нгп У в. Модифицируйте процедуру чЕВ-Ткнн-1мзнкт таким образом, чтобы получить псевдокод процедуры КЯ-УЕВ-Тннн-1мзнкт(Ъ; х), которая вставляет а в КЯ-9ЕВ-дерево Ъ', вызывая при необходимости процедуру Скнлтн-ХнтчКЯ-чЕВ-Ткее. а Модифицируйте процедуру чЕВ-Тннн-ЯпсснззОк таким образом, чтобы получить псевдокод процедуры КЯ-УЕВ-Ткнн-Япсснззок(Ъ',х), которая возвращает преемник элемента х в КЯ-9ЕВ-дереве Ъ' или нп., если у х нег преемника в $'. д. Докажите, что в предположении простого равномерного хеширования процедуры КЯ-УЕВ-Ткнн-1нзнкт и КЯ-УЕВ-Ткнн-Япсснззок имеют ожидаемое амортизированное время работы, равное 0(!я 1к и).
в. В предположении, что элементы из 9ЕВ-дерева никогда не удаляются, докажите, что требуемая для КЯ-9ЕВ-дерева память равна 0(п), где и — количество элементов, фактически хранящихся в КЯ-ЧЕВ-дереве. ж. КЯ-9ЕВ-деревья имеют еще одно преимущество перед 9ЕВ-деревьями; у них меньшее время создания. Сколько времени требуется, чтобы создать пустое КЯ-чЕВ-дерево? 20.2. у-бысгирме лучи В этой задаче исследуются "у-быстрые лучи" ("у-Тазг птеа") Д.
Уилларда (П. %Ч11агб), в которых, как и в деревьях ван Эмде Бааса, каждая из операций Мнмннд, Мппмпм, МАх~мпм, Рннпнснззон и Япсснззон над элементами из универсума с размером и в наихудшем случае выполняются за время 0(!к 1к и). Амортизированное время выполнения операций 1нзнкт и Пнснтн также составляет 0(16 16 и). Подобно деревьям ван Эмде Бааса со сниженным количеством памяти (см. задачу 20.1), у-быстрые лучи используют для хранения и элементов только 0(п) памяти.
В дизайне у-быстрых лучей используется идеальное хеширование (см. раздел 11.5). Для разработки предварительной структуры предполаким, что мы создаем идеальную хеш-таблицу, содержащую не только каждый элемент динамического множества, но и каждый префикс бинарного представления каждого элемента множества. Например, если и = 16, так что 1к и = 4, и х = 13 находится в множестве, то,поскольку бинарное представление 13 представляет собой 1101,идеаль- Глава 2К деревья вам Эмде Баева 595 ная хеш-таблица должна содержать строки 1„11, 110 и 1101.
В дополнение к хештаблице мы создаем дважды связанный список элементов, находящихся в данный момент в множестве, в порядке их возрастания. ж Какое количество памяти требуется этой структуре данных? б. Покажите, как выполнить операции Мппмцм и Млхгмцм за время 0(1); операции Мемвек, Ркепесеззок и Бпссеззок — за время 0(1к1К и); операции 1мзект и Пееете — за время 0(1л и). Для снижения требований к памяти до О(и) внесем в структуру данных следующие изменения. Кластеризуем и элементов в и/1я и групп размером 1л и. (Будем считать, что и делится на 1к и.) Первая группа состоит из 1к и наименьших элементов множества, вторая группа — из следующих по величине 1к и элементов, и т.д.
Объявим "представительное" значение для каждой группы. Представитель г-й группы как минимум такой же по величине, как наибольший элемент в г-й группе, и меньше любого элемента (г+ 1)-й группы. (Представителем последней группы может быть наибольший возможный элемент и — 1.) Заметим, что представителем может быть и значение, в настоящий момент в множество не входящее. Будем хранить !к и элементов каждой группы в сбалансированном бинарном дереве поиска, таком как красно-черное дерево. Каждый представитель указывает на сбалансированное бинарное дерево поиска своей группы, а каждое сбалансированное бинарное дерево поиска указывает на представителя своей группы.
В идеальной хеш-таблице хранятся только представители, которые также находятся в дважды связанном списке в возрастающем порядке. Назовем такую структуру у-быстрывв лучам. а Покажите, что у-быстрый луч для хранения и элементов требует только 0(и) памяти. а Покажите, как выполнять операции Мпч!мсм и Млхгмсм в у-быстром луче за время 0(!к 1я и). д. Покажите, как выполнить операцию Мемвек за время 0(1к!к и). е. Покажите, как выполнять операции РКЕПЕСЕЗЗОК и ЯОССЕЗЗОК за время О(1б1ки). ж. Поясните, почему операции 1ызект и Пекете требуют времени П(1л 1к и). з. Покажите, как ослабить требование, чтобы каждая группа в у-быстром луче имела ровно !я и элементов для того, чтобы амортизированное время работы операций 1мзект и Ревете было равно О(1л 1л и), и при этом не повлиять на асимптотические времена работы других операций.
596 Часть Н Сяансные структуры ааннык Заключительные замечаияя Структура данных в этой главе названа по имени П. ван Эмде Боаса (Р. кап Епк1е Воаз), который изложил соответствующую идею в 1975 году [3371. В более поздних статьях ван Эмде Боаса [3381 и ван Эмде Боаса, Кааса (Кааз) и Зейлстры (Х151з~га) [339) эта идея была развита и уточнена. Впоследствии Мель- хорн (МеЫЬогп) и Няхер (Хапег) [2501 расширили эту идею для простых размеров универсумов. В книге Мельхорна [2471 используется несколько иной подход к деревьям ван Эмде Боаса, чем подход из данной главы.
Используя идеи, лежащие в основе деревьев ван Эмде Боаса, Дементьев (13егпеп11еу) и др. [821 разработали нерекурсивное трехуровневое дерево поиска, которое в их экспериментах по производительности превосходило деревья ван Эмде Боаса. Ванг (%ап8) и Лин (Ып) [345) разработали версии деревьев с использованием аппаратной конвейеризации, с константным амортизированным временем работы операций и 0(1818 и) стадиями конвейера. Патраску (Раггазси) и Торуп (ТЬогир) [271, 2721 показали, что нижняя граница времени поиска предшественника в дереве ван Эмде Боаса оптимальна (даже в случае разрешенной рандомизации). Глава 21.
Структуры данных для непересекающихся множеств В некоторых приложениях выполняется группировка и различных элементов в набор непересекающихся множеств. Две важные операции, которые должны выполняться с таким набором, — поиск множества, содержащего заданный элемент, и обьединение двух множеств. В данной главе мы познакомимся со структурой данных, которая поддерживает эти операции. В разделе 21.1 описаны операции, поддерживаемые указанной структурой данных, и представлено простое приложение. В разделе 21.2 мы рассмотрим использование простого связанного списка для представления связанных множеств. Более эффективное представление с помощью корневых деревьев приведено в разделе 21.3.
Время работы с использованием деревьев линейно для всех практических применений, хотя теоретически оно сверхлинейно. В разделе 2!.4 определяется и обсуждается очень быстро растущая функция и ее очень медленно растущая инверсия, которая и проявляется во времени работы операций над представлением непересекающихся множеств с использованием деревьев. Там же с помощью амортизационного анализа доказывается верхняя сверхлинейная граница времени работы. 21.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
