Изменения

Перейти к: навигация, поиск

СНМ с операцией удаления за О(1)

43 байта добавлено, 23:35, 31 мая 2014
Нет описания правки
=== Реализация операции Find ===
В нашей реализации операции <tex>find</tex> вместо уже известного нам метода '''сжатия путей (path compressing)''' мы будем использовать '''разделение путей (path splitting)'''. Он заключается в том, чтобы при выполнении операции find перевешивать элемент, от которого мы вызвались, не сразу к корню, а к собственному "дедушке". Такой метод сокращения пути приводит к той же амотризационной оценке для функции <tex>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>, несмотря на то, что интуитивно кажется более медленным. Мы будем использовать именно разделение путей, потому что это серьезно упрощает поддержку списков и инвариантов.
 
== Примечания ==
<references />
116
правок

Навигация