Изменения

Основной идеей работы дерева является перетаскивание найденной вершины эвристика "Move to Root", перетаскивающая найденную вершину в корень почти после каждой операции. Для <tex> p(x) </tex> - предка вершины <tex> x </tex> эвристика "Move to Root" совершает повороты вокруг ребра <tex> \langle (x, p(x) \rangle </tex>), пока <tex> x </tex> не окажется корнем дерева.Данный поворот аналогичен zig - повороту.==Операции со splay-деревом=====Splay==="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> была нечетной. На рисунке представлен пример работы zig, где <tex>a</tex> является предком <tex>b</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>a</tex> и <tex>c</tex>, а второй {{---}} между <tex>a</tex> и <tex>b</tex>.[[file:Zigzig.PNG|500px|Zig-zig - поворот]]* Zig-Zag. Если <tex> p(x) </tex> - не корень дерева и <tex> x </tex> - левый ребенок, а <tex> p(x) </tex> - правый, или наоборот, то делаем поворот вокруг ребра <tex> \langle x, p(x) \rangle </tex>, а затем поворот нового ребра <tex> \langle x, p(x) \rangle </tex>, где <tex> p(x) </tex> - новый родитель <tex> x </tex>: первый поворот ребра между <tex>a</tex> и <tex>b</tex>, а второй между <tex>b</tex> и <tex>c</tex>, для поворота направо, и первый поворот ребра между <tex>c</tex> и <tex>b</tex>, а второй между <tex>b</tex> и <tex>a</tex>, для поворота налево.[[file:zigzag.PNG|500px|Zig-zag - поворот]]

Данная операция занимает <tex> O(d) </tex> времени=Операции со splay-деревом===Splay=="Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, где <tex> d </tex> - длина пути но при этом она использует другую последовательность поворотов. Эти повороты можно совершать в прямом и обратном порядке в зависимости от <tex> x </tex> до корнязадачи, что иллюстрируют рисунки. В результате этой операции <tex> Пока x </tex> становится не является корнем деревавыполняется следующее :===Zig===Если p - корень дерева с сыном x, а расстояние до корня от каждой вершины сокращается примерно пополамто совершаем один поворот вокруг ребра (x, p), что связано с разделением случаев "zig-zig" делая x корнем дерева. Данный случай является крайним и "zig-zag"выполняется только один раз в конце, если изначальная глубина x была нечетной.

[[file:ZigSplay.gif|500px|Zig - поворот]]===Zig-Zig===Если p - не корень дерева, а x и p - оба левые или оба правые дети, то делаем поворот ребра (p, g), где g отец p, а затем поворот ребра (x, p). [[file:ZigZigSplay.gif|500px|Zig-zig - поворот]]===Zig-Zag===Если p - не корень дерева и x - левый ребенок, а p - правый, или наоборот, то делаем поворот вокруг ребра (x, p), а затем поворот нового ребра (x, g), где g - бывший родитель p. [[file:ZigZagSplay.gif|500px|Zig-zag - поворот]] Данная операция занимает O(d) времени, где d - длина пути от x до корня. В результате этой операции x становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag". ==Find=(key)==

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

===Split=(key, Tree)==Split(<tex>i</tex>, <tex>T</tex>). Запускаем Splay от элемента <tex>i</tex> key и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>i</tex>key.===Add=(key, Tree)==Add(<tex>i</tex>, <tex>T</tex>). Запускаем Split(<tex>i</tex>key, <tex>T</tex>Tree), который нам возвращает деревья <tex>T_1</tex> Tree_1 и <tex>T_2</tex>Tree_2, их подвешиваем к <tex>i</tex> key как левое и правое поддеревья соответственно.

===Remove=(key, Tree)== Remove(<tex>i</tex>, <tex>T</tex>). Запускаем Splay от <tex>i</tex>-го key элемента и возвращаем Merge от его детей.

== Анализ операции splay ==

# *[http://en.wikipedia.org/wiki/Splay_tree Splay tree - Википедия]*[http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf Sleator, Daniel SleatorD.; Tarjan, Robert Tarjan E."A data structure for dynamic treesSelf-Adjusting Binary Search Trees"]