116
правок
Изменения
→Реализация
==== Операция Find ====
Реализуем собственно операцию <tex>\mathrm{Find(a)}</tex>:
# Пусть <tex>x</tex> {{---}} вершина дерева, ассоциированная с элементом <tex>a</tex>
# Пока <tex>p(x) \neq root</tex>, выполняем:
## <tex>Relink(x)</tex>
## <tex>x := t</tex>
=== Реализация операции Delete ===
Сначала разработаем процедуру удаления узла из дерева, у которого <tex>size(T) \leq 4</tex> {{---}} удаление из такого дерева даст нам сокращенное дерево. Назовем эту процедуру <tex>\mathrm{ReducedTreeDelete(a)} </tex>.
==== Операция ReducedTreeDelete ====
# Если дерево не сокращенное, сделаем его сокращенным, просто переподвесив все вершины к корню. Так как дерево маленькое {{---}} <tex>size(T) \leq 4</tex> {{---}} операция выполняется за <tex>O(1)</tex>
# Если <tex>a</tex> ассоциирован с листом, просто удалим этот лист.
# Иначе <tex>a</tex> ассоциирован с корнем: просто поменяем <tex>a</tex> местами с элементом из любого листа (любого сына корня) и удалим этот лист.
Теперь подумаем, как удалять элемент из полного дереве размера больше 4. После удаления дерево должно остаться полным. <br/>
Нам необходимо найти некоторый лист дерева, из которого мы удаляем элемент. Реализуем для этого процедуру <tex>\mathrm{FindLeaf(a)}</tex>.
==== Операция FindLeaf ====
# Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex>.
# Если <tex>x</tex> {{---}} лист, задача решена.
# Если <tex>x</tex> {{---}} корень дерева, то он является первым в <tex>\mathrm{DFS_{LIST}}</tex>. Но при обходе в глубину последняя пройденная вершина всегда является листом, а значит {{---}} вершина, идущая в <tex>\mathrm{DFS_{LIST}}</tex> перед корнем, является листом. Возвращаем ее.
# В противном случае:
#* Если <tex>x</tex> имеет брата справа {{---}} <tex>r</tex>, то перед тем как обойти <tex>r</tex> поиском в глубину, мы обошли самый правый лист поддерева <tex>x</tex>. Следовательно, нужный нам лист {{---}} <tex>\mathrm{DFS_{LIST}}[r].prev</tex>.
#* Иначе <tex>x</tex> имеет брата слева {{---}} <tex>l</tex>, и по аналогичным рассуждениям листом является <tex>\mathrm{DFS_{LIST}}[x].prev</tex>.
== Примечания ==
