172
правки
Изменения
→Insert
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
=== Insert insert ===Операция <tex>\mathrm{Insertinsert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.
Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k.x</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k.x</tex>.
* Реализация №1
# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{Splitsplit}(T, k.x) \to \{T_1, T_2\}</tex>.# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{Mergemerge}(T_1, k) \to T_1</tex>.# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{Mergemerge}(T_1, T_2) \to T</tex>.
* Реализация №2
# Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>.
# Теперь вызываем <tex>\mathrm{Splitsplit}(T, k.x) \to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом)
# Полученные <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.
# Полученное дерево ставим на место элемента, найденного в первом пункте.
В первой реализации два раза используется <tex>\mathrm{Mergemerge}</tex>, а во второй реализации слияние вообще не используется.
=== Remove ===
