== Операция split ==
Тут будет == Операция 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>. Как же устроена сея замечательная операция? Рассмотрим случай, в котором требуется распилить дерево по ключу, большему ключа корня.Посмотрим, как будут устроены результирующие деревья <tex>T_1</tex> и <tex>T_2</tex>:* <tex>T_1</tex>: левое поддерево <tex>T_1</tex> совпадёт с левым поддеревом <tex>T</tex>. Для нахождения правого поддерева <tex>T_1</tex>, нужно распилить правое поддерево <tex>T</tex> на <tex>T^R_1</tex> и <tex>T^R_2</tex> по ключу <tex>x</tex> и взять <tex>T^R_1</tex>.* <tex>T_2</tex> совпадёт с <tex>T^R_2</tex>. Случай, в котором требуется распилить дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично. Оценим время работы операции <tex>\mathrm{split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{split}</tex> длядерева хотя бы на один меньшей высоты и делается ещё <tex>\mathcal{O}(1)</tex> операция. Тогда итоговая трудоёмкость этой операцииравна <tex>\mathcal{O}(h)</tex>, где <tex>h</tex> {{---}} высота дерева. Так как высота декартова дерева {{---}} <tex>\mathcal{O}(\log n)</tex>, то и операция <tex>\mathrm{split}</tex> работает за <tex>\mathcal{O}(\log n)</tex>. {{TODO|t=Запилить рисунок}}
== Операция merge ==
