116
правок
Изменения
→Реализация операции Find
# Если после этого <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>
==== Операция Find ====
Реализуем собственно операцию <tex>Find(a)</tex>:
# Пусть <tex>x</tex> {{---}} вершина дерева, ассоциированная с элементом <tex>a</tex>
# Пока <tex>p(x) \neq root</tex>, выполняем:
## <tex>t := p(x)</tex>
## <tex>Relink(x)</tex>
## <tex>x := t</tex>
== Примечания ==
