Изменения
Нет описания правки
[[file:split.png|thumb|200px|Операция split]]
Операция <tex>\mathrm{split}</tex>(''разрезать'') позволяет сделать следующее: разрезать декартово дерево <tex>T</tex> по ключу
<tex>x</tex> и получить два других декартовых дерева: <tex>T_1</tex> и <tex>T_2</tex>, причем в <tex>T_1</tex>
находятся все ключи дерева <tex>T</tex>, не большие <tex>x</tex>, а в <tex>T_2</tex> {{---}} большие <tex>x</tex>.
<tex>\mathrm{split}(T, x) \to \{T_1, T_2\}</tex>.
Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня.
[[file:merge.png|thumb|200px|Операция merge]]
Рассмотрим вторую замечательную операцию с декартовыми деревьями {{---}} <tex>\mathrm{merge}</tex>(''слить'').
С помощью этой операции можно починить всё, что предварительно было сломано с помощью операции <tex>\mathrm{split}</tex>слить два декартовых дерева в одно.А именноПричем, <tex>\mathrm{merge}</tex> принимает два дерева, причем все ключи в первом(''левом'') дереве должны быть меньше, чемключи во втором(''правом''), и создаёт новое . В результате получается дерево, в котором есть все ключи из первого и второго деревьев.
<tex>\mathrm{merge}(T_1, T_2) \to T</tex>
Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
Тогда, очевидно, у результирующего дерева <tex>T</tex> есть корень.
<tex>T_1</tex> и <tex>T_2</tex> может быть только либо корнем <tex>T_1</tex>, либо корнем <tex>T_2</tex>.
Рассмотрим случай, в котором корень <tex>T_1</tex> выше корня <tex>T_2</tex>.
