Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 127
Текст из файла (страница 127)
На базовом уровне элементы фактических динамических множеств хранятся в некоторых из структур ртого-нЕВ(2), а остальные структуры рто1о-нЕВ(2) хранят резюмирующие биты. На рисунке под каждой из нерезюмирующих базовых структур указано, какие биты в ней хранятся. Например, структура рто1о-нЕВ(2), Рекурсивно определим для универсума (О, 1, 2,..., и — 1) нрозносозрунзнууб оон змдо Бааса (ргото уап епи)е Воаз янцсппе — рнзго-неВ-структуру), которую обозначим как рто1о-иЕВ(и). Каждая структура ргого-нЕВ(и) содержит атрибут и, указывающий размер универсума.
В дополнение к этому структура содержит следующее. Часть К Сналсные структуры данных 516 1 $151611' 611161 э вя э щп Эьонвпю !ЗЛЗ Эяь ипн МЛ5 Рис. 26 4. Структура ргозо-еЕВ(16), представляющая множество (2, 3, 4, 5,7, 14, 15). Она указывает нв чепяре структуры ргосо-иЕВ(4) в сйисег(О .. 3) и на резюмирующую структуру, авторах гешке представляет собой ргом-оЕВ(4), Кюклаа структура ргого-сЕВ(4) уыюьпмет на две структуры ргого-ееВ(2) в с!изгег]О.. Ц и на резюмирующую ргого-иеВ(2), кажаав сгрукгура ргоьо-иЕВ(2) соаерхгит только массив А[О .. Ц нз двух битов. Структуры ргоЗо-оЕВ(2) над 'Элементы г,з'" хранят биты 1 и У фактического динамического множества, а сгруатуры ргого-иеВ(2) над "Кластеры з,з" храпах биты зошглагу для кластеров г и У в структуре ргозо-оЕВ(16) верхнего уровня.
Для ясности темная штриховка указываег прозострухтуру верхнего уровня, юторал хранит резюмирующую информацию длв родительской структуры; во всем остальном гакаа протострук. тура илевтична другим прогосгруатурам с тем же размером универсума. помеченная как "Элементы 6,7", хранит бит 6 (нулевой, поскольку элемент 6 в множестве отсутствует) в своем элементе А[0] и бит 7 (единичный, поскольку элемент 7 присутствует в множестве) в своем элементе А[1]. Подобно кластерам, каждая резюмирующая структура представляет собой просто динамическое множество с размером универсума з(й, так что мы представляем ее с помощью структуры ргого-иЕВ(,Я.
Четыре резюмирующих бита для основной струатуры рто$о-иЕВ(16) находятся в крайней слева структуре рго1о-иЕВ(4) и в конечном итоге — в двух структурах рго4о-иЕВ(2). Например, структура рго8о-оЕВ(2), помеченная как "Кластеры 2,3", имеет А[0] = О, что говорит о том, что в кластере 2 структуры рго1о-оЕВ(16) (содержащем элементы 577 Глава 2К деревья ван ЭМде Бааса 8-11) содержатся толью нули О, и А]1] = 1, что говорит нам о том, что в кластере 3 (содержащем элементы 12-15) имеется как минимум одна единица. Каждая структура рю1о-вЕВ(4) указывает на свое резюме, хранящееся в виде структуры рю1о-иЕВ(2).
Взгляните, например, на структуру рю1о-иЕВ(2) слева от структуры, помеченной как аЭлемеиты О, Г'. Посюльку ее элемент А[0] равен О, значит, все элементы структуры "Элементы О,Г' нулевые, а поскольку ее элемент А(Ц равен 1, мы знаем, что структура "Элементы 2,3" содержит как минимум одну единицу. 20.2.2. Операции с протоструктурами ван Эмде Бааса Теперь опишем, как выполняются операции над протоструктурами ван Эмде Бааса. Сначала будут рассмотрены запрашивающие операции МЕМВЕК, М1Х1МОМ и ЯОССЕЯЯОК, которые не изменяют протоструктуру. Затем рассмотрим операции 11ЧЗЕКТ и ПЕЕЕТЕ. Операции МАХ1МОМ и РКЕОЕСЕЗЗОК, симметричные операциям М11ч1мом и Зоссеззок соответственно, мы оставим в качестве упр. 20.2.1. Каждая из операций Мемвек, Зоссеззок, Ркеоесеззок, 11чзект и 13ееете получает параметр х и протоструктуру К.
В каждой операции предполагается, что 0 < х < К и. Определение наличия значенин в множестве Для выполнения операции Мемвек(х) необходимо найти бит для х в соответствующей структуре рго1о-ЧЕВ(2). Это можно сделать за время О(!к!ки), полностью минуя структуры зиглгпагу. Приведенная далее процедура получает рюго-ЧЕВ-структуру К и значение х, и возвращает бит, указывающий, входит ли х в динамическое множество, хранимое структурой К. Ркото-чЕВ-Мемвек(К х) 1 !з" Ки== 2 2 гензгп К А]х] 3 е!зе гегцгп Ркото-чЕВ-Мемвек(К с!ие1ее (Ыф~(х)], 1оче(х)) Процедура Ркото-чЕВ-Мемвек работает следующим образом. В строке 1 выполняется проверка базового случая, когда К представляет собой структуру рю1о-ЧЕВ(2).
Строка 2 обрабатывает базовый случай, просто возвращая соответствующий бит массива А. Строка 3 работает рекурсивно, "погружаясь" в соответствующую меньшую протоструктуру. Значение ЬщЬ(х) указывает, какая структура рю1о-иЕВ(з7и) посещается, а 1ож(х) определяет запрашиваемый в структуре рю1о-зЕВ(ч'и) элемент. Давайте посмотрим, что происходит при вызове Ркото-ЧЕВ-Мемвек(К 6) для структуры ргого-иЕВ(16) на рис. 20.4. Поскольку Ь!кЬ(6) = 1 при и = 16, мы рекурсивно обращаемся к структуре рю1о-иЕВ(4) справа вверху и запрашиваем элемент!оле(6) = 2 этой структуры. В этом рекурсивном вызове и = 4, так что рекурсия продолжается.
В случае и = 4 мы имеем Ь!кЬ(2) = 1 и 1ож(2) = О, 1взвЕ 372Е 57я Часть и Сложные структуры данник так что мы запрашиваем элемент 0 структуры рго1о-ЧЕВ(2) справа вверху. Этот рекурсивный вызов оказывается базовым случаем, так что цепочка рекурсивных вызовов возвращает А[О] = О. Таким образом, вызов Рното-ЧЕВ-Мвмввк(17, 6) возвращает О, указывая, что элемент 6 в множестве отсутствует.
Для определения времени работы Рното-ЧЕВ-Мвмввк обозначим время работы со структурой рто1о-иЕВ(и) через Т(и). Каждый рекурсивный вызов требует константного времени (не включая время, затрачиваемое вызовами, которые он выполняет в свою очередь). Когда процедура Ркото-ЧЕВ-Мвмввк делает рекурсивный вызов, она обращается к структуре ргого-иЕВ(чти). Таким образом, время работы можно характеризовать рекуррентным соотношением Т(и) = Т(ч7и) + 0(1), с которым мы уже встречались в (20.2). Его решение имеет вид Т(и) = 0(18 18 и), и мы можем заключить, что время работы процедуры РкотоЧЕВ-Мвмввк составляет 0(18 18 и). Поиск минимального элемента Теперь рассмотрим, как выполнить операцию М1н1м11м.
Процедура РкотоЧЕВ-М1н1м15м($7) возвращает минимальный элемент в протоструктуре 17, или НП., если Ъ' представляет пустое множество. Рното-чЕВ-М!н1мом(Ъ') 1 !! 17. и == 2 2 !! 17. А [0] == 1 3 гевягп 0 4 е1веЫ 17. А[1] == 1 5 ге1пгп 1 б е1зе гегнгп н1ь 7 е!яе тгп-с1иягет = Ркото-ЧЕВ-М1х1м11м(17.яигптагу) 8 !Г т!п-с1иягет == г1И.
9 ге!ага мп. 10 е1яе о27яе! = РКОТО-ЧЕВ-М11Ч1М15М(Ъ'.с1ия1ет[гл!п-с1ия1ет]) 11 гегнгп 1пйех(гпзп-с1иягет, о))яе1) Эта процедура работает следующим образом. В строке 1 выполняется проверка базового случая, обрабатываемого в строках 2-6 методом "грубой силы". Рекурсивный случай обрабатывается строками 7 — 11. Сначала в строке 7 определяется номер первого кластера, который содержит элемент множества. Это делается с помощью применения рекурсивного вызова Ркото-ЧЕВ-М1м1мом к атрибуту 17. яитгпа771, который представляет собой структуру рто1о-иЕВ(,/и).
В строке 7 этот номер кластера присваивается переменной т!п-с1ия1ет. Если множество пустое, то рекурсивный вызов вернет значение мпа которое будет возвращено рассматриваемой процедурой в строке 9. В противном случае минимальный элемент множества находится где-то в кластере с номером т!п-с1ия1ет. Рекурсивный вызов в строке 10 находит смещение минимального элемента в пределах этого кластера. Наконец в строке 11 из номера кластера и смещения в кластере строится минимальный элемент и возвращается его значение.
579 Глава 2К деревьв вал Эмде Бааса Хотя запрос резюмирующей информации позволяет быстро найти кластер, содержащий минимальный элемент (поскольку эта процедура выполняет два рекурсивных вызова над структурами рто!о-иЕВ(чти)), в наихудшем случае время ее работы не равно 0(18 18 и). Обозначив через Т(и) время работы процедуры Рното-чеВ-мпч[мпм со структурой ртого-иеВ(и) в наихудшем случае, получаем рекуррентное соотношение Т(и) = 2Т(чГи) + 0(1) .
(20.3) Вновь применим замену переменных для решения этого рекуррентного соотно- шения, положив т = 18 и. Это дает Т(2 ) = 2Т(2 72) + 0(1) . Переименование Я(т) = Т(2 ) дает рекуррентное соотношение Я(т) = 2Я(т/2) + 0(1), которое, согласно случаю 1 основной теоремы, имеет решение Я(т) = тв(т). Возвращаясь от Я(т) к Т(и), получим Т(и) = Т(2 ) = Я(т) = еэ(т) = ел(18 и). Таким образом, мы видим, что из-за второго рекурсивного вызова время работы процедуры Рното-чЕВ-М1ьпмом равно ез(18 и), а не требуемому О(!8 1к и). Поиск преемника Операция БПССЕЗКОК еще хуже.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
