333
правки
Изменения
→Биномиальное дерево
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
Док-ем по индукции:
База <tex>k = 1</tex> - верно. Пусть для некоторого <tex>k </tex> условие верно, то док-ем, что для <tex>k + 1</tex> это также верно:
Рассмотрим <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>. То свойство доказано.
*имеет корень степени <tex>k</tex>; степерь всех остальных вершин меньше степени корня биномиального дерева;
*максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\log(n)</tex>.
