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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
'''Биномиальное дерево <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>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.}}
 
'''Биномиальное дерево <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>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.}}
 
На рисунке ниже приведен пример биномиальных деревьев для <tex>k = 0, 1, 2, 4 </tex>.
 
На рисунке ниже приведен пример биномиальных деревьев для <tex>k = 0, 1, 2, 4 </tex>.
[[Файл:7_1.gif]]
+
[[Файл:http://www.intuit.ru/department/algorithms/dscm/7/7_1.gif]]

Версия 21:46, 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]k = 0, 1, 2, 4 [/math]. Файл:Http://www.intuit.ru/department/algorithms/dscm/7/7 1.gif