Изменения

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

Splay-дерево

9230 байт добавлено, 18 май
Добавлены две реализации операции splay
===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> {{---}} симметрично rotate_left
*<tex>\mathrm{p}(v)</tex> {{---}} родитель вершины v
*<tex>\mathrm{g}(v)</tex> {{---}} родитель родителя вершины v
 
Приведем реализацию <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>\mathrm{L}</tex>, <tex>\mathrm{M}</tex>, <tex>\mathrm{R}</tex>. Деревья <tex>\mathrm{L}</tex> и <tex>\mathrm{R}</tex> содержат все вершины исходного дерева, для которых на данном этапе известно, что они меньше или больше искомого элемента соответственно. Дерево <tex>\mathrm{M}</tex> содержит вершины, принадлежащие поддереву текущей вершины на пути к целевой в исходном дереве. Изначально деревья <tex>\mathrm{L}</tex> и <tex>\mathrm{R}</tex> пусты, а текущая вершина пути к целевой {{---}} корень.
 
Во время операции splay производится спуск на две вершины по пути поиска целевой. Пройденные ребра удаляются, и отсоединившиеся при этом поддеревья добавляются правым ребенком наибольшей по значению вершине дерева <tex>\mathrm{L}</tex> или левым ребенком к наименьшей по значению вершине дерева <tex>\mathrm{R}</tex>. При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот. В конце пути производится слияние деревьев <tex>\mathrm{L}</tex>, <tex>\mathrm{M}</tex> и <tex>\mathrm{R}</tex> таким образом, что новым корнем дерева становится вершина с целевым значением.
 
Приведем реализацию. Определим переменные:
*<tex>\mathrm{val}</tex> {{---}} значение в целевой вершине
*<tex>\mathrm{t}</tex> {{---}} текущая вершина, до и после splay {{---}} корень дерева
*<tex>\mathrm{l}</tex> {{---}} наибольшая по значению вершина дерева <tex>\mathrm{L}</tex>
*<tex>\mathrm{r}</tex> {{---}} наименьшая по значению вершина дерева <tex>\mathrm{R}</tex>
*<tex>\mathrm{l\_root}</tex> {{---}} корень дерева <tex>\mathrm{L}</tex>
*<tex>\mathrm{r\_root}</tex> {{---}} корень дерева <tex>\mathrm{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>\mathrm{l}</tex> с полученным деревом
*<tex>\mathrm{break\_right}(v)</tex> {{---}} симметрично <tex>\mathrm{break_left}</tex>
*<tex>\mathrm{assemble}()</tex> {{---}} слить деревья <tex>\mathrm{L}</tex>, <tex>\mathrm{M}</tex> и <tex>\mathrm{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_2 n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log_2 n)</tex>
==Анализ операции splay==
5
правок

Навигация