Изменения

Перейти к: навигация, поиск

Splay-дерево

Нет изменений в размере, 21:12, 6 апреля 2012
Нет описания правки
Данный поворот аналогичен zig - повороту.
===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 - поворот]]
94
правки

Навигация