depth = глубина

Рис. 20.2 (а) Рекурсивное определение биномиального дерева Bk (треугольники - поддеревья с выделенным корнем), (б) Деревья Во-В$. Цифры указывают глубину вершин в дереве В4. (в) Другое представление дерева Bk

Лемма 20.1 (Свойства биномиальных деревьев). Дерево Bk

1.содержит 2к вершин;

2.имеет высоту к;

3.имеет Снк вершин глубины г;

4- имеет корень, являющийся вершиной степени к; все остальные вершины имеют меньшую степень; дети корня являются корнями поддеревьев Bk-i, Bk-2, • • •, В\, Во (слева направо).

Доказательство, проводится индукцией по к. Для Во всё очевидно. Пусть утверждение верно для Bk-i- Тогда:

1.Дерево Bk состоит из двух копий Bk-i и потому содержит 2k-i + 2k-i = 2к вершин

2.При соединении двух копий описанным способом высота увеличивается на 1.

3.Пусть D(k,i) - число вершин глубины г в дереве Bk- По построению дерева Bk (см. рис. 20.2а) имеет место равенство

D(k, г) = D(k -1,г) + D(k - 1, г - 1) = CJU + С[~ \ = С\.

(Мы воспользовались индуктивным предположением и упр. 6.1-7.)

4. По предположению индукции все вершины в -B-i имеют степень не больше к - 1, так что корень дерева Bj~ будет в нём единственной вершиной степени к. В правом из склеиваемых деревьев дети корня были вершинами деревьев 5fc 2, -Bfc-3j • • •, В\, Во, теперь к ним добавилось слева еще дерево Вк-\.□

Следствие 20.2. Максимальная степень вершины в биномиальном дереве с га вершинами равна lg га.

Доказательство. Используем утверждения 1 и 4 леммы 20.1. □

Название «биномиальное дерево» связано с утверждением 3 леммы 20.1 (число Снк называют биномиальным коэффициентом). См.

также упр. 20.1-3.

20.1.2. Биномиальные кучи

Биномиальная куча (binomial heap) - это набор Н биномиальных деревьев, в вершинах которых записаны ключи (числа) и, возможно, дополнительная информация. При этом должны быть выполнены такие свойства биномиальной кучи (binomial-heap properties):

1.Каждое дерево в Н упорядочено в смысле куч (is heap-ordered), т.е. ключ каждой вершины не меньше, чем ключ её родителя.

2.В Н нет двух биномиальных деревьев одного размера (с одинаковой степенью корня).

Первое свойство гарантирует, что корень каждого из деревьев имеет наименьший ключ среди его вершин.

Из второго свойства следует, что суммарное количество вершин в биномиальной куче Н однозначно определяет размеры входящих в неё деревьев. В самом деле, общее число вершин, равное га, есть сумма размеров отдельных деревьев, которые суть различные степени двойки, а такое представление единственно (двоичная система счисления). Отсюда вытекает также, что куча с га элементами состоит из не более чем [lg raj + 1 биномиальных деревьев.

На рис. 20.3а показана биномиальная куча if с 13 вершинами. В двоичной системе 13 записывается как 1101 (13 = 8 + 4+1), и Н состоит из биномиальных деревьев В3, В2 и Во (с количеством вершин 8, 4 и 1).

Представление биномиальных куч в программе

Как показано на рис. 20.36, каждое биномиальное дерево в биномиальной куче хранится в представлении «левый ребёнок, правый сосед» (см. разд. 11.4). Каждая вершина имеет поле key (ключ), а

Рис. 20.3 Биномиальная куча Н с п = 13 вершинами, (а) Куча состоит из биномиальных деревьев Во, Е>2 и Вз, имеющих соответственно 1, 4 и 8 вершин (всего 13 вершин). Ключ каждой вершины не меньше, чем ключ её родителя. Корни деревьев связаны в корневой список в порядке возрастания степени, (б) Представление кучи в программе. Каждое биномиальное дерево хранится в представлении «левый ребёнок, правый сосед», и в каждой вершине хранится её степень (degree).

также хранит дополнительную информацию. Кроме того, каждая вершина х хранит указатели р[х] (родитель), child[x] (самый левый из детей) и sibling[x] («следующий по старшинству брат»). Если х - корень, то р[х] = NIL; если х не имеет детей, то child[x] = NIL, а если х является самым правым ребёнком своего родителя, то sibling[x] = NIL. Каждая вершина х содержит также поле degree[x] в котором хранится степень (число детей) вершины х.

На рис. 20.3 показано также, что корни биномиальных деревьев, составляющих биномиальную кучу, связаны в список, называемый корневым списком (root list) в порядке возрастания степеней. Как мы видели, в куче с п вершинами степени корневых вершин образуют подмножество множества {0,1,..., lgra }.

Для построения корневого списка используется поле sibling: для корневой вершины оно указывает на следующий элемент корневого списка (и содержит NIL для последнего корня в корневом списке).