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