Биномиальная куча — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
*имеет <tex>2^k</tex> узлов;
 
*имеет <tex>2^k</tex> узлов;
 
*имеет высоту k;
 
*имеет высоту k;
*имеет ровно <tex>\left ( {k}{i} \right )</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>.

Версия 22:09, 13 марта 2011

Определение:
Биномиальное дерево [math]B_k[/math] — дерево, определяемое для каждого [math]k = 0, 1, 2, \dots [/math] следующим образом: [math]B_0[/math] - дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; [math]B_k[/math] состоит из двух биномиальных деревьев [math]B_{k-1}[/math], связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.

Свойства биномиальных деревьев Биномиальное дерево [math]B_k[/math] с n вершинами:

  • имеет [math]2^k[/math] узлов;
  • имеет высоту k;
  • имеет ровно [math]{k\choose i}[/math] узлов на высоте [math]i = 0, 1, 2, \dots[/math];
  • имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева. Кроме того, если дочерние узлы корня пронумеровать слева направо числами [math] k - 1, k - 2, \dots, 0[/math], то i-й дочерний узел корня является корнем биномиального дерева [math]B_i[/math].