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