333
правки
Изменения
→Свойства биномиальных деревьев
{{Утверждение
|statement=Биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет ровно <texdpi = "165"> \displaystyle k\choose i</tex> узлов на высоте <tex>i</tex>;
|proof=
Докажем по индукции:
База <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> всего узлов <texdpi = "165">\displaystyle {k\choose i} </tex> + <tex dpi = "165">{k\choose {i - 1}}</tex>, так как от подвешенного дерева в дерево порядка <tex>k+1</tex> нам пришли узлы глубины <tex>i-1</tex>. То для <tex>i</tex>-го уровня дерева <tex>B_{k+1}</tex> количество узлов <texdpi = "165">\displaystyle {k\choose i} </tex> + <tex dpi = "165">{k\choose {i - 1}} </tex> = <tex dpi ="160">{{k + 1}\choose i} </tex>. Переход доказан, то биномиальное дерево <tex>B_k</tex> с <tex>n</tex> вершинами имеет ровно <texdpi = "165"> \displaystyle {k\choose i}</tex> узлов на высоте <tex>i</tex>.
}}
