Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 128
Текст из файла (страница 128)
В наихудшем случае наряду с вызовом Ркото-чЕВ-Мпимпм она делает еще два рекурсивных вызова. Процедура Рното-чЕВ-Бпссеазок(К х) возвращает наименьший элемент в протоструктуре К, больший, чем х, или значение нп., если в К нет элемента, большего, чем х. Условие, чтобы элемент х имелся в множестве, не ставится, но предполагается, что О < х < К и. Рното-чЕВ-Боссеззок(К х) 1 1ТКи== 2 2 !Гх== о и КА[1] ==1 3 ге!пгп 1 4 е!ве гегпгп мп.
5 е!ве оДве! = Ркото-чЕВ-Боссеззок(К с1ив!ег(Ь18Ь(х)), 1ои(х)) б !Т оЯЪе! ф мн. 7 гегпгп 1пе!ех(1щЬ(х), обЪе!) 8 еье васс-с1иввет = Ркото-чеВ-Бпссеззок(квиттагу,ыйь(х)) 9 !Г васс-с1ив!ет == ып. 10 ге!игл нп. 11 е!ве о5евег = Рното-чеВ-м!ьпмпм(к с(ив!ет(васс-с1ив!ет)) 12 ге!пгп 1пе) ех(висс-с(ив!ет, обеве1) Часть и Сложные струюпуры данныл 5вО Процедура Ркото-ЧЕВ-Боссняяок работает следующим образом. Как обычно, в строке 1 проверяется базовый случай, обрабатываемый методом грубой силы в строках 2-4: единственный вариант наличия преемника у х в структуре рто1о-иЕВ(2) — при х = 0 и А[1), равном 1.
В строках 5 — 12 выполняется обработка рекурсивного случая. В строке 5 выполняется поиск преемника х в кластере х с присваиванием результата переменной обЬек В строке б определяется, имеет ли х преемника в своем кластере; если имеет, то строка 7 вычисляет и возвращает значение этого преемника. В противном случае требуется выполнить поиск в других кластерах. В строке 8 переменной лисс-с1ив1ет присваивается номер следующего непустого кластера с использованием резюмирующей информации для его поиска. В строке 9 выполняется проверка равенства лисс-с1ив1ет значению Мй., при этом, если все последую1цие кластеры пусты, в строке 10 процедуры возвращается значение ми..
Если лисс-с)извет не равно н1ь, то в строке 11 переменной обве1 присваивается первый элемент этого кластера, а строка 12 вычисляет и возвращает минимальный элемент в данном кластере. В наихудшем случае процедура Рното-ЧЕВ-Босскяяок рекурсивно вызывает сама себя дважды для структур рто1о-иеВ(,,/й) и делает один вызов РкоточеВ-м1м1МОМ для структуры рто1о-иеВ(,/й). таким образом, рекуррентное соотношение для времени работы процедуры Рното-ЧЕВ-815сскяяок в наихудшем случае Т(и) имеет вид Т(и) = 2Т( и) + сл(18 Ч'и) = 2Т(чти) + 6(18и) . Можно применить ту же методику, что и для рекуррентного соотношения (20.1), и показать, что данное рекуррентное соотношение имеет решение Т(и) ев(18 и 18 18 и).
Таким образом, Ркото-ЧЕВ-Зссскяяок асимптотически медленнее РКОТО-ЧЕВ-М1Н1МОМ. Вставка элемента Для вставки элемента необходимо вставить его в соответствующий кластер, а также установить резюмирукиций бит этого кластера равным 1. Процедура Ркото-ЧЕВ-1мяккт()т, х) вставляет значение х в протоструктуру 1т. Ркото-чЕВ-11няект(т', х) 1 111л.и==2 2 у'.А[х) = 1 3 еЬе Рното-ЧЕВ-1няккт(1т. с1ив1ет[Ь18Ь(х)), 1ож(х)) 4 Ркото-ЧЕВ-1няякт(1т.виттату, Ь18Ь(х)) В базовом случае строка 2 устанавливает соответствукиций бит в массиве А равным 1. В рекурсивном случае рекурсивный вызов в строке 3 вставляет х в соответствующий кластер, а строка 4 устанавливает резюмирующий бит этого кластера равным 1. Гаева ед деревья вая Эмде Баева Поскольку процедура Ркото-чЕВ-1нзект в наихудшем случае делает два рекурсивных вызова, ее время работы характеризуется рекуррентным соотношением (20.3).
Следовательно, время работы процедуры Ркото-чЕВ-1нзект равно 9(1би). Удаление элемента Операция Оееете более сложная, чем операция вставки. В то время как при вставке всегда можно установить резюмирующнй бит равным 1, при удалении сбросить резюмирующий бит в 0 можно не всегда. Нужно определить, есть ли в данном кластере единичные биты. Исходя из определения протоструктур, требуется исследовать все ч'и бит кластера, чтобы выяснить, есть ли среди них хотя бы один, равньвй 1. В качестве альтернативы в протоструктуру можно добавить атрибут п, указывающий количество элементов в ней. Реализация процедуры Ркото-чЕВ-1)ееете оставлена читателям в качестве упр. 20.2.2 и 20.2.3. Очевидно, что нам нужно так модифицировать протоструктуру ван Эмде Боаса таким образом, чтобы каждая операция выполняла не более одного рекурсивного вызова.
Из следующего раздела вы узнаете, как это можно сделать. Упражнения 20.2.2 Напишите псевдокоды процедур Ркото-чЕВ-МАх~мом н Ркото-чЕВРкеоесеззок. 20.2.2 Напишите псевдокод процедуры Ркото-чЕВ-Оееете. Она должна обновлять соответствующий резюмирующий бит путем сканирования соответствующих битов кластера.
Каково время работы вашей процедуры в наихудшем случае? 20.2.3 Добавьте к каждой протоструктуре атрибут и, указывающий количество элементов, которое она представляет во множестве в данный момент, и напишите псевдокод процедуры Рното-чЕВ-Рееете, использующий этот атрибут и для принятия решения о сбросе резюмирующих битов в О. Каково время работы вашей процедуры в наихудшем случае? Какие другие процедуры должны быть изменены в связи с добавлением этого нового атрибута? Повлияют ли эти изменения на времена работы этих процедур? 20.2.4 Модифицируйте протоструктуру таким образом, чтобы она поддерживала дублирующиеся ключи. 20.2.5 Модифицируйте протоструктуру таким образом, чтобы она поддерживала ключи со связанными с ними сопутствующими данными.
Часть и Сложные струннеры данных 58л гО.гсв Напишите псевдокод процедуры, создающей протоструктуру рго1о-оЕВ(и). го.г.у Докажите, что если выполняется строка 9 процедуры Ркото-чЕВ-М1 п~мпм, то протоструктура пуста. го.г.в Предположим, что разработана протоструктура, в которой каждый массив с1ил1ег имеет только иь/4 элементов. Какими будут времена работы каждой из операций? 20.3.
Дерево ван Эмде Бааса Протоструктура из предыдущего раздела не позволяет достичь искомого времени работы 0(1к 1к и). Это связано с тем, что в большинстве операций требуется слишком много рекурсивных вызовов. В этом разделе мы разработаем структуру данных, подобную протоструктуре ван Эмде Боаса, но хранящую немного больше информации и тем самым устраняющую необходимость в части рекурсии. В разделе 20.2 мы видели, что сделанное предположение о размере универсума — и = 2 для некоторого целого )с — неоправданно ограничивает возможные эь значения и слишком разреженным множеством значений. Начиная с этого момента мы позволяем размеру универсума быть любой точной степенью 2 и, когда ь/й не является целым числом (т.е. и представляет собой нечетную степень 2; и = 2э"+1 для некоторого целого )с ) О), мы будем делить |я и бит числа на старшие ((10 и)/21 бнт и младшие ~(!би)/2) бит.
Для удобства обозначим 2(ОЯ")/з) ("верхний квадратный корень" и) как чл/й, а 21('Я )/з) ("нижний квадратный корень" и) как чь/й„так что и = чл/й чьсй и, когда и представляет собой четную степень 2 (и = 2эн для некоторого целого й), ~~~й = ь/й = чсй. Поскольку мы позволяем и быть нечетной степенью 2, следует переопределить вспомогательные функции из раздела 20.2: ЫОЬ(х) = (х/т/й), 1олч(х) = х пюс1 эь/й, 1пг(ех(х, у) = х чьгй+ у .
20.3.1. Деревья ван Эмде Боаса Дерево ван Эмде Бааса (чап Епйе Воаз ггее — чЕВ-дерево), модифицирует протоструктуру ван Эмде Боаса. Обозначим чЕВ-дерево с размером универсума и как чЕВ(и) и, если только и не равно базовому размеру 2„с атрибутом аиглтагу, указывающим на деРево чЕВ( чл/й), и с массивом с1ил1ег'10 .. чл/й — Ц, Указывающим на деревья ~~й иЕВ( ь/й).
Как показано на рис. 20.5, чЕВ-дерево содержит два атрибута, отсутствующие в протоструктуре; )лава 20. Деревья ввя Эмде Боаса оЕВ(ьз2й) Чзи оЕВ( и)-деревьев Ряс. 20.5. информапнл в оеВ(и)-дереве прн и > 2. структура содерлоп размер универсума и, элементы оззн н озее, улазатель виозозосу на дерево оЕВ(ьзтй) н масона сньяес]О..
ьзlй — 1] вз ~(/й указателей на оЕВ(4й)-деревья. гпзп хранит минимальный элемент чЕВ-дерева; тох хранит максимальный элемент чЕВ-дерева. Кроме того, элемент, хранящийся в тт, не появляется ни в одНом из рекурсивных деревьев оЕВ(4lй), на которые указывает массив с1ил1ег. 'Таким образом, элементы, хранящиеся в иЕВ(и)-дереве ч", представляют собой К тт плюс все элементы, рекурсивно храняпшеся в чЕВ(Ки)-деревьях, на которые указывают )2. с1ил(ег[0 ..
~~/й — Ц. Заметим, что, югда чЕВ-дерево содержит два или более элементов, мы рассматриваем тт и кпах по-разному: элемент, хранящийся в тзп, не появляется ни в одном из кластеров, в отличие от элемента тах, который располагается в кластере (кроме случая, когда чЕВ-дерево содержит единственный элемент, так что минимальный и максимальный элементы совпадают). Поскольку базовый размер равен 2, чЕВ(2)-дерево не нуждается в массиве А, который имеет соответствующая структура рго1о-иЕВ(2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
