Изменения

"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока <tex> x </tex> не является корнем дерева выполняется следующее :

# Zig. Если <tex> p(x) </tex> - корень дерева, то совершаем один поворот вокруг ребра <tex> \langle x, p(x) \rangle </tex>, делая <tex> x </tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex> x </tex> была нечетной.

[[file:zig.jpg|500px|Zig - поворот]]

# Zig-Zig. Если <tex> p(x) </tex> - не корень дерева, а <tex> x </tex> и <tex> p(x) </tex> - оба левые или оба правые дети, то делаем поворот ребра <tex> \langle p(x), p(p(x)) \rangle </tex>, а затем поворот ребра <tex> \langle x, p(x) \rangle </tex>.

Данная операция занимает <tex> O(d) </tex> времени, где <tex> d </tex> - длина пути от <tex> x </tex> до корня. В результате этой операции <tex> x </tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".

==Merge==

Merge(<tex>T_1</tex>, <tex>T_2</tex>). У нас есть два дерева <tex>T_1</tex> и <tex>T_2</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay от самого большого элемента в дереве <tex>T_1</tex> (пусть это элемент <tex>i</tex>). После этого корень <tex>T_1</tex> содержит элемент <tex>i</tex>, при этом у него нет правого ребёнка. Делаем <tex>T_2</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево.