13
правок
Изменения
Исправление помарок в разделе
Определим вспомогательные функции:
*<tex>\mathrm{rotate\_left}(v)</tex> {{---}} поворот ребра, соединяющего v и его правого сына
*<tex>\mathrm{rotate\_right}(v)</tex> {{---}} симметрично rotate_left<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 = p(v)
'''Node''' r = v.right
'''if''' (p != '''null''')
'''if''' (p.left == v)
p.left = r
p(v) = r
p(r) = p
'''if''' (v.right != '''null''')
p(v) = v
'''void''' splay('''Node''' v):
'''while''' (p(v) != '''null''')
'''if''' (v == p(v).left)
'''if''' (g(v) == '''null''')
rotate_right(p(v))
Преимуществом данного подхода является возможность инкапсуляции всех модификаций структуры дерева, включая создание вспомогательных переменных и нарушение инвариантов. Рекомендуется для использования в случае, когда есть прямой доступ к целевой для операции splay вершине, иначе требуется два прохода по пути от корня до вершины (первый {{---}} поиск вершины стандартным алгоритмом, второй {{---}} splay).
===Top-down===
Данная реализация не требует прямого доступа к целевой вершине, поскольку процесс перебалансировки происходит во время поиска вершины в дереве.
В процессе спуска во время операции Splay 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> пусты, а текущая вершина пути к целевой {{---}} корень.
Приведем реализацию. Определим переменные:
*<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_leftbreak\_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> симметрична.
t = break_left(t)
t = break_right(t)
Реализацию splay можно упростить, опустив вторую операцию удаления ребра в случае zig-zag. Приведем также ее:
'''if''' (val < t.left.value)
t = rotate_right(t)
'''else'''
'''if''' (val > t.right.value)
t = rotate_left(t)
===Время работы===
В обоих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из <tex>O(\log_2 log n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log_2 log n)</tex>
==Анализ операции splay==
