Изменения
Нет описания правки
Данная операция занимает <tex> O(d) </tex> времени, где <tex> d </tex> - длина пути от <tex> x </tex> до корня. В результате этой операции <tex> x </tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
==Merge(<tex>T_1</tex>, <tex>T_2</tex>)==
У нас есть два дерева <tex>T_1</tex> и <tex>T_2</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго.
запускаем Move to Root от самого большого элемента (пусть это элемент <tex>i</tex>) в дереве <tex>T_1</tex>. после этого корень <tex>T_1</tex> содержит элемент <tex>i</tex>, причём у него нет правого ребёнка. делаем <tex>T_2</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево.
==Split(<tex>i</tex>, <tex>T</tex>)==
запускаем Splay от элемента <tex>i</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>i</tex>.
==Insert(<tex>i</tex>, <tex>T</tex>)==
Запускаем split(<tex>i</tex>, <tex>T</tex>), который нам возвращает деревья <tex>T_1</tex> и <tex>T_2</tex>, их подвешиваем к <tex>i</tex> как левое и правое поддеревья соответственно.
==Remove(<tex>i</tex>, <tex>T</tex>)==
Запускаем Move to Front от <tex>i</tex>-го элемента и возвращаем Merge от его детей.
== Анализ операции splay ==
