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