Структуры данных и модели вычислений

         

Свойства биномиальных деревьев


  • Дерево состоит из корня с присоединенными к нему корнями поддеревьев в указанном порядке.
  • Дерево имеет высоту .
  • Дерево имеет ровно узлов.
  • В дереве на глубине имеется ровно узлов.
  • В дереве корень имеет степень , остальные узлы имеют меньшую степень.
  • Для каждого натурального числа n существует биномиальный лес, в котором количество узлов равно .
  • Максимальная степень вершины в биномиальном лесе с

    узлами равна .

  • Биномиальный лес содержит не более

    биномиальных поддеревьев.

Чтобы убедиться в существовании биномиального леса из узлов, представим в двоичной системе счисления (разложим по степеням двойки) , где . Для каждого , такого, что , в искомый лес включаем дерево .

Биномиальная куча — это набор биномиальных деревьев, узлам которых приписаны элементы взвешенного множества в соответствии с кучеобразным порядком, при котором вес элемента, приписанного узлу, не превосходит весов элементов, приписанных его потомкам.

Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей

где — ключ (вес) элемента, приписанного узлу, — родитель узла,

— левый ребенок узла, — правый брат узла, — степень узла.

Доступ к куче осуществляется ссылкой на самое левое поддерево. Корни деревьев, из которых составлена куча, оказываются организованными с помощью поля в так называемый корневой односвязный список.

Поиск элемента с минимальным ключом. Поскольку искомый элемент находится в корне одного из деревьев кучи, элемент с минимальным ключом находится путем просмотра корневого списка за время .

Слияние двух очередей. Две очереди и объединяются в одну очередь следующим образом. Последовательно выбираются деревья из исходных очередей в порядке возрастания их высот и вставляются в результирующую очередь , вначале пустую.

Если дерево очередной высоты присутствует лишь в одной из исходных очередей, то перемещаем его в результирующую очередь. Если оно присутствует в одной из исходных очередей и уже есть в результирующей очереди, то объединяем эти деревья в одно , которое вставляем в . Если присутствует во всех трех очередях, то сливаем два из них в

и вставляем в , а третье дерево просто перемещаем в . Трудоемкость — .

Вставка нового элемента. Создается одноэлементная очередь из вставляемого элемента, которая объединяется с исходной очередью. Трудоемкость — .

Удаление минимального элемента. Сначала в исходной куче

производится поиск дерева , имеющего корень с минимальным ключом. Найденное дерево удаляется из , его прикорневые поддеревья включаются в новую очередь , которая объединяется с исходной очередью . Трудоемкость — .

Уменьшение ключа. Осуществляется с помощью всплытия. Трудоемкость — .

Удаление элемента. Уменьшается ключ удаляемого элемента до , применяется всплытие, всплывший элемент удаляется как минимальный. Трудоемкость — .



Содержание  Назад  Вперед