Изменения
→find(tree, x)
==Операции со 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> была нечетной. [[file:zigЗиг.jpgpng|500px800px|Zig - zig — поворот]]# Zig====zig-Zig. zig====Если <tex> p(x) </tex> - — не корень дерева, а <tex> x </tex> и <tex> p(x) </tex> - — оба левые или оба правые дети, то делаем поворот ребра <tex> \langle (p(x, g)</tex>, где <tex>g</tex> отец <tex>p(p(x)) \rangle </tex>, а затем поворот ребра <tex> \langle (x, p(x) \rangle </tex>. [[file:ZigzigЗиг_зиг.PNGpng|500px800px|Zigzig-zig - — поворот]]# Zig====zig-Zag. zag====Если <tex> p(x) </tex> - — не корень дерева и <tex> x </tex> - — левый ребенок, а <tex> p(x) </tex> - — правый, или наоборот, то делаем поворот вокруг ребра <tex> \langle (x, p(x) \rangle </tex>, а затем поворот нового ребра <tex>(x, g)</tex>, где <tex>g</tex> — бывший родитель <tex>p</tex>. [[file:Зиг_заг2.png|900px|zig-zag — поворот]] Данная операция занимает <tex>O(d)</tex> времени, где <tex>d</tex> — длина пути от <tex>x</tex> до корня. ===find(tree, x)===Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного дерева поиска]], только после нее запускается операция splay. ===merge(tree1, tree2)===У нас есть два дерева <tex> \langle mathtt{tree1}</tex> и <tex>\mathtt{tree2}</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем splay от самого большого элемента в дереве <tex>\mathtt{tree1}</tex> (пусть это элемент <tex>i</tex>). После этого корень <tex>\mathtt{tree1}</tex> содержит элемент <tex>i</tex>, при этом у него нет правого ребёнка. Делаем <tex>\mathtt{tree2}</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево. ===split(tree, x)===Запускаем splay от элемента <tex>x</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, pсодержит корень элемент больше или не больше, чем <tex>x</tex>. ===add(tree, x)===Запускаем split(tree, x) , который нам возвращает деревья <tex>\mathtt{tree1}</tex> и <tex>\rangle mathtt{tree2}</tex>, их подвешиваем к <tex>x</tex>как левое и правое поддеревья соответственно. ===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}(xv) </tex> {{- новый --}} родитель родителя вершины <tex>v</tex> Приведем реализацию <tex> x \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:zigzagTop-Down_Splay.PNGpng|500px512px]] В конце пути производится слияние деревьев <tex>L</tex>, <tex>M</tex> и <tex>R</tex> таким образом, что новым корнем дерева становится вершина с целевым значением. [[file:Top-Down_Assembly.png|Zig512px]] Приведем реализацию. Определим переменные:*<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> {{--zag - }} поворот]]ребра, соединяющего <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()
'''void''' simplified_splay('''Value''' val): '''while''' (t.value !===Merge===val)Merge '''if''' (val <tex>T_1</tex>, <tex>T_2t.value) '''if''' (val </tex>)t. У нас есть два дерева <tex>T_1</tex> и <tex>T_2</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второгоleft. Запускаем Splay от самого большого элемента в дереве <tex>T_1</tex> value) t = rotate_right(t) t = break_right(пусть это элемент <tex>i</tex>t). После этого корень <tex '''else''' '''if''' (val >T_1</tex> содержит элемент <tex>i</tex>, при этом у него нет правого ребёнкаt. Делаем <tex>T_2</tex> правым поддеревом <tex>i</tex> и возвращаем полученное деревоright.value) t = rotate_left(t) t = break_left(t) assemble()
===SplitВремя работы===Split(<tex>i</tex>, <tex>T</tex>). Запускаем Splay от элемента <tex>i</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>i</tex>.===Add===Add(<tex>i</tex>, <tex>T</tex>). Запускаем Split(<tex>i</tex>, <tex>T</tex>), который нам возвращает деревья <tex>T_1</tex> и <tex>T_2</tex>, их подвешиваем к <tex>i</tex> как левое и правое поддеревья соответственно.
== Анализ операции splay ==
[[Амортизационный анализ | Амортизационный анализ]] сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>vx</tex> — это величина, обозначаемая <tex>r(vx)</tex> и равная <tex>\log_2 C(vx)</tex>, где <tex>C(vx)</tex> — количество вершин в поддереве с корнем в <tex>vx</tex>.
{{Лемма
|id = Lemma1
|statement=
Амортизированное время операции splay вершины <tex>vx</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(vx) + 1</tex>
|proof=
Проанализируем каждый шаг операции splay. Пусть <tex>r'</tex> и <tex>r</tex> — ранги вершин после шага и до него соответственно, <tex>up</tex> — предок вершины <tex>vx</tex>, а <tex>wg</tex> — предок <tex>up</tex> (если есть).
Разберём случаи в зависимости от типа шага:
'''Zigzig'''. Поскольку выполнен один поворот, то время амортизированное время выполнения шага <tex>T = 1 + r'(vx) + r'(up) - r(vx) - r(up)</tex> (поскольку только у вершин <tex>vx</tex> и <tex>up</tex> меняется ранг). Ранг вершины <tex>up</tex> уменьшился, поэтому <tex>T \le leqslant 1 + r'(vx) - r(vx)</tex>. Ранг вершины <tex>vx</tex> увеличился, поэтому <tex>r'(vx) - r(vx) \ge geqslant 0</tex>. Следовательно, <tex>T \le leqslant 1 + 3r'(vx) - 3r(vx)</tex>. '''zig-zig'''. Выполнено два поворота, амортизированное время выполнения шага <tex>T = 2 + r'(x) + r'(p) + r'(g) - r(p) - r(x) - r(g)</tex>. Поскольку после поворотов поддерево с корнем в <tex>x</tex> будет содержать все вершины, которые были в поддереве с корнем в <tex>g</tex> (и только их), поэтому <tex>r'(x) = r(g)</tex>. Используя это равенство, получаем: <tex>T = 2 + r'(p) + r'(g) - r(x) - r(p) \leqslant 2 + r'(p) + r'(g) - 2r(x)</tex>, поскольку <tex>r(x) \leqslant r(p)</tex>.
}}
==ЛитератураТеорема о близких запросах в сплей-дереве== {{Теорема |about = о близких запросах в сплей-дереве|statement = Пусть в сплей-дерево сложены ключи <tex> 1, \dotsc, n </tex>. Зафиксируем один из ключей <tex> f </tex>. Пусть выполняется <tex> m </tex> запросов к ключам. Тогда суммарное время на запросы есть <tex> \displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1)) </tex>, где <tex> q_{i} </tex> {{---}} значение в вершине, к которой обращаются в <tex> i </tex>-ый запрос. |proof = Для доказательства теоремы воспользуемся методом потенциалов: <tex> a_{i} = t_{i} + \Phi_{i} - \Phi_{i-1} </tex>. По условию выполняется <tex> m </tex> запросов, следовательно <tex> T = \displaystyle \sum_{i=1}^{m} t_{i} = \sum_{i=1}^{m} \left (a_{i} + \Phi_{i-1} - \Phi_{i} \right) = \sum_{i=1}^{m} a_{i} + \sum_{i=1}^{m} \left ( \Phi_{i-1} - \Phi_{i} \right) </tex> <tex> (\ast) </tex>. Введем следующие обозначения: * Весом узла с ключом <tex> q </tex> будем называть величину <tex> w(q) =\displaystyle \dfrac {1}{\left (\lvert q - f \rvert + 1 \right )^{2}} </tex>. * Размером узла, содержащего ключ <tex> q </tex>, будем называть величину <tex> s(q) = \displaystyle \sum_{y} w(y) </tex>, где <tex> y </tex> {{---}} узлы поддерева с корнем в <tex> q </tex>. * <tex> r(q) = \log_{2}s(q) </tex> {{---}} ранг узла. * Потенциал дерева после <tex> i </tex>-го запроса обозначим как <tex> \Phi_{i} = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q) </tex>. Пусть <tex> W </tex> {{---}} вес дерева. Тогда <tex> W = \displaystyle \sum_{q=1}^{n} w(q) = \sum_{q=1}^{n} \dfrac {1}{\left (\lvert q - f \rvert + 1 \right)^{2}} \leqslant 2 \cdot \sum_{q=1}^{+\infty} \dfrac {1}{ \left ( \lvert q - f \rvert + 1 \right)^{2}} = O(1) </tex>. Последнее верно, так как при фиксированном <tex> f </tex>, начиная с некоторого места, а именно <tex> q = f </tex>, ряд сходится. Из определения размера узла следует, что <tex> w(q) \leqslant s(q) \leqslant W </tex>. Также заметим, что для любого <tex> q </tex> от <tex> 1 </tex> до <tex> n </tex> верно, что <tex> w(q) \geqslant \displaystyle \dfrac {1}{n^{2}} </tex>, так как максимальное значение знаменателя в определении <tex> w(q) </tex> достигается при <tex> q = n </tex> и <tex> f = 1 </tex> или наоборот. Тогда, воспользовавшись полученными оценками, найдем изменение потенциала сплей-дерева после <tex> m </tex> запросов: <tex>\displaystyle \sum_{i=1}^{m} \left ( \Phi_{i-1} - \Phi_{i} \right) = \Phi_{0} - \Phi_{m} \leqslant \sum_{q=1}^{n} \log_{2} W - \sum_{q=1}^{n} \log_{2}w(q) = \sum_{q=1}^{n} \log_{2} \dfrac {W}{w(q)} </tex> <tex> \displaystyle = O \Biggl(\sum_{q=1}^{n} \log_{2} n^{2}\Biggr) = </tex> <tex> \displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left (n \log_{2}n\right) </tex>. Первое неравенство верно, так как максимальное значение потенциала достигается при <tex> s(q) = W </tex>, а минимальное при <tex> s(q) = w(q) </tex>, а значит изменение потенциала не превышает разности этих величин. Обозначим за <tex> t </tex> корень сплей-дерева. Тогда, воспользовавшись вышеуказанной [[# Lemma1|леммой]] (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что <tex> \displaystyle a_{i} = 3 \cdot \left ( r(t) - r(q_{i}) \right) + 1 = O\left (\log_{2} \dfrac {s(t)}{s\left (q_{i}\right)}\right) + 1 = O\left (\log_{2} \dfrac {W}{w(q_{i})}\right) + 1 = </tex> <tex> O\left (\log_{2} \left (W \cdot \left (\lvert q_{i} - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left (\log_{2} \left (\lvert q_{i} - f \rvert + 1 \right) \right ) + 1 </tex>. Докажем, что данное определение потенциала удовлетворяет условию [[Амортизационный анализ|теоремы о методе потенциалов]]. Для любого <tex> i </tex> верно, что <tex> a_{i} = O(\log_{2}(n)) </tex>, так как <tex> \lvert q_{i} - f \rvert + 1 \leqslant n </tex>, и <tex> \Phi_{i} = O(n\log_{2}(n)) </tex>, как было показано выше. Так как количество операций на запрос <tex>k = O(n) </tex>, то <tex> a_{i} = O(f(k,n)) </tex> и <tex> \Phi_{i} = O(kf(k,n)) </tex>, где <tex> f(k,n) </tex> {{---}} функция из теоремы о методе потенциалов, равная в данном случае <tex> \log_{2}n </tex>. Следовательно, потенциал удовлетворяет условию теоремы. Тогда, подставляя найденные значения в формулу <tex> (\ast) </tex>, получаем, что <tex>T=\displaystyle \sum_{i=1}^{m} \left ( O \left ( \log_{2} \left ( \lvert q_{i} - f \rvert + 1 \right) \right) + 1 \right ) + O\left ( n \log_{2} n \right) = </tex> <tex> \displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_{2} \left ( \lvert q_{i} - f \rvert + 1 \right) \right)</tex>. }} Данная теорема показывает, что сплей-деревья поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу. ==Splay-деревья по неявному ключу==Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья. == См. также ==* [[2-3 дерево]]* [[B-дерево]]* [[B+-дерево]]* [[АВЛ-дерево]]* [[Красно-черное дерево]] ==Источники информации==*[[wikipedia:en:Splay_Tree|Википедия {{---}} Splay tree]]*[http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf Sleator, Daniel SleatorD.; Tarjan, Robert Tarjan E."A data structure for dynamic treesSelf-Adjusting Binary Search Trees"] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Деревья поиска ]]