Изменения

В нашей реализации операции <tex>\mathrm {Find}</tex> вместо уже известного нам метода '''сжатия путей (path compressing)''' мы будем использовать '''разделение путей (path splitting)'''. Он заключается в том, чтобы при выполнении операции <tex>\mathrm {Find}</tex> перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функции <tex>\mathrm {Find}</tex><ref>[http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Union-Find-Tarjan.pdf|Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.]</ref>, несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.<br/>==== Операция Relink ====Реализуем процедуру <tex> \mathrm { Relink(x) } </tex> {{---}} переподвешивание элемента <tex>x</tex> к его "дедушке" с сохранением инвариантов и структуры списков.  # Удалим <tex> x </tex> из <tex> \mathrm{C_{LIST}} \; p(x)</tex> и вставим его в <tex> \mathrm{C_{LIST}} \; p(p(x))</tex> следующим образом:#* Если <tex>x</tex> имеет брата справа от себя, вставим его в <tex> \mathrm{C_{LIST}} \; p(p(x))</tex> сразу слева от <tex> p(x) </tex>#* Иначе (если <tex> x </tex> {{---}} крайний правый сын <tex>p(x)</tex>) {{---}} вставим <tex> x </tex> сразу справа от <tex> p(x) </tex># Обновим <tex> \mathrm {DFS_{LIST}} </tex> следующим образом:#* Если <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> стал листом, присвоим <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>