=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 декартову дереву по неявному ключу].
=Литература=
