333
правки
Изменения
→Биномиальное дерево
*имеет корень степени <tex>k</tex>; степень всех остальных вершин меньше степени корня биномиального дерева;
Так как с увеличением порядка дерева мы подвешиваем к текущему корню ровно один корень другого дерева, то степень корня с увеличением порядка на 1 также увеличивается на 1. То дерево порядка <tex>k</tex> имеет корень степени <tex>k</tex>. И т.к. при таком увеличении порядка в полученном дереве лишь степень корня возросла, то доказываемый инвариант, т.е. степень корня больше степени остальных вершин, не будет нарушаться.
*максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\log(n)</tex>.
