Изменения

Операция <tex>\mathrm{add}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.

# Разбиваем Распилим наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{split}(T, T_1, T_2, k.x)\to \{T_1, T_2\}</tex>.# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{merge}(T_1, T_1, k)\to T_1</tex>.#Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{merge}(T, T_1, T_2)\to T</tex>.

Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>. Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем <tex>\mathrm{split}(T, T_1, T_2, k.x)\to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.

Операция <tex>\mathrm{remove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.

# Разбиваем Распилим наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split}(T, k.x) \to \{T_1, T_2, x)\}</tex>.# Теперь отделяем от второго первого дерева элемент <tex>x</tex>, опять таки разбивая распиливая по ключу <tex>x</tex>, то есть <tex>\mathrm{split}(T_2T_1, T_2k.x) \to \{T_1, T_3, x)\}</tex>.# Сливаем первое дерево со третьимвтором, то есть <tex>\mathrm{merge}(T, T_1, T_3T_2)\to T</tex>.

Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент. Найдя элемент, мы просто вызываем <tex>merge</tex> его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть <tex>\mathrm{merge}(T,T.l,T.rt)\to T</tex>.