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