Биномиальная куча

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Биномиальное дерево [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]. Файл:7 1.gif