Биномиальная куча — различия между версиями
Строка 8: | Строка 8: | ||
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>; | *имеет ровно <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> | *имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева. Кроме того, если дочерние узлы корня пронумеровать слева направо числами <tex> k - 1, k - 2, \dots, 0</tex>, то i-й дочерний узел корня является корнем биномиального дерева <tex>B_i</tex> | ||
− | *максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\ | + | *максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\lg (n)</tex>. |
Версия 22:12, 13 марта 2011
Определение: |
Биномиальное дерево | — дерево, определяемое для каждого следующим образом: - дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; состоит из двух биномиальных деревьев , связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.
Свойства биномиальных деревьев. Биномиальное дерево
с n вершинами:- имеет узлов;
- имеет высоту k;
- имеет ровно узлов на высоте ;
- имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева. Кроме того, если дочерние узлы корня пронумеровать слева направо числами , то i-й дочерний узел корня является корнем биномиального дерева
- максимальная степень произвольного узла в биномиальном дереве с n узлами равна .