Изменения

Структура обычного декартова дерева поддерживается с помощью двух операций: '''<tex>split''' </tex> {{---}} разбиение одного декартова дерева на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и '''<tex>merge''' </tex> {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: <tex>split(root, t)</tex> {{---}} разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и <tex>merge(root1, root2)</tex> {{---}} слияние двух любых деревьев, соответственно.

Пусть процедура '''<tex>split''' </tex> запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим сначала два тривиальных случая. Первый: <tex>l = t</tex>. В этом случае процедура '''<tex>split''' </tex> должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левой части ответа, а сам корень {{---}} в качестве правой. Второй случай (<tex>t = l + 1</tex>) рассматривается аналогично. Следующий случай не так тривиален: <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру '''<tex>split''' </tex> от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левой частью ответа нашей процедуры, а правая часть сына станет левым сыном корня, после чего корень станет правой частью ответа. Случай <tex>t > l + 1</tex> рассматривается аналогично, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.

Посмотрим любую из [[Декартово дерево#Операция merge|реализаций]] процедуры '''<tex>merge'''</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры '''<tex>merge''' </tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.