Изменения

Док-ем Докажем по индукции:

База <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>. То свойство доказано.

Так как с увеличением порядка дерева мы подвешиваем к текущему корню ровно один корень другого дерева, то степень корня с увеличением порядка на 1 также увеличивается на 1. То дерево порядка <tex>k</tex> имеет корень степени <tex>k</tex>. И т.к. так как при таком увеличении порядка в полученном дереве лишь степень корня возросла, то доказываемый инвариант, т.е. то есть степень корня больше степени остальных вершин, не будет нарушаться.

Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Т.к. Так как степень корня дерева порядка <tex>k</tex> равна <tex>k</tex>, а узлов в этом дереве <tex>n = 2^k</tex>, то прологарифмировав обе части получаем, что <tex>k=O(\log(n))</tex>, то степень произвольного узла не более <tex>\log(n)</tex>.