1302
правки
Изменения
→cascadingCut
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> x.mark == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае применяем операцию <tex>cut</tex> для текущей вершины и запускаем каскадное вырезание от родителя.
'''Пример'''
Рисунок иллюстрирует пример каскадного вырезания:
* Изначально, куча состояла из 3 фибоначчиевых деревьев. У вершины с ключом 24 отсутствует 1 ребенок.
* Уменьшаем ключ 26 до 5 и делаем операцию <tex>cut</tex> этого дерева. Получаем кучу с 4 деревьями и новым минимумом. Но у вершины с ключом 24 был удален второй ребенок, поэтому запускам операцию <tex>cascadingCut</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.
* У вершины с ключом 7 удален лишь один ребенок, поэтому операция <tex>cascadingCut</tex> от нее не запускается. В итоге, получаем кучу, состоящую из 5 фибоначчиевых деревьев.
==== Время работы ====
Докажем, что амортизированное время работы операции <tex>decreaseKey</tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
Иначе, добавляем к помеченной вершине родителя еще 2 монеты. В итоге, в родительском узле становится 4 монеты, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.
=== delete ===
