Изменения

Перейти к: навигация, поиск

Декартово дерево

14 байт убрано, 18:41, 11 апреля 2012
Insert
Операция <tex>\mathrm{Insert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.
==== * Реализация №1 ====
# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{Split}(T, k.x) \to \{T_1, T_2\}</tex>.
# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{Merge}(T_1, k) \to T_1</tex>.
# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{Merge}(T_1, T_2) \to T</tex>.
==== * Реализация №2 ====
# Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>.
# Теперь вызываем <tex>\mathrm{Split }(T, k.x) \to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом)

Навигация