= Биномиальное дерево =
{{Определение
== Свойства биномиальных деревьев ==
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет <tex>2^k</tex> узлов
|proof=Так как в дереве порядка <tex>k+1</tex> вдвое больше узлов, чем в дереве порядка <tex>k</tex>, а в дереве нулевого порядка <tex>1 = 2^0</tex> узел, то дерево порядка <tex>k</tex> имеет <tex>2^k</tex> узлов.
}}
'''{{Утверждение 1'''. Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет <tex>2^k</tex> узлов; ''Доказательство'': Так как в дереве порядка <tex>k+1</tex> вдвое больше узлов, чем в дереве порядка <tex>k</tex>, а в дереве нулевого порядка <tex>1 |statement= 2^0</tex> узел, то дерево порядка <tex>k</tex> имеет <tex>2^k</tex> узлов. '''Утверждение 2'''. Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет высоту <tex>k</tex>; ''Доказательство'': |proof=Так как в дереве порядка <tex>k+1</tex> высота больше на <tex>1</tex> (так как мы подвешиваем к текущему дереву дерево того же порядка), чем в дереве порядка <tex>k</tex>, а в дереве нулевого порядка высота <tex>0</tex> , то дерево порядка <tex>k</tex> имеет высоту <tex>k</tex>. '''Утверждение 3'''. Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>; ''Доказательство'': }
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
|proof=
Докажем по индукции:
Рассмотрим <tex>i</tex> уровень дерева <tex>B_{k+1}</tex>. Дерево <tex>B_{k+1}</tex> было получено подвешиванием одного дерева порядка <tex>k</tex> к другому. Тогда на <tex>i</tex> уровне дерева <tex>B_{k+1}</tex> всего узлов <tex>{k\choose i} + {k\choose {i - 1}}</tex>, так как от подвешенного дерева в дерево порядка <tex>k+1</tex> нам пришли узлы глубины <tex>i-1</tex>. То для <tex>i</tex> уровня дерева <tex>B_{k+1}</tex> количество узлов <tex>{k\choose i} + {k\choose {i - 1}} ={{k + 1}\choose i} </tex>. То свойство доказано.
}}
'''{{Утверждение 4''': |statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет корень степени <tex>k</tex>; степень всех остальных вершин меньше степени корня биномиального дерева;|proof=Так как в дереве порядка <tex>k+1</tex> степень корня больше на <tex>1</tex>, чем в дереве порядка <tex>k</tex>, а в дереве нулевого порядка степень корня <tex>0</tex>, то дерево порядка <tex>k</tex> имеет корень степени <tex>k</tex>. И так как при таком увеличении порядка(при переходе от дерева порядка <tex>k</tex> к <tex>k+1</tex>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться.
Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет корень степени <tex>k</tex>; степень всех остальных вершин меньше степени корня биномиального дерева; ''Доказательство'': Так как в дереве порядка <tex>k+1</tex> степень корня больше на <tex>1</tex>, чем в дереве порядка <tex>k</tex>, а в дереве нулевого порядка степень корня <tex>0</tex>, то дерево порядка <tex>k</tex> имеет корень степени <tex>k</tex>. И так как при таком увеличении порядка(при переходе от дерева порядка <tex>k</tex> к <tex>k+1</tex>) в полученном дереве лишь степень корня возрастает, то доказываемый инвариант, то есть степень корня больше степени остальных вершин, не будет нарушаться. '''Утверждение 5'''. Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами максимальная степень произвольного узла в биномиальном дереве с <tex>n</tex> узлами равна <tex>\log(n)</tex>. ''Доказательство'': }}
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами максимальная степень произвольного узла в биномиальном дереве с <tex>n</tex> узлами равна <tex>\log(n)</tex>.
|proof=
Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Так как степень корня дерева порядка <tex>k</tex> равна <tex>k</tex>, а узлов в этом дереве <tex>n = 2^k</tex>, то прологарифмировав обе части получаем, что <tex>k=O(\log(n))</tex>, то степень произвольного узла не более <tex>\log(n)</tex>.
}}
= Биномиальная куча=
