333
правки
Изменения
→Свойства биномиальных деревьев
Докажем по индукции:
База <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>. То свойство доказано.
