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