Изменения
Нет описания правки
'''Сплей-дерево (Splay-tree)''' {{---}} двоичное дерево поиска, позволяющее находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Основной идеей работы дерева является эвристика "Move to Root", перетаскивающая найденную вершину в корень почти после каждой операции. Для p(x) - предка вершины x "Move to Root" совершает повороты вокруг ребра (x, p(x)), пока x не окажется корнем дерева.
=Операции со splay-деревом=
==Splay==
"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Эти повороты можно совершать в прямом и обратном порядке в зависимости от задачи, что иллюстрируют рисунки. Пока x не является корнем дерева выполняется следующее :
===Zig===
Если p - корень дерева с сыном x, то совершаем один поворот вокруг ребра (x, p), делая x корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина x была нечетной.
}}
===Литература===
*[http://en.wikipedia.org/wiki/Splay_tree Splay tree - Википедия]
