Изменения

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

Splay-дерево

450 байт добавлено, 21:04, 13 апреля 2012
Нет описания правки
'''Сплей-дерево (Splay-tree)''' {{---}} двоичное дерево поиска, позволяющее находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Основной идеей работы дерева является эвристика "Move to Root", перетаскивающая найденную вершину в корень почти после каждой операции. Для <tex>p </tex> - предка вершины <tex>x </tex> "Move to Root" совершает повороты вокруг ребра <tex>(x, p)</tex>, пока <tex>x </tex> не окажется корнем дерева.
=Операции со splay-деревом=
 ==Splay(Tree, x)=="Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока <tex>x </tex> не является корнем дерева выполняется следующее:
===Zig===
Если <tex>p </tex> - корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x </tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x </tex> была нечетной.
[[file:ZigSplay.gif|500px|Zig - поворот]]
===Zig-Zig===
Если <tex>p </tex> - не корень дерева, а <tex>x </tex> и <tex>p </tex> - оба левые или оба правые дети, то делаем поворот ребра <tex>(p, g)</tex>, где <tex>g </tex> отец <tex>p</tex>, а затем поворот ребра <tex>(x, p)</tex>.
[[file:ZigZigSplay.gif|500px|Zig-zig - поворот]]
===Zig-Zag===
Если <tex>p </tex> - не корень дерева и <tex>x - левый ребенок, а <tex>p </tex> - правый, или наоборот, то делаем поворот вокруг ребра <tex>(x, p)</tex>, а затем поворот нового ребра <tex>(x, g)</tex>, где <tex>g </tex> - бывший родитель <tex>p</tex>.
[[file:ZigZagSplay.gif|500px|Zig-zag - поворот]]
Данная операция занимает <tex>O(d) </tex> времени, где <tex>d </tex> - длина пути от <tex>x </tex> до корня. В результате этой операции <tex>x </tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
==Find(Tree, key)==
==Merge(Tree1, Tree2)==
У нас есть два дерева <tex>Tree1 </tex> и <tex>Tree2</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay от самого большого элемента в дереве <tex>Tree1 </tex> (пусть это элемент <tex>i</tex>). После этого корень <tex>Tree1 </tex> содержит элемент <tex>i</tex>, при этом у него нет правого ребёнка. Делаем <tex>Tree2 </tex> правым поддеревом <tex>i </tex> и возвращаем полученное дерево.
==Split(Tree, keyx)==Запускаем Splay от элемента key <tex>x</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем key<tex>x</tex>.
==Add(Tree, keyx)==Запускаем Split(Tree, keyx), который нам возвращает деревья Tree1 <tex>Tree</tex>1 и <tex>Tree2</tex>, их подвешиваем к key <tex>x</tex> как левое и правое поддеревья соответственно.
==Remove(Tree, keyx)== Запускаем Splay от key <tex>x</tex> элемента и возвращаем Merge от его детей.
=Анализ операции splay=
Анонимный участник

Навигация