Изменения

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

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

* <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру <tex>Split\mathrm{split}</tex> от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левой частью ответа нашей процедуры, а правая часть сына станет левым сыном корня, после чего корень станет правой частью ответа.

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