Изменения

Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.

== Операция split ==

Операция <tex>\mathrm{split}</tex>(''распилить'') позволяет сделать следующее: разрезать декартово дерево <tex>T</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>.

== Операция merge ==

Рассмотрим вторую замечательную операцию с декартовыми деревьями {{---}} <tex>\mathrm{merge}</tex>(''слить'').

Рассуждая аналогично операции <tex>\mathrm{split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex>

равна <tex>\mathcal{O}(\log n)</tex>.

== Операция add==