Изменения
Новая страница: «'''Сплей-дерево (Splay-tree)''' {{---}} саморегулирующееся двоичное дерево поиска. Относится к разря…»
'''Сплей-дерево (Splay-tree)''' {{---}} саморегулирующееся двоичное дерево поиска. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Основной идей для сохранение баланса дерева является перетаскивание найденной вершины в корень после каждой операции поиска.
==Move to Root==
Пусть <tex> p(x) </tex> - предок вершины <tex> x </tex>.
Эвристика "Move to Root" совершает повороты вокруг ребра <tex> <x, p(x)> </tex>, пока <tex> x </tex> не окажется корнем дерева.
==Splay==
"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока <tex> x </tex> не является корнем дерева выполняется следующее :
# Zig. Если <tex> p(x) </tex> - корень дерева, то совершаем один поворот вокруг ребра <tex> <x, p(x)> </tex>, делая <tex> x </tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex> x </tex> была нечетной.
# Zig-Zig. Если <tex> p(x) </tex> - не корень дерева, а <tex> x </tex> и <tex> p(x) </tex> - оба левые или оба правые дети, то делаем поворот ребра <tex> <p(x), p(p(x))> </tex>, а затем поворот ребра <tex> <x, p(x)> </tex>.
# Zig-Zag. Если <tex> p(x) </tex> - не корень дерева и <tex> x </tex> - левый ребенок, а <tex> p(x) </tex> - правый, или наоборот, то делаем поворот вокруг ребра <tex> <x, p(x)> </tex>, а затем поворот нового ребра <tex> <x, p(x)> </tex>, где <tex> p(x) </tex> - новый родитель <tex> x </tex>.
Данная операция занимает <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"
Основной идей для сохранение баланса дерева является перетаскивание найденной вершины в корень после каждой операции поиска.
==Move to Root==
Пусть <tex> p(x) </tex> - предок вершины <tex> x </tex>.
Эвристика "Move to Root" совершает повороты вокруг ребра <tex> <x, p(x)> </tex>, пока <tex> x </tex> не окажется корнем дерева.
==Splay==
"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока <tex> x </tex> не является корнем дерева выполняется следующее :
# Zig. Если <tex> p(x) </tex> - корень дерева, то совершаем один поворот вокруг ребра <tex> <x, p(x)> </tex>, делая <tex> x </tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex> x </tex> была нечетной.
# Zig-Zig. Если <tex> p(x) </tex> - не корень дерева, а <tex> x </tex> и <tex> p(x) </tex> - оба левые или оба правые дети, то делаем поворот ребра <tex> <p(x), p(p(x))> </tex>, а затем поворот ребра <tex> <x, p(x)> </tex>.
# Zig-Zag. Если <tex> p(x) </tex> - не корень дерева и <tex> x </tex> - левый ребенок, а <tex> p(x) </tex> - правый, или наоборот, то делаем поворот вокруг ребра <tex> <x, p(x)> </tex>, а затем поворот нового ребра <tex> <x, p(x)> </tex>, где <tex> p(x) </tex> - новый родитель <tex> x </tex>.
Данная операция занимает <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"
