Структуры данных и модели вычислений
Свойства биномиальных деревьев
- Дерево состоит из корня с присоединенными к нему корнями поддеревьев в указанном порядке.
- Дерево имеет высоту .
- Дерево имеет ровно узлов.
- В дереве на глубине имеется ровно узлов.
- В дереве корень имеет степень , остальные узлы имеют меньшую степень.
- Для каждого натурального числа n существует биномиальный лес, в котором количество узлов равно .
- Максимальная степень вершины в биномиальном лесе с
узлами равна .
- Биномиальный лес содержит не более
биномиальных поддеревьев.
Чтобы убедиться в существовании биномиального леса из узлов, представим в двоичной системе счисления (разложим по степеням двойки) , где . Для каждого , такого, что , в искомый лес включаем дерево .
Биномиальная куча — это набор биномиальных деревьев, узлам которых приписаны элементы взвешенного множества в соответствии с кучеобразным порядком, при котором вес элемента, приписанного узлу, не превосходит весов элементов, приписанных его потомкам.
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей
где — ключ (вес) элемента, приписанного узлу, — родитель узла,
— левый ребенок узла, — правый брат узла, — степень узла.
Доступ к куче осуществляется ссылкой на самое левое поддерево. Корни деревьев, из которых составлена куча, оказываются организованными с помощью поля в так называемый корневой односвязный список.
Поиск элемента с минимальным ключом. Поскольку искомый элемент находится в корне одного из деревьев кучи, элемент с минимальным ключом находится путем просмотра корневого списка за время .
Слияние двух очередей. Две очереди и объединяются в одну очередь следующим образом. Последовательно выбираются деревья из исходных очередей в порядке возрастания их высот и вставляются в результирующую очередь , вначале пустую.
Если дерево очередной высоты присутствует лишь в одной из исходных очередей, то перемещаем его в результирующую очередь. Если оно присутствует в одной из исходных очередей и уже есть в результирующей очереди, то объединяем эти деревья в одно , которое вставляем в . Если присутствует во всех трех очередях, то сливаем два из них в
и вставляем в , а третье дерево просто перемещаем в . Трудоемкость — .
Вставка нового элемента. Создается одноэлементная очередь из вставляемого элемента, которая объединяется с исходной очередью. Трудоемкость — .
Удаление минимального элемента. Сначала в исходной куче
производится поиск дерева , имеющего корень с минимальным ключом. Найденное дерево удаляется из , его прикорневые поддеревья включаются в новую очередь , которая объединяется с исходной очередью . Трудоемкость — .
Уменьшение ключа. Осуществляется с помощью всплытия. Трудоемкость — .
Удаление элемента. Уменьшается ключ удаляемого элемента до , применяется всплытие, всплывший элемент удаляется как минимальный. Трудоемкость — .
