Алгоритмы - построение и анализ (1021735), страница 110
Текст из файла (страница 110)
19.!. В частности, операция (Ъ!он требует только О (!8п) времени для объединения двух биномиальных пирамид с общим количеством и элементов. В главе 20 мы познакомимся с пирамидами Фибоначчи, у юторых для выполнения ряда операций нужно еще меньше времени (однаю в табл. 19.1 показано амортизированное время выполнения операций, а не время выполнения операции в наихудшем случае). В этой главе мы не рассматриваем вопросы выделения памяти для узлов перед вставкой и освобождения памяти после их удаления, полагая, что за это отвечает код, вызывающий процедуры для работы с пирамидами. Все три указанных вида пирамид не могут обеспечить эффективную реализацию поиска элемента с заданным ключом (операция Зелнсн), поэтому такие операции, как Рескелзе Кеу и 1)еьете в качестве параметра получают указатель на узел, а не значение его ключа.
Как говорилось при рассмотрении очередей с приоритетами в разделе 6.5, когда мы используем сливаемые пирамиды в приложении, мы часто храним в каждом элементе пирамиды дескриптор соответствующего объекта приложения, так же как и каждый объект приложения Глава 19. Бнномиальные пирамиды 539 хранит дескриптор соответствующего элемента пирамиды. Точная природа этих дескрипторов зависит от приложения и его реализации. В разделе 19.1 определяются биномиальные деревья и пирамиды, а также частично рассмотрен вопрос их реализации.
В разделе 19.2 показано, каким образом можно реализовать операции над биномиальными пирамидами, время работы юторых будет соответствовать приведенному в табл. 19.1. 19.1 Биномиальные деревья и биномиальные пирамиды Биномиальная пирамида представляет собой коллекцию биномиальных деревьев, так что данный раздел начинается с определения биномиальных деревьев и доказательства некоторых ключевых свойств. Затем мы определим биномиальные пирамиды и познаюмимся с их возможным представлением. 19.1.1 Биномиальные деревья Бияомиальиое дерево (Ь1пош(а! 1гее) Вь представляет собой рекурсивно определенное упорядоченное дерево (см.
раздел Б.5.2). Как показано на рис. 19.1а, биномиальное дерево Во состоит из одного узла. Биномиальное дерево Вь состоит из двух биномиальных деревьев Вь м связамоьюх вместе: корень одного из них является крайним левым дочерним узлом корня второго дерева. На рис. 19.1б показаны биномиальные деревья от Во до В4. Некоторые свойства биномиальных деревьев приводятся в следующей лемме. Лемма 19.1 (Свойства биномиальных деревьев). Биномиальное дерево Вя 1. имеет 2" узлов; 2. имеет высоту к; 3.
имеет ровно (",.) узлов на глубине(= 0,1,...,к; 4. имеет корень степени к; степень всех остальных вершин меньше степени корня биномиального дерева. Кроме того, если дочерние узлы юрия пронумеровать слева направо числами й — 1, й — 2,..., О, то 1-й дочерний узел корня является корнем биномиального дерева В;. Доказательство. Доказательство выполняется по индукции по )с. Базой индукции является биномиальное дерево Во, для которого тривиальна проверка выполнения свойств, перечисленных в лемме. Пусть перечисленные свойства выполняются для биномиального дерева Вь з. 1. Биномиальное дерево Вь состоит из двух юлий Вь м поэтому Вь содержит 2" 1+ 2" 1 = 2" узлов. Часть Ч. Сложные структуры данных 540 геккх 1 3 Рис.
19.1. Рекурсивное определение бииомиального дерева, примеры биномиальиых деревьев и альтернативное предсгавление биномиальиых деревьев 2. Из способа, которым выполняется связывание двух копий Вя 1 в одно биномиальное дерево Вы следует, что глубина биномиального дерева Ва на единицу больше максимальной глубины биномиального дерева Вь и Таким образом, в соответствии с гипотезой индукции максимальная глубина дерева Вь равна (Й вЂ” 1) + 1 = Й. 3.
Пусть Р (1г, 1) — количество узлов на глубине 1 у биномиального дерева Вь Поскольку Вь состоит из двух связанных копий Вь ы узел биномиального дерева Вь 1 на глубине 1 появляется один раз на глубине 1 в биномиальном дереве Вы и второй — на глубине 1+ 1. Другими словами, количество узлов на глубине 1 в биномиальном дереве Вь равно количеству узлов на глубине 1 в биномиальном дереве Вь г плюс количество узлов на глубине 1 — 1 в Вь и Таким образом, Глава 19. Биномиальные пирамиды 541 (При выводе использован результат упражнения В.1-7.) 4. Единственным узлом в биномиальном дереве Вь со степенью, превышающей степень в Вь м является корень, который имеет на один дочерний узел больше, чем в биномиальном дереве Вь н Поскольку корень биномиального дерева Вь 1 имеет степень Ь вЂ” 1, корень Вь имеет степень Ь.
Теперь, в соответствии с гипотезой индукции, как показано на рис. 19.1в, дочерними узлами корня Вь 1 являются корни биномиальных деревьев Вь з, Вь з,..., Во. Таким образом, когда выполняется привязка еще одного биномиального дерева Вь м дочерними узлами корня создаваемого дерева становятся кони биномиальных деревьев Вь ы Вь з,..., Вс. ° Следствие 19.2. Максимальная степень произвольного узла в биномиальном де- реве с и узлами равна 1к и. Доказательство. Доказательство следует из свойств 1 и 4 леммы 19.1.
Термин "биномиальное дерево" происходит из свойства 3 леммы 19.1, поскольку члены (~) представляют собой биномиальные коэффициенты. В упражнении 19.1-3 приводится еще одно обоснование этого термина. 19.1.2 Биномиальные пирамиды Бинвмиальнал пирамида (Ь(полна! Ьеар) Н представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам бинамиальных пирамид. 1. Каждое биномиальное дерево в Н подчиняется свойству неубывающей пирамиды (ппп-беар ргорег1у): ключ узла не меньше ключа его родительского узла.
Мы говорим, что такие деревья являются упорядоченными в соответствии со свойством неубывающей пирамиды (ш1п-беар-оп1егеб). 2. Для любого неотрицательного целого /с имеется не более одного биномиального дерева Н, чей корень имеет степен~с. Первое свойство говорит нам о том, что корень дерева, упорядоченного в соответствии со свойством неубывающей пирамиды, содержит наименьший ключ в дереве. Из второго свойства следует, что биномиальная пирамида Н, содержащая п узлов, состоит не более чем из ~1б и)' + 1 биномиальных деревьев.
Чтобы понять, почему это так, заметим, что бинарное представление числа и имеет ~15 и)' + 1 битов, скажем, (Ь11я„), Ьр „) м..., Ьс), так что и = 2 ', с" Ь;2 . В соответствии 11я ь) 1 со свойством 1 леммы 19.1, биномиальное дерево В; входит в состав Н тогда Часть У. Сложные структуры данных 542 ыаа (70- --м Оо7.— - — ---~ 1 г,н — -- — — — — — — --з ~я", '.13 ! !117 (П7) !И) ,77 б, 'ь'ы !и! — — ~ ~~' Рис.
19.2. Бнномнальная пирамида с 13 узлами и только тогда, когда бнт Ь; = 1. Следовательно, биномиальная пирамида Н содержит не более [!я п] + 1 биномиальных деревьев. На рис. 19.2а показана биномиальная пирамида с 13 узлами. Бинарное представление числа 13 имеет вид (1101), и биномиальная пирамида Н состоит ю биномиальных деревьев Во, Вз и Вз, которые содержат, соответственно, 1, 4 и 3 узлов, причем ключ каждого из узлов не превышает ключ родительского узла Представление бииомиальиых пирамид Как показано на рис. 19.26, каждое биномиальное дерево в биномиальной пирамиде хранится в представлении с левым дочерним и правым сестринским узлами (которое рассматривалось в разделе 10.4).
Каждый узел имеет поле Йеу и содержит сопутствующую информацию, необходимую для работы приложения. Кроме того, каждый узел содержит указатель р [х] на родительский узел, указатель сЬгЫ [х] на крайний левый дочерний узел и указатель я61тд [х] на правый сестринский по отношению к х узел. Если х — корневой узел, то р [х] = нй.. Если узел х не имеет дочерних узлов, то сЫН [х] = 7чп., а если х — самый правый Глава 19. Биномиальные пирамиды дочерний узел своего родителя, то в(И(пд [х] = мп..
Каждый узел х, кроме того, содержит поле»(едгее [х), в котором хранится количество дочерних узлов х. Как видно из рис. 19.2, корни биномиальных деревьев внутри биномиальиой пирамиды организованы в виде связанного списка, который мы будем называть слиском корней (гоог 1йт). При проходе по списку степени корней находятся в строго возрастающем порядке. В соответствии со вторым свойством биномиальных пирамид, в биномиальной пирамиде с п узлами степени корней представляют собой подмножество множества (О, 1,..., ~1бг»)). Поле вййпд имеет различный смысл для корней и для прочих узлов.
Если х — корень, то в(Итд [х] указывает на следующий корень в списке (как обычно, если х — последний корень в списке, то в1Ытд [х) = нп.). Обратиться к данной биномиальной пирамиде Н можно при помощи поля Аеас [Н], которое представляет собой указатель на первый корень в списке корней Н. Если биномиальная пирамида не содержит элементов, то Ьеа»1 [Н) = ьп . Упражнения 19.1-1. Предположим, что х — узел биномиального дерева в биномиальной пирамиде и что вййпд [х) Ф н|ь. Если х не является корнем, как соотносятся »(едгее [в(Итд[х)) и Иедгее [х]? А если х — корень биномиального дерева? 19.1-2.
Если х — некорневой узел биномиального дерева в биномиальной пирамиде, как соотносятся Йедгее [х] и Недгее [р[х])? 19.1-3. Предположим, что мы помечаем узлы биномиального дерева Вь последовательными двоичными числами при обходе в обратном порядке, как показано на рис. 19.3. Рассмотрим узел х на глубине г, помеченный числом 1, и пусть д = к — 1. Покажите, что в двоичном представлении х содержится д единиц. Сколько всего имеется 1»-строк, содержащих в точности д единиц? Покажите, что степень х равна количеству единиц справа от крайнего правого нуля в двоичном представлении 1.
фШ! ~0011; (Й01'~ »0П0 И01 ~,ПИ0) 900) (000ьз (к10 ', 00КО т,и00,, (00Ю! Рис. 19З. Биномнвльное дерево В» с узлами, помеченными двоичными числами при обходе в обратном порядке Часть Ч. Сложные структуры данньа 544 19.2 Операции над биномиальными пирамидами В этом разделе мы покажем, как выполнить операции над биномиальными пирамидами за время, приведенное в табл.
19.1. Мы покажем только верхиис границы; поиск нижних границ остается в качестве упражнения 19.2-10. Создание новой биномиальной пирамиды Для создания пустой биномиальной пирамиды процедура МАкн Впчом1Аь НеАР просто выделяет память и возвращает объект Н, где ЬеаИ [Н] = 1чп.. Вреич работы этой процедуры составляет 9 (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
