Изменения
Нет описания правки
* <tex>\mathrm{Delete(x)}</tex> {{---}} удалить элемент x из содержащего его множества. Время: <tex>O(1)</tex>.
В дальнейшем мы будем использовать используются следующие понятия и обозначения:
* <tex>size(A)</tex> {{---}} размер множества <tex>A</tex> (количество элементов в нем).
=== Реализация операции Find ===
В нашей реализации операции <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>, несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.
==== Операция Relink ====
Реализуем процедуру <tex> \mathrm { Relink(x) } </tex> {{---}} переподвешивание элемента <tex>x</tex> к его "дедушке" с сохранением инвариантов и структуры списков.
Осталось рассмотреть другой случай {{---}} когда до и после выполнения <tex>\mathrm{Find} \; T_A</tex> было полным. Обозначим множество <tex>A</tex> после выполнения <tex>\mathrm{Find}</tex> как <tex>A'</tex>
Так как <tex>\mathrm{Find}</tex> изменяет <tex>T_A</tex> только посредством операции <tex>\mathrm{Relink}</tex>, достаточно доказать, что <tex>\mathrm{Relink}</tex> сохраняет '''инвариант 3'''.
==== Анализ операции Relink ====
=== Delete ===
Пусть для множества <tex>A</tex> '''инвариант 3 выполняется'''.
Если после выполнения <tex>\mathrm{Delete} \; T_A</tex> стало сокращенным, то '''инвариант 3''' сохранен по '''лемме 1'''.
<references />
== Источники информации ==* [http://www2.mta.ac.il/~amirben/downloadable/ufd.pdf A. Ben-Amram, S. Yoffe. A Simple And Efficient Union-Find-Delete Algorithm]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Система непересекающихся множеств ]]
