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