116
правок
Изменения
→Операция FindLeaf
#* Если <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>.
Итак, мы нашли некоторый лист дерева за <tex>O(1)</tex>. Теперь нам нужно просто уметь его удалять, но так, чтобы инварианты и структура списков сохранялись.
==== Операция DeleteLeaf ====
Пусть <tex>x</tex> {{---}} удаляемый лист.
# Извлекаем <tex>x</tex> из <tex>\mathrm{C_{LIST}} \; p(x) </tex> и из <tex>\mathrm{DFS_{LIST}}</tex>
# Удаляем узел <tex>x</tex>
Следующие 2 шага обеспечивают сохранение полноты дерева
# Если <tex>p(x) \neq root(T)</tex>, вызовем <tex>\mathrm{Relink}</tex> для 2 самых правых детей <tex>p(x)</tex>
# Иначе найдем среди детей <tex>p(x)</tex> узел, не являющийся листом (с помощью <tex>\mathrm{NL_{LIST}}</tex>), и вызовем <tex>\mathrm{Relink}</tex> для 3 его самых правых детей.
Так как операция <tex>\mathrm{Relink}</tex> сохраняет полноту дерева и выполняется за <tex>O(1)</tex>, <tex>\mathrm{DeleteLeaf}</tex>, очевидно, обладает теми же свойствами.
<br/>
Итак, соберем воедино операцию <tex>\mathrm{Delete(a)}</tex>:
==== Операция Delete ====
Пусть элемент <tex>a</tex> ассоциирован с вершиной <tex>x</tex>
# Если <tex>size(T) \leq 4</tex>, вызываем <tex>\mathrm{ReducedTreeDelete(a)}</tex>
# Иначе:
## <tex>l := \mathrm{FindLeaf(a)} </tex>
## Поменяем элементы в <tex>x</tex> и <tex>l</tex> местами.
## <tex>\mathrm{DeleteLeaf(l)}</tex>
== Примечания ==
