Изменения

Эта операция выполняется как для обычного [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0[Дерево поиска,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F наивная реализация|бинарного дерева]] , только после нее запускается операция Splay.

Для операции split нам необходимо хранить число вершин в поддереве. Это число может меняться вовремя операции splay, но при этом его легко поддерживать: мы точно знаем, куда переместятся поддеревья. Тогда после операции мы просто пересчитываем число элементов для 2 (zig) или 3 (zig-zig, zig-zag) вершин. Остальные операции аналогичны [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE_%D0%BD%D0%B5%D1%8F%D0%B2%D0%BD%D0%BE%D0%BC%D1%83_%D0%BA%D0%BB%D1%8E%D1%87%D1%83 [Декартово дерево по неявному ключу|декартову дереву по неявному ключу]].