Изменения
→Операция merge
== Операция 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>.Рассмотрим случай, в котором корень <tex>T_1</tex> выше корня <tex>T_2</tex>.Случай, в котором корень <tex>T_2</tex> выше корня <tex>T_1</tex>, симметричен этому. Если корень <tex>T_1</tex> выше корня <tex>T_2</tex>, то он и будет являться корнем. Тогда левое поддерево <tex>T</tex> совпадёт с левым поддеревом <tex>T_1</tex>. Справа же нужно подвесить объединение правого поддерева<tex>T_1</tex> и дерева <tex>T_2</tex>. Рассуждая аналогично операции <tex>\mathrm{split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex> равна <tex>\mathcal{O}(\log n)</tex>. {{TODO|t=запилить рисунок}}
== Операция add==
