Биномиальное дерево

► B0 — дерево, состоящее из одного узла высоты 0;

► Bk - дерево высоты k формируется из двух деревьев Bk-1 , при этом корень

одного из них становится потомком

корнядругого.

► Биномиальный лес — это набор биномиальных деревьев, в котором любые два дерева имеют разные высоты.

Свойства биномиальных деревьев

Дерево Bk состоит из корня с корнями поддеревьев Bk-1 , … B1 , B0 в указанном порядке.

►2. Дерево Bk имеет высоту k.

►3. Дерево Bk имеет ровно 2k узлов.

4. В дереве Bk на глубине I имеется ровно Cki узлов.

►5. В дереве Bk корень имеет степень k, остал. узлы имеют меньшую степень.

6.Длякаждого натурал. числа n сущ. биномиальный лес, в котором колич. узлов равно n.

►7. Максимальная степень вершины в биномиальном лесе с n узлами равна log2n.

►8. Биномиальный лес содержит не более |log2n| биномиальных поддеревьев

Биномиальная куча

[key, parent, child, sibling, degree]

key — ключ (вес) элемента, приписанного узлу, parent — родитель узла, child — левый ребенок

узла, sibling — правый брат узла, degree — степень узла

Фибоначчиева куча (англ. Fibonacci heap)

►время работы операций, не требующих удаления- равно O(1)

►удаление O(logn)

набор деревьев

► Каждое дерево в H подчиняется свойству неубывающей пирамид (min-heap property): ключ узла не меньше ключа его родительског узла.

► Каждый узел x в H содержит след. указатели и поля: ► key[x] — поле, в котором хранится ключ;

► parent[x] — указатель на родительский узел; ► child[x] — указ. на один из дочерних узлов; ► left[x] — указ. на левый сестринский узел;

► right[x] — указ. на правый сестринский узел;

►degree[x] — поле, в кот хранится кол. дочер. узлов;

► mark[x] —лог знач., кот указывает, были ли потери узлом x дочерних узлов, начиная с момента, когда x стал дочерним узлом какого-то другого узла.

►Дочерние узлы x объединены при помощи указателей left и right в один циклический дважды связанный список дочерних узлов (child list) x.

►Корни всех деревьев в H связаны при помощи указателей left и right в циклический дважды связанный список корней (root list).

►Обращение к H выполняется посредством указателя min[H] на корень дерева с

минимальным ключом. Этот узел называется

минимальным узлом (minimum node) H.