Изменения
→find(tree, x)
'''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983 </tex> году.
==Эвристики==
* '''Splay''' {{---}} также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.
'''Пример''': При последовательном использовании операций "move to root" для вершин <tex>A</tex> и <tex>B</tex> требуется по <tex>6 </tex> поворотов, в то время как при использовании операции "splay" для вершины <tex>B</tex> достаточно <tex>3 </tex> поворотов.
[[file:Move_to_root.png|700px750px]]
[[file:Splay.png|800px750px]]
==Операции со splay-деревом==
===splay(tree, x)===
"splay" делится на <tex>3 </tex> случая:
====zig====
Если <tex>p</tex> — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетной.
===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==
[[Амортизационный анализ | Амортизационный анализ]] сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>x</tex> — это величина, обозначаемая <tex>r(x)</tex> и равная <tex>\log_2 C(x)</tex>, где <tex>C(x)</tex> — количество вершин в поддереве с корнем в <tex>x</tex>.
{{Лемма
Мы утверждаем, что эта сумма не превосходит <tex>3(r'(x) - r(x))</tex>, то есть, что <tex>r(x) + r'(g) - 2r'(x) \leqslant -2</tex>. Преобразуем полученное выражение следующим образом: <tex>(r(x) - r'(x)) + (r'(g) - r'(x)) = \log_2 \dfrac {C(x)}{C'(x)} + \log_2 \dfrac {C'(g)}{C'(x)}</tex>.
Из рисунка видно, что <tex>C'(g) + C(x) \leqslant C'(x)</tex>, значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов <tex>\log_2 a + \log_2 b = \log_2 ab</tex>. При <tex>a + b \leqslant 1</tex> произведение <tex>ab</tex> по неравенству между средними не превышает <tex>\dfrac{1/}{4}</tex>. А поскольку логарифм — функция возрастающая, то <tex>\log_2 ab \leqslant -2</tex>, что и является требуемым неравенством.
'''zig-zag'''. Выполнено два поворота, амортизированное время выполнения шага <tex>T = 2 + r'(x) + r'(p) + r'(g) - r(x) - r(p) - r(g)</tex>. Поскольку <tex>r'(x) = r(g)</tex>, то <tex>T = 2 + r'(p) + r'(g) - r(x) - r(p)</tex>. Далее, так как <tex>r(x) \leqslant r(p)</tex>, то <tex>T \leqslant 2 + r'(p) + r'(g) - 2r(x)</tex>.
{{Теорема
|statement=
Если к ключам <tex>1 \ldots n</tex>, сложенным в сплей-дерево выполняется <tex>m</tex> запросов, к <tex>i</tex>-му ключу осуществляется <tex>k_i</tex> запросов, где <tex>k_i> 0</tex> > 0, то суммарное время работы не превышает <tex>O(m \cdot H(p_1, p_2, \ldots , p_n))</tex>, где <tex>p_i = k_i / m</tex>, <tex>H</tex> — шенноновская энтропия
|proof=
Известно, что <tex>H(p_1, p_2, \ldots , p_n) = -c \cdot \displaystyle \sum_{i=1}^n (p_i \cdot \log_{2}p_i)</tex> {{---}} [[Энтропия_случайного_источника | шенноновская энтропия]].
==Splay-деревья по неявному ключу==
Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.
== См. также ==
* [[2-3 дерево]]
* [[B-дерево]]
* [[B+-дерево]]
* [[АВЛ-дерево]]
* [[Красно-черное дерево]]
==Источники информации==
