116
правок
Изменения
→Операция Relink
#* Если <tex>x</tex> {{---}} крайний правый сын <tex>p(x)</tex>, то на предыдущем шаге мы вставили его в список детей <tex>p(p(x))</tex> сразу после <tex>p(x)</tex>, следовательно {{---}} порядок обхода вершин из <tex> p(p(x)) </tex> в глубину не изменился. Значит, нам не нужно менять <tex> \mathrm {DFS_{LIST}} </tex>.
#* В противном случае нам нужно поместить участок <tex> \mathrm {DFS_{LIST}} </tex>, соответствующий поддереву <tex>x</tex>, перед <tex>p(x) </tex>. Этот участок {{---}} полуинтервал <tex>[x, l)</tex>, где <tex>l</tex> {{---}} сосед <tex>x</tex> справа. Вырежем его и вставим перед <tex>p(x) </tex>.
# Если после этого у <tex>p(x)</tex> осталось менее 3 детей, проделаем шаги 1 и 2 и с ними тоже.
# Если после этого <tex> p(x) </tex> стал листом, присвоим <tex> rank(p(x)) := 0 </tex> и удалим <tex> p(x) </tex> из <tex>\mathrm{NL_{LIST}}</tex> корня дерева.
# Если после этого <tex>\mathrm{NL_{LIST}}</tex> корня стал пустым(это значит, что дерево стало сокращенным), присвоим <tex> rank(root) := 1 </tex>
Очевидно, что <tex>\mathrm{Relink} </tex> выполняется за <tex>O(1)</tex>
