Изменения

'''Сплей-дерево (Splay-tree)''' {{---}} саморегулирующееся двоичное дерево поиска, поддерживающее свойство сбалансированности. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.

"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>.

# 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>.

# 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>, для поворота налево.