Изменения

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

Splay-дерево

9142 байта добавлено, 17:58, 7 октября 2019
find(tree, x)
===find(tree, x)===
Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного деревапоиска]], только после нее запускается операция splay.
===merge(tree1, tree2)===
===remove(tree, x)===
Запускаем splay от <tex>x</tex> элемента и возвращаем Merge от его детей.
 
==Реализация операции splay==
 
===Bottom-up===
 
В этой реализации операция splay производится при подъеме от целевой вершины до корня путем применения поворотов. Для подъема по дереву требуется доступ к вершине-родителю. Этого можно достичь либо путем хранения в каждой вершине ссылки на родителя, либо с помощью стека вершин на пути от корня к целевой.
 
Определим вспомогательные функции:
*<tex>\mathrm{rotate\_left}(v)</tex> {{---}} поворот ребра, соединяющего v и его правого сына
*<tex>\mathrm{rotate\_right}(v)</tex> {{---}} симметрично <tex>\mathrm{rotate\_left}</tex>
*<tex>\mathrm{p}(v)</tex> {{---}} родитель вершины <tex>v</tex>
*<tex>\mathrm{g}(v)</tex> {{---}} родитель родителя вершины <tex>v</tex>
 
Приведем реализацию <tex>\mathrm{p}</tex>, <tex>\mathrm{g}</tex>, <tex>\mathrm{rotate\_left}</tex>. Реализация <tex>\mathrm{rotate\_right}</tex> симметрична. Положим, что для доступа к родительской вершине имеется соответствующее поле.
 
'''Node''' p('''Node''' v):
'''return''' v.parent
 
'''Node''' g('''Node''' v):
'''return''' p(p(v))
 
'''void''' rotate_left('''Node''' v):
'''Node''' p = p(v)
'''Node''' r = v.right
'''if''' (p != '''null''')
'''if''' (p.left == v)
p.left = r
'''else'''
p.right = r
'''Node''' tmp = r.left
r.left = v
v.right = tmp
p(v) = r
p(r) = p
'''if''' (v.right != '''null''')
p(v) = v
 
Реализация splay:
 
'''void''' splay('''Node''' v):
'''while''' (p(v) != '''null''')
'''if''' (v == p(v).left)
'''if''' (g(v) == '''null''')
rotate_right(p(v))
'''else if''' (p(v) == g(v).left)
rotate_right(g(v))
rotate_right(p(v))
'''else'''
rotate_right(p(v))
rotate_left(p(v))
'''else'''
'''if''' (g(v) == '''null''')
rotate_left(p(v))
'''else if''' (p(v) == g(v).right)
rotate_left(g(v))
rotate_left(p(v))
'''else'''
rotate_left(p(v))
rotate_right(p(v))
 
Преимуществом данного подхода является возможность инкапсуляции всех модификаций структуры дерева, включая создание вспомогательных переменных и нарушение инвариантов. Рекомендуется для использования в случае, когда есть прямой доступ к целевой для операции splay вершине, иначе требуется два прохода по пути от корня до вершины (первый {{---}} поиск вершины стандартным алгоритмом, второй {{---}} splay).
 
===Top-down===
 
Данная реализация не требует прямого доступа к целевой вершине, поскольку процесс перебалансировки происходит во время поиска вершины в дереве.
 
В процессе спуска во время операции splay дерево разбивается на три части: <tex>L</tex>, <tex>M</tex>, <tex>R</tex>. Деревья <tex>L</tex> и <tex>R</tex> содержат все вершины исходного дерева, для которых на данном этапе известно, что они меньше или больше искомого элемента соответственно. Дерево <tex>M</tex> содержит вершины, принадлежащие поддереву текущей вершины на пути к целевой в исходном дереве. Изначально деревья <tex>L</tex> и <tex>R</tex> пусты, а текущая вершина пути к целевой {{---}} корень.
 
За одну итерацию операции splay производится спуск на две вершины по пути поиска целевой. Пройденные ребра удаляются, и отсоединившиеся при этом поддеревья добавляются правым ребенком наибольшей по значению вершине дерева <tex>L</tex> или левым ребенком к наименьшей по значению вершине дерева <tex>R</tex>. При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот.
 
[[file:Top-Down_Splay.png|512px]]
 
В конце пути производится слияние деревьев <tex>L</tex>, <tex>M</tex> и <tex>R</tex> таким образом, что новым корнем дерева становится вершина с целевым значением.
 
[[file:Top-Down_Assembly.png|512px]]
 
Приведем реализацию. Определим переменные:
*<tex>val</tex> {{---}} значение в целевой вершине
*<tex>t</tex> {{---}} текущая вершина, до и после splay {{---}} корень дерева
*<tex>l</tex> {{---}} наибольшая по значению вершина дерева <tex>L</tex>
*<tex>r</tex> {{---}} наименьшая по значению вершина дерева <tex>R</tex>
*<tex>l\_root</tex> {{---}} корень дерева <tex>L</tex>
*<tex>r\_root</tex> {{---}} корень дерева <tex>R</tex>
 
Определим вспомогательные функции:
*<tex>\mathrm{rotate\_left}(v)</tex> {{---}} поворот ребра, соединяющего <tex>v</tex> и его правого сына
*<tex>\mathrm{rotate\_right}(v)</tex> {{---}} симметрично <tex>\mathrm{rotate\_left}</tex>
*<tex>\mathrm{break\_left}(v)</tex> {{---}} удалить ребро, соединяющее <tex>v</tex> и его правого сына, соединить <tex>l</tex> с полученным деревом
*<tex>\mathrm{break\_right}(v)</tex> {{---}} симметрично <tex>\mathrm{break\_left}</tex>
*<tex>\mathrm{assemble}()</tex> {{---}} слить деревья <tex>L</tex>, <tex>M</tex> и <tex>R</tex>
 
Приведем реализацию <tex>\mathrm{rotate\_left}</tex>, <tex>\mathrm{break\_left}</tex>, <tex>\mathrm{assemble}</tex>. Реализация и <tex>\mathrm{break\_right}</tex> симметрична.
 
'''Node''' rotate_left('''Node''' v):
'''Node''' r = v.right
'''Note''' tmp = r.left
r.left = v
v.right = tmp
'''return''' r
 
'''Node''' break_left('''Node''' v):
'''Node''' tmp = v.right
v.right = '''null'''
'''if''' (l == '''null''')
l_root = l = v
'''else'''
l.right = v
l = v
'''return''' tmp
 
'''void''' assemble():
l.right = t.left
r.left = t.right
t.left = l_root
t.right = r_root
 
Реализация splay:
 
'''void''' splay('''Value''' val):
'''while''' (t.value != val)
'''if''' (val < t.value)
'''if''' (val == t.left.value)
t = break_right(t)
'''else if''' (val < t.left.value)
t = rotate_right(t)
t = break_right(t)
'''else'''
t = break_right(t)
t = break_left(t)
'''else'''
'''if''' (val == t.right.value)
t = break_left(t)
'''else if''' (val > t.right.value)
t = rotate_left(t)
t = break_left(t)
'''else'''
t = break_left(t)
t = break_right(t)
assemble()
 
Реализацию splay можно упростить, опустив вторую операцию удаления ребра в случае zig-zag. Приведем также ее:
 
'''void''' simplified_splay('''Value''' val):
'''while''' (t.value != val)
'''if''' (val < t.value)
'''if''' (val < t.left.value)
t = rotate_right(t)
t = break_right(t)
'''else'''
'''if''' (val > t.right.value)
t = rotate_left(t)
t = break_left(t)
assemble()
 
===Время работы===
 
В обеих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из <tex>O(\log n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log n)</tex>
==Анализ операции splay==
Анонимный участник

Навигация