172
правки
Изменения
→Remove
В первой реализации два раза используется <tex>\mathrm{merge}</tex>, а во второй реализации слияние вообще не используется.
=== Remove remove ===Операция <tex>\mathrm{Removeremove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.
* Реализация №1
# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{Split split }(T, k.x) \to \{T_1, T_2\}</tex>.# Теперь отделяем от первого дерева элемент <tex>x</tex>, опять таки разбивая по ключу <tex>x</tex>, то есть <tex>\mathrm{Split split }(T_1, k.x - \varepsilon) \to \{T_1, T_3\}</tex>.# Сливаем первое дерево со вторым, то есть <tex>\mathrm{Merge merge }(T_1, T_2) \to T</tex>.
* Реализация №2
# Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент.
# Найдя элемент, вызываем <tex>\mathrm{Mergemerge}</tex> его левого и правого сыновей# Результат процедуры <tex>\mathrm{Mergemerge}</tex> ставим на место удаляемого элемента.
В первой реализации два раза используется <tex>\mathrm{Splitsplit}</tex>, а во второй реализации разрезание вообще не используется.
== Построение декартова дерева ==
