333
правки
Изменения
Нет описания правки
|neat = 1
|definition =
'''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> - дерево, состоящее из одного узла высоты <tex>0</tex>, то есть состоит из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.
}}
Биномиальное дерево <tex>B_k</tex> с n вершинами:
*имеет <tex>2^k</tex> узлов;
*имеет высоту <tex>k</tex>;
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
*имеет корень степени <tex>k</tex>; степерь всех остальных вершин меньше степени корня биномиального дерева;
*максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\log(n)</tex>.
{{Определение
|definition=
'''Биномиальная пирамида ([[Двоичная куча|куча]]) <tex>H</tex>''' {{---}} представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам '''биномиальных пирамид'''.*Каждое биномиальное дерево в Н <tex>H</tex> подчиняется свойству '''неубывающей пирамиды''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей пирамиды дерево).*Для любого неотрицательного целого <tex>k </tex> найдется не более одного биномиального дерева Н<tex>H</tex>, чей корень имеет степень K<tex>k</tex>.}}
==== Представление биномиальных куч ====
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:
*''<tex>key'' </tex> {{---}} ключ (вес) элемента;*''<tex>parent'' </tex> {{---}} указатель на родителя узла;*''<tex>child'' </tex> {{---}} указатель на левого ребенка узла;*''<tex>sibling'' </tex> {{---}} указатель на правого брата узла;*''<tex>degree'' </tex> {{---}} степень узла (количество дочерних узлов данного узла).
Корни деревьев, их которых состоит пирамида, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в неубывающем порядке.
