Splay-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
[[file:Zigzig.PNG|500px|Zig-zig - поворот]]
 
[[file:Zigzig.PNG|500px|Zig-zig - поворот]]
 
# 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>.
 
# 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>.
 +
[[file:zigzag.PNG|500px|Zig-zag - поворот]]
  
 
Данная операция занимает <tex> O(d) </tex> времени, где <tex> d </tex> - длина пути от <tex> x </tex> до корня. В результате этой операции <tex> x </tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
 
Данная операция занимает <tex> O(d) </tex> времени, где <tex> d </tex> - длина пути от <tex> x </tex> до корня. В результате этой операции <tex> x </tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
 
==Литература==
 
==Литература==
 
# Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"
 
# Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"

Версия 00:22, 27 апреля 2011

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

Основной идей для сохранение баланса дерева является перетаскивание найденной вершины в корень после каждой операции поиска.

Move to Root

Пусть [math] p(x) [/math] - предок вершины [math] x [/math]. Эвристика "Move to Root" совершает повороты вокруг ребра [math] \langle x, p(x) \rangle [/math], пока [math] x [/math] не окажется корнем дерева. Данный поворот аналогичен zig - повороту.

Splay

"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока [math] x [/math] не является корнем дерева выполняется следующее :

  1. Zig. Если [math] p(x) [/math] - корень дерева, то совершаем один поворот вокруг ребра [math] \langle x, p(x) \rangle [/math], делая [math] x [/math] корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина [math] x [/math] была нечетной.

Zig - поворот

  1. Zig-Zig. Если [math] p(x) [/math] - не корень дерева, а [math] x [/math] и [math] p(x) [/math] - оба левые или оба правые дети, то делаем поворот ребра [math] \langle p(x), p(p(x)) \rangle [/math], а затем поворот ребра [math] \langle x, p(x) \rangle [/math].

Zig-zig - поворот

  1. Zig-Zag. Если [math] p(x) [/math] - не корень дерева и [math] x [/math] - левый ребенок, а [math] p(x) [/math] - правый, или наоборот, то делаем поворот вокруг ребра [math] \langle x, p(x) \rangle [/math], а затем поворот нового ребра [math] \langle x, p(x) \rangle [/math], где [math] p(x) [/math] - новый родитель [math] x [/math].

Zig-zag - поворот

Данная операция занимает [math] O(d) [/math] времени, где [math] d [/math] - длина пути от [math] x [/math] до корня. В результате этой операции [math] x [/math] становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".

Литература

  1. Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"