Изменения

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

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

# Распилим Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split}(T, k.x) \to \{T_1, T_2\}</tex>.# Теперь отделяем от первого дерева элемент <tex>x</tex>, опять таки распиливая разбивая по ключу <tex>x</tex>, то есть <tex>\mathrm{split}(T_1, k.x- \varepsilon) \to \{T_1, T_3\}</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>.