333
правки
Изменения
Нет описания правки
[[Файл:binHeapExample.png|thumb|325px|Пример биномиального дерева <tex>B_0, B_2, B_3</tex>]]
'''Свойства биномиальных деревьев(с доказательством). '''
Биномиальное дерево <tex>B_k</tex> с n вершинами:
*имеет <tex>2^k</tex> узлов;
В силу того, что с увеличением порядка дерева на <tex>1</tex> количество узлов увеличивается вдвое, а изначально дерево имеет <tex>2^0 = 1</tex> узел, то при любом <tex>k</tex>, дерево порядка <tex> k</tex> имеет <tex>2^k</tex> узлов.
*имеет высоту <tex>k</tex>;
В силу того, что с увеличением порядка дерева на <tex>1</tex>, мы подвешиваем к текущему дереву дерево того же порядка, то высота получившегося в результате слияния дерева увеличивается на <tex>1</tex>. Изначально имеем высоту <tex>2^0 = 1</tex> узел, то при любом <tex>k</tex>, дерево порядка <tex> k</tex> имеет высоту <tex>k</tex>.
*имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
*имеет корень степени <tex>k</tex>; степерь всех остальных вершин меньше степени корня биномиального дерева;
