403
правки
Изменения
→cascadingCut
==== cascadingCut ====
[[File:Cascading-cutКаскадное вырезание.png|thumb|600px500px|Каскадное вырезание]]
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> x.mark == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае вырезаем текущую вершину и запускаем каскадное вырезание от родителя.
Иначе, добавляем к помеченной вершине родителя еще 2 монеты. В итоге, в родительском узле становится 4 монеты, и мы можем рекурсивно продолжить данный процесс. Оценка доказана.
Рисунок иллюстрирует пример каскадного вырезания:
* Изначально, куча состояла из 3 фибоначчиевых деревьев. У вершины с ключом 24 отсутствует 1 ребенок.
* Уменьшаем ключ 26 до 5 и делаем операцию <tex>cut</tex> этого дерева. Получаем кучу с 4 деревьями и новым минимумом. Но у вершины с ключом 24 был удален второй ребенок, поэтому запускам операцию <tex>cascadingCut</tex> для этой вершины: вырезаем ее, помещаем в корневой список и помечаем ее родителя.
* У вершины с ключом 7 удален лишь один ребенок, поэтому операция <tex>cascadingCut</tex> от нее не запускается. В итоге, получаем кучу, состоящую из 5 фибоначчиевых деревьев.
=== delete ===
