90
правок
Изменения
м
# 1. 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>.
# 2. 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>.
# 3. 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>, для поворота налево.
→Splay
===Splay===
"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Эти повороты можно совершать в прямом и обратном порядке в зависимости от задачи, что иллюстрируют рисунки. Пока <tex> x </tex> не является корнем дерева выполняется следующее :
[[file:zig.jpg|500px|Zig - поворот]]
[[file:Zigzig.PNG|500px|Zig-zig - поворот]]
[[file:zigzag.PNG|500px|Zig-zag - поворот]]
