Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 126
Текст из файла (страница 126)
Поиск в этом кластере крайней слева (справа) 1 дает позицию преемника (предшественника). Для удаления значения х положим 1 = (к/ь2и~. Установим А[х1 равным О, а затем установим еиттагу(1~ равным логическому ИЛИ битов в 1-м кластере. В каждой из описанных выше операций мы выполняем поиск не более чем в двух кластерах по Чеи бит, плюс в массиве зиелтлагу, так что каждая операция выполняется за время 0(к/и). На первый взгляд создается впечатление не прогресса, а регресса. Наложение бинарного дерева дает нам операции со временем выполнения 0(1яи), что асимптотически быстрее, чем время О(к/и). Однако применение дерева со степенью к/и оказывается ключевой идеей деревьев ван Эмде Боаса.
Мы продолжим путешествие по этому пути в следующем разделе. Упражнения голл Модифицируйте структуры данных из этого раздела таким образом, чтобы они поддерживали дублирующиеся ключи. гол.г Модифицируйте структуры данных из этого раздела таким образом, чтобы они поддерживали ключи со связанными сопутствующими данными. гол.з Заметьте, что при использовании описанных в этом разделе структур способ поиска преемника и предшественника значения х не зависит от того, находится ли х в данный момент в этом множестве. Покажите, как найти преемник х в бинарном дереве поиска, когда х в этом дереве отсутствует.
573 Гааеа гд деревья ван Эмде Боаса голл Предположим, что вместо дерева со степенью ь/й мы накладываем дерево со степенью и'/ь, где к > 1 — константа. Какой будет высота такого дерева и за какое время будет выполняться каждая из операций иад ним? 20.2. Рекурсивная структура В этом разделе мы модифицируем идею наложения дерева степени ~/й на битовый вектор.
В предыдущем разделе мы использовали структуру размером ~/й, каждый элемент которой указывал на другую структуру размером т/й. Теперь мы делаем структуру рекурсивной, уменьшая размер универсума на квадратный корень на каждом уровне рекурсии. Начиная с универсума размером и, мы делаем структуры хранящими ~/й = и1/з элементов, которые хранят структуры по и1/4 элементов, которые хранят структуры по и'/а элементов, и так далее до базового размера 2. Для простоты в этом разделе мы считаем, что и = 2~ для некоторого целого числа 14, так что и, и'/з, и'/4,...
являются целыми числами. На практике это ограничение является достаточно жестким, ограничивающим нас значениями и из последовательности 2, 4, 16, 256, 65536,.... Из следующего раздела вы узнаете, как ослабить это предположение и считать только, что и = 2" для некоторого целого числа (с. Поскольку рассматриваемая в этом разделе структура представляет собой только предвестник настоящего дерева ван Эмде Боаса, отнесемся терпимо к этому ограничению, призванному способствовать облегчению понимания. Вспомним, что наша цель — получить время работы операций, равное 0(1я1яи), и подумаем, как можно ее достичь. В конце раздела 4.3 мы видели, что путем замены переменных можно показать, что рекуррентное соотношение Т(п) = 2Т ( (~/и) ) + 1к и (20.1) имеет решение Т(п) = О(16п1616п). Рассмотрим похожее, ио более простое рекуррентное соотношение Т(и) = Т(ъ/и) + 0(1) . (20.2) Если воспользоваться тем же методом замены переменных, можно показать, что рекуррентное соотношение (20.2) имеет решение Т(и) = 0(1616и).
Пусть гп = 1к и, так что и = 2'", и имеем Т(2 ) = Т(2~/~) + О(1) . Теперь переименуем Я(т) = Т(2 ), что даст новое рекуррентное соотношение Я(т) = Я(та/2) + О(1) . 574 Часто и Сложные структуры даккыл Согласно случаю 2 основного метода это рекуррентное соотношение имеет решение Б(т) = О(1кт). Вернемся от Я(т) к Т(и), получая Т(и) = Т(2 ) = Я(т) = 0(1кт) = О(1к!ки). Рекуррентное соотношение (20.2) будет направлять наши поиски структуры данных. Мы разработаем рекурсивную структуру данных, которая на каждом уровне рекурсии будет выполнять уменьшение на множитель т/й. Когда операция обходит эту структуру данных, на каждый уровень, прежде чем опуститься на уровень ниже, она затрачивает константное время.
Время выполнения такой операции характеризует рекуррентное соотношение (20.2). Вот еще один способ представить, как в решении рекуррентного соотношения (20.2) получается 1к1ки. Рассматривая размер универсума на каждом уровне рекурсивной структуры данных, мы получаем последовательность 4/4 и4/а, Есш4 рассмотрет какое жшнчество битов требуется для хранения размера универсума на каждом уровне, мы получим 1ки на верхнем уровне„ и каждый последующий уровень будет требовать половину битов предыдущего.
В общем случае, если мы начнем с 6 бит и будем уменьшать это количество на каждом уровне в два раза, то после 1к 6 уровней мы придем к одному биту. Поскольку 6 = !ли, после 1к 1ки уровней получаем размер универсума, равный 2. Вернемся к структуре данных на рис. 20.2. Заданное значение х располагается в кластере с номером (х/т/й). Если рассматривать х как 1ки-битовое бинарное целое число, то номер кластера, (х/з/й), определяется (1к и)/2 старшими битами числа х. В своем кластере х находится в позиции х шое) з/й, которая определяется (!я и)/2 младшими битами числа х.
Позже нам потребуется такая индексация, так что определим некоторые функции, которые облегчат нашу работу: Ь)яЬ(х) = (х/з/й), 1оло(х) = х шос) к/й, ш4)ех(х, у) = хт/й+ у . Функция Ь(кЬ(х) дает (1к и)/2 старших битов числа х, возвращая номер кластера х. Функция 1оло(х) дает (1я и)/2 младших битов числа х и указывает позицию х в его кластере. Функция 1пе(ех(х, у) строит номер элемента из значений х и у, рассматривая х как (1ки)/2 старших битов номера элемента, а у — как (1я и)/2 младших битов. Справедливо тождество х = 1пс(ех(Ь(кЬ(х), 1оло(х)). Значение и, используемое каждой из этих функций, всегда представляет собой размер универсума структуры данных, в которой вызывается данная функция и которое изменяется при переходе к рекурсивной структуре.
20.2.1. Протоструктуры ван Эмде Бааса От рекуррентного соотношения (20.2) перейдем к построению рекурсивной структуры данных, поддерживающей указанные операции. Хотя эта структура данных и не позволяет достичь нашей цели — времени работы 0(1к1ки) — для некоторых операций, она служит основой для структуры дерева ван Эмде Боаса, с которой мы встретимся в разделе 20.3.
улове 20. Де)оееья еон Эмое Бааса 575 ьвЬя) я ьяо ,„lй ртозо-оЕВ(,/и) струатур Рис. 20.3. информация в струкгуре ртосо-оеВ(н) нри и > 4. структура сонери версума и, указатель янтзнату на структуру ртозо-оЕВ(,/и) и массив с)нязет]0 .. указателей на ртосо-оЕВ( /н)-сзруктурм. нт размер унизуй — 1] нз з/й Если и = 2, то зто базовый размер, и она содержит массив А[0 ..
1] из двух битов. В противном случае и = 22 для некоторого целого числа )с > 1, так что и > 4. В дополнение к размеру универсума и структура данных рто1о-нЕВ(и) содержит следующие атрибуты, показанные на рис. 20.3: указатель аипзтпату на структуру рго1о-иЕВ(,/и); ° массив с(ил1ет[0 .. з/й — 1] из;/й указателей, каждый из которых указывает на ртого-иЕВ(.,/й) структуру. Элемент х, где 0 < х < и, рекурсивно хранится в кластере номер Ь)я)з(х), как элемент номер )озо(х) в пределах этого кластера. В двухуровненой структуре из предыдущего раздела каждый узел хранит массив размером з/й, каждый элемент которого содержит один бит. По индексу каждого элемента можно вычислить начальный индекс подмассива размером з/й, который резюмируется этим битом.
В протоструктуре вместо вычисления индексов используются явные указатели. Массив аитглату содержит резюмирующие биты, рекурснвно хранящиеся в протостру«туре, и массив с)иа1ег, содержащий з/й указателей. На рис. 20.4 показана (полностью развернутая) протоструктура ргого-нЕВ (16), представляющая множество (2, 3,4, 5, 7, 14, 15) . Если значение з находится в протострукгуре, на которую указывает виттату, то з-й кластер содержит некоторое значение из представленного множества. Как и в дереве с константной высотой, с)млеет[з] представляет значения от зз/й до (з + 1)з/й — 1, которые образуют з-й кластер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
