Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 129
Текст из файла (страница 129)
Вместо этого его элементы можно определить из атрибутов тзп и тах. В чЕВ-дереве без элементов, независимо от его размера универсума и, оба атрибута, тт и тах, равны ии.. На рис. 20.6 показано чЕВ(16)-дерево )2, хранящее массив (2, 3, 4, 5, 7, 14, 15) . Поскольку наименьшим элементом является 2, атрибут ) '. тпт равен 2, и несмотря на то что )з)к)з(2) = О, этот элемент 2 отсутствует в иЕВ(4)-дереве, на которое указывает )к. с1ив1ег]0]: обратите внимание, что К с1ил1ег]0]. тт равно 3, так что 2 в этом чЕВ-дереве отсутствует.
Аналогично, поскольку К с(ил1ег]0].тзп равно 3, и 2, и 3 являются единственными элементами в 1'. с1ил1ег]0], кластеры иЕВ(2) в ч'. с1ил1ет]0] пустые. Атрибуты тзи и тпах являются ключевыми элементами для снижения юличества рекурсивных вызовов в операциях над чЕВ-деревьями. Эти атрибуты служат четырем целям. 1.
Операции Мпч1мцм и Мдх~мпм не выполняют ни одного рекурсивного вызова, просто возвращая значения тт илн тах. 2. Операция Бцссеззок может избежать рекурсивных вызовов для определения, находится ли преемник значения х в Ыб)з(х). Это связано с тем, что преемник х находится в его кластере тогда и толью тогда, югда х строго меньше атрибута тах этого кластера. Симметричные рассуждения применимы к операции РКЕтэЕСЕЗЗОК и атрибуту тт. Часть и Слолслые смруюлуры данных Рнс. 20.6. иЕВ(16)-дерево, соответствующее рта то-иЕВ-дереку на рнс.
20.4. Оно хранит множество 12, 3,4, 5,7, 14, 15). Косые черты указыаают значения нп.. Значение, хранящееся е атрнбуте тап тЕВ-дерееа, не ноялляется нн а одном нз его кластеров. Темках штриховка служит той же нелл, что н на рнс, 20.4. 3. Исходя нз значений атрибутов пхзп и тпах тЕВ-дерева, можно за юнстантное время определить, пустое ли оно илн в нем есть один или как минимум два элемента. Эта возможность используется в операциях 1140ект и 0п.етн. Если и тхп, и пзах равны нць то чЕВ-дерево не содержит ни одного элемента. Если пьхп и тах не равны 1чпь но равны друг другу, значит, в чЕВ-дереве только один элемент.
В противном случае и паап, и пьат не равны ни нно ни лруг другу, и тЕВ-дерево содержит два или более элементов. 4. Зная, что чЕВ-дерево пустое, мы можем вставить в него элемент, просто обновляя его атрибуты тпап и тах. Следовательно, вставку в пустое дерево можно выполнить за юнстантное время. Аналогично, если мы знаем, что тЕВ-дерево содержит только один элемент, его можно удалить за юнстантное время простым обновлением атрибутов гпхп и тппх. Эти свойства позволят сократить цепочки рекурсивных вызовов. Глава гц деревья ван Эльое Боева 585 Даже если размер универсума и представляет собой нечетную степень 2, разница в размерах резюмируюшего чЕВ-дерева и кластеров не повлияет на асимптотическое время работы операций над чЕВ-деревом.
Все рекурсивные процедуры, реализующие операции над чЕВ-деревом, характеризуются рекуррентным соотношением Т(и) < Т(~/и) + О(1) . (20.4) Это рекуррентное соотношение похоже на рекуррентное соотношение (20.2), и решать его мы будем таким же способом. Положив т =!3 и, перепишем рекуррентное соотношение в виде Т(2 ) < Т(2( !~1) -1- О(1) . Заметив, что ! т/2~! < 2т/3 для всех т ) 2, мы имеем Т(2 *) < Т(2г .1~) + 0(1) Полагая Я(т) = Т(2 ), перепишем это последнее рекуррентное соотношение как Я(т) < Я(2т/3) + О(1), которое, в соответствии со случаем 2 основного метода, имеет решение Я(т) = 0(!к т). (В терминах асимптотического решения дробь 2/3 ничем не отличается от дроби 1/2, поскольку при применении основного метода мы находим, что 1окз~г1 = 1окг1 = О.) Таким образом, мы имеем Т(и) = Т(2 ) = Я(т) = 0(!ят) = 0(!к!ки).
Прежде чем использовать дерево ван Эмде Боаса, необходимо знать размер универсума и, чтобы иметь возможность создать представляющее пустое множество дерево ван Эмде Боаса соответствующего размера. В задаче 20.1 требуется показать, что общее жшичество памяти, требующееся для дерева ван Эмде Боаса, равно 0(и), а время создания пустого дерева составляет ьЭ(и). Вспомним, что, напротив, пустое красно-черное дерево можно создать за константное время.
Таким образом, мы можем отказаться от использования дерева ван Эмде Боаса в случае небольшого количества операций, поскольку время, требующееся для создания структуры данных, может превзойти экономию времени на отдельных операциях. Обычно этот недостаток не является существенным, поскольку, как правило, для представления множества с малым количеством элементов используются простые структуры данных, такие как массив или связанный список. 20.3.2. Операции над деревом ван Эмде Бокса Теперь мы готовы рассмотреть выполнение операций над деревом ван Эмде Боаса. Как и в случае протоструктуры ван Эмде Боаса, рассмотрим сначала запрашивающие операции, а затем — операции 1!чзект и Рн.втп.
Из-за небольшой асимметрии между минимальным и максимальным элементами в чЕВ-дереве— когда оно содержит как минимум два элемента, минимальный элемент, в отличие от максимального, в кластере не содержится — мы приведем псевдокоды для всех Часть Н Сложные структуры данные 58б пяти запрашивающих операций. Как и в случае операций над протоструктурами ван Змде Бааса, рассматриваемые здесь операции получают в качестве параметров К и х, где К представляет собой дерево ван Эмде Бааса, а х — элемент; при этом предполагается, что О < х < К и. Поиск минимального и максимального элементов Поскольку минимальный и максимальный элементы хранятся в виде атрибутов тт и тах, эти две операции имеют однострочный код и выполняются за константное время.
ЧЕВ-ТКЕЕ-М11н!М15М($'') 1 геянгн К тт чЕВ-Ткее-Млх1м15м (К) 1 гегпгв К тах Определение наличия значения в множестве Процедура чЕВ-Тквв-Мнмввк(Кх) имеет рекурсивный случай наподобие процедуры Ркото-ЧЕВ-Мкмввк, но базовые случаи несколько отличаются. Мы также проверяем, не равен ли х минимальному или максимальному элементу. Посюльку ЧЕВ-дерево не хранит биты, как зто делает протоструктура, процедура ЧЕВ-Тквн-Мемвек разработана таким образом, чтобы возвращать значения тК15В или рЛЬЗВ, а не 1 или О. чЕВ-Ткее-Мемвек(К х) 1 11 х == К тш или х == К тах 2 гензгв тк15Е 3 е1аеЫ К и == 2 4 гегпгн рльзк 5 е1ае гегпгп чЕВ-Ткни-Мнмввк(К с1ин1ег(Ь1йЬ(х)(,!о5ч(х)) В строке 1 выполняется проверка, не является ли х минимальным нли максимальным элементом.
Если является, то строка 2 возвращает значение тк15н. В противном случае в строке 3 выполняется проверка базового случая. Поскольку в базовом случае дерево иЕВ(2) не имеет элементов, отличных от хранящихся в атрибутах тт и тах, строка 4 возвращает значение рльзв. Другая возможность— югда случай не базовый, а х не равно ни т1и, ни тах — обрабатывается рекурсивным вызовом в строке 5. Время работы процедуры ЧЕВ-Тккв-Мкмввк характеризует рекуррентное соотношение (20.4), так что эта процедура выполняется за время 0(1я 1к и).
Поиск преемника и предшественника Теперь рассмотрим, как реализовать операцию Б15сскзкок. Вспомним, что процедура Ркото-ЧЕВ-Я15ссввзок(К х) может выполнять два рекурсивных вызова: один для определения того, находится ли преемник х в том же кластере, что 5я7 Гяаеа 7Д Деревья еая Эмде Бааса и х, и если нет, то еще один для поиска кластера, содержащего преемник х. Поскольку в дереве ван Эмде Бааса можно быстро получить доступ к максимальному элементу, двух рекурсивных вызовов можно избежать, ограничившись вместо иих одним рекурсивным вызовом либо над кластером, либо над резюмирующим массивом, но не над обоими.
чЕВ-Тккк-Япсскззок(К, х) 1 1ТКи== 2 2 !!'х == О и К тах == 1 3 гепвгп 1 4 е!ве гегвгп нп. 5 еЬе!Т К т1п ф нп. и х < К тзп 6 гетпгп К тт 7 еЬе тах-(оеа = чЕВ-Тккк-Млх!ыпм(К с!ив!ет[Ы8)т(х)[) 8 !!' тах-1оеа ~ ми. и !о» (х) ( тах-(оеа 9 опяе! = ЧЕВ-ТКЕЕ-ЗПССЕЗЗОК(К с!ив!ет[Ы8П(х)[, 1очч(х)) !О гецвгв !пе(ех(Ы8п(х), аЯяе!) 11 еье вися-с1ия!ет = чеВ-тккк-йпсскззок(кяиттату,ы8!ь(х)) 12 вв вися-с!ив!ет == !чн.
13 гегпгп ми. !4 е!ае оДяе! = чЕВ-Тккк-Мпч!мпм (К с!ив!ет[висс-с!ив!ет[) 15 гетвгп !пе!ех(васс-с!ия!ет, о((яе!) В этой процедуре шесть инструкций гегвгп и несколько ветвлений. Мы начинаем с базового случая а строках 2-4, возвращая при этом 1 в строке 3, если выполняется попьпка найти преемник О и 1 находится в 2-элементном множестве; в противном случае базовый случай возвращает мп. в строке 4. Если мы имеем дело не с базовым случаем, то следующей в строке 5 выполняется проверка, не является ли х строго меньше минимального элемента.
Если это так, мы просто возвращаем минимальный элемент в строке б. Если мы добрались до строки 7, то нам известно, что мы имеем дело не с базовым случаем и что х не меньше минимального значения чЕВ-дерева К. В строке 7 выполняется присваивание переменной тах-!аеа максимального элемента кластера х. Если кластер х содержит несколью элементов, больших х, то нам известно, что преемник х находится где-то в кластере х.
В строке 8 выполняется проверка этого условия. Если преемник х находится в кластере х, то в строке 9 выясняется, где именно в кластере он находится, а строка 1О возвращает преемник точно так же, как и строка 7 процедуры Ркото-чЕВ-Япсскззок. Мы попадаем в строку 11, если х не меньше, чем наибольший элемент в его кластере. В этом случае в строках 11-15 поиск преемника х выполняется таким же образом, как и в строках 8-12 процедуры Ркото-чЕВ-Бпсскззок. Легю увидеть, как рекуррентное соотношение (20.4) характеризует время работы процедуры чЕВ-Ткдк-Япсскззок, В зависимости от результата тестирования в строке 8 процедура рекурсивно вызывает сама себя либо в строке 9 (для чЕВ-дерева с размером универсума ф'й), либо в строке 11 (для чЕВ-дерева с раз- 588 Часть К Слалсные структуры данныл мерам универсума ле/ии). В любом случае выполняется один рекурсивный вызов для чЕВ-дерева с размером универсума не более ~/й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
