22
правки
Изменения
Нет описания правки
|definition=
'''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> - дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.}}
Пример биномиального дерева для k = 0, 1, 2.
[[Файл:Example.jpg]]
*имеет высоту k;
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
*имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева. Кроме того, если дочерние узлы корня пронумеровать слева направо числами <tex> k - 1, k - 2, \dots, 0</tex>, то i-й дочерний узел корня является корнем биномиального дерева <tex>B_i</tex>;*максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\lg log(n)</tex>.
{{Определение
'''Биномиальная пирамида ([[Двоичная куча|куча]]) H''' {{---}} представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам '''биномиальных пирамид'''.
*Каждое биномиальное дерево в Н подчиняется свойству '''неубывающей пирамиды''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойсвом неубывающей прирамиды дерево).
* Для любого неотрицательного целого k найдется не более одного биномиального дерева Н, чей корень имеет степень K.}}
==== Представление биномиальных куч ====
|-
|Insert
|<tex>O(\lglog(n))</tex>
|-
|Minimum
|<tex>O(\lglog(n))</tex>
|-
|Extract_Min
