166
правок
Изменения
→Remove
Операция <tex>\mathrm{Remove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.
# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{Split }(T, k.x) \to \{T_1, T_2\}</tex>.
# Сливаем первое дерево со вторым, то есть <tex>\mathrm{Merge }(T_1, T_2) \to T</tex>.
# Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент.
# Найдя элемент, вызываем <tex>Merge</tex> его левого и правого сыновей, и возвращаемое ею # Возвращаемое значение ставим на место удаляемого элемента, то есть функции <tex>\mathrm{Merge }(T.l, T.t) \to T</tex>ставим на место удаляемого элемента.
== Высота декартового дерева ==
