Изменения
Новая страница: «= Фибоначчиевы деревья = {{Определение |definition= '''Фибоначчиево дерево''' - биномиальное дерево…»
= Фибоначчиевы деревья =
{{Определение
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
}}
{{Лемма
|statement=
Фибоначчиево дерево ранга <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
|proof=
Для рангов 0 и 1 соответствующие деревья содержат 1 вершину, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.
Рассмотрим дерево ранга <tex> k </tex>
Оно в худшем случае (удален ребенок ранка <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.
Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}
Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то высота фибоначчиева дерева есть <tex> O(logN) </tex>.
Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).
Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>
Также в любой вершине хранятся поля <tex> degree[x], \, mark[x] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.
= Фибоначчиевы кучи =
{{Определение
|definition=
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}
Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list).
Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.
Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью амортизационного анализа.
= Операции =
== Merge ==
{{Определение
|definition=
'''Фибоначчиево дерево''' - биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
}}
{{Лемма
|statement=
Фибоначчиево дерево ранга <tex> k </tex> содержит не менее <tex> F_k </tex> (<tex> k </tex> число Фибоначчи) вершин
|proof=
Для рангов 0 и 1 соответствующие деревья содержат 1 вершину, <tex> F_0 \ge 1, F_1 \ge 1 </tex>.
Рассмотрим дерево ранга <tex> k </tex>
Оно в худшем случае (удален ребенок ранка <tex> k - 1 </tex>) содержит <tex> 1 + F_1 + F_2 + ... + F_{k-2} </tex> вершин.
Эта сумма, в свою очередь, равна <tex> F_k </tex>
}}
Поскольку <tex> F_k = \Omega(\varphi^k) </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 </tex>, то высота фибоначчиева дерева есть <tex> O(logN) </tex>.
Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<tex> child[x] </tex>).
Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за <tex> O(1) </tex>
Также в любой вершине хранятся поля <tex> degree[x], \, mark[x] </tex>: степень вершины(число ее детей) и пометка о том, потеряла ли вершина <tex> x </tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.
= Фибоначчиевы кучи =
{{Определение
|definition=
'''Фибоначчиева куча''' - набор фибоначчиевых деревьев.
}}
Корни фибоначчиевых деревьев, составляющих фибоначчиеву кучу, также объединены в двусвязный циклический список(корневой список, root list).
Доступ к куче осуществляется с помощью указателя <tex> min[H] </tex>, указывающего на минимальную вершину в куче.
Доказательство времени работы для всех операций с фибоначчиевыми кучами проводим с помощью амортизационного анализа.
= Операции =
== Merge ==
