Изменения
Нет описания правки
== Операция remove ==
Операция <tex>remove(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.
===Реализация №1:===
<p>1) Разбиваем наше дерево по ключу, который мы хотим удалить, то есть <tex>split(T, T_1, T_2, x)</tex>.</p>
<p>2) Теперь отделяем от второго дерева элемент <tex>kx</tex>, опять таки разбивая по ключу <tex>kx</tex>, то есть <tex>split(T_2, T_2, T_3, x)</tex>.</p>
<p>3) Сливаем первое дерево со третьим, то есть <tex>merge(T, T_1, T_3)</tex>. </p>
===Реализация №2:===
Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), ища удаляемый элемент. Найдя элемент, мы просто вызываем <tex>merge</tex> от его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть <tex>merge(T,T.l,T.r)</tex>.
