403
правки
Изменения
→cascadingCut
[[File:Каскадное вырезание.png|thumb|500px|Каскадное вырезание]]
Перед вызовом каскадного вырезания нам известно, что перед этим мы удалили ребенка у этой вершины. Если <tex> x.mark == false </tex>, то мы ставим эту пометку <tex> true </tex> и заканчиваем. В противном случае вырезаем текущую вершину применяем операцию <tex>cut</tex> для текущей вершины и запускаем каскадное вырезание от родителя.
Докажем, что амортизированное время работы операции <tex>decreaseKey</tex> есть <tex> O(1) </tex>. Поскольку в процедуре нет циклов, ее время работы определяется лишь количеством рекурсивных вызовов каскадного вырезания.
