Изменения
Нет описания правки
Данная операция занимает O(d) времени, где d - длина пути от x до корня. В результате этой операции x становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
==Find(Tree, key)==
Эта операция выполняется как для обычного бинарного дерева, только после нее запускается операция Splay.
У нас есть два дерева Tree1 и Tree2, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay от самого большого элемента в дереве Tree1 (пусть это элемент i). После этого корень Tree1 содержит элемент i, при этом у него нет правого ребёнка. Делаем Tree2 правым поддеревом i и возвращаем полученное дерево.
==Split(Tree, key, Tree)==
Запускаем Splay от элемента key и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем key.
==RemoveAdd(Tree, key)==Запускаем Split(Tree, key), который нам возвращает деревья Tree1 и Tree2, их подвешиваем к key как левое и правое поддеревья соответственно. ==Remove(Tree, key)==
Запускаем Splay от key элемента и возвращаем Merge от его детей.
