Изменения

'''Сплей-дерево ''' (англ. ''Splay-tree)''' {{---}} ) — это [[Дерево поиска, наивная реализация | двоичное дерево поиска, позволяющее ]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983 </tex> году. Основной идеей работы дерева является перетаскивание найденной вершины в корень почти после каждой операции==Эвристики==Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Для Этого мы можем добиться, используя различные эвристики:* '''Move to Root''' {{---}} совершает повороты вокруг ребра <tex> p(x, p) </tex> - предка вершины , где <tex> x </tex> эвристика "Move to Root" совершает повороты вокруг ребра — найденная вершина, <tex> \langle x, p(x) \rangle </tex>— ее предок, пока <tex> x </tex> не окажется корнем дерева. Однако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет <tex> \Omega(n) </tex>.Данный поворот аналогичен zig * '''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|750px]] [[file:Splay.png|750px]] 

Данная операция занимает ===splay(tree, x)==="splay" делится на <tex>3</tex> случая:====zig====Если <tex>p</tex> — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex> O(dx, p) </tex> времени, где делая <tex> d x</tex> - длина пути от корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex> x </tex> до корнябыла нечетной. [[file:Зиг. В результате этой операции png|800px|zig — поворот]]====zig-zig====Если <tex>p</tex> — не корень дерева, а <tex> x </tex> становится корнем дереваи <tex>p</tex> — оба левые или оба правые дети, то делаем поворот ребра <tex>(p, g)</tex>, где <tex>g</tex> отец <tex>p</tex>, а расстояние до корня от каждой вершины сокращается примерно пополамзатем поворот ребра <tex>(x, что связано с разделением случаев "p)</tex>. [[file:Зиг_зиг.png|800px|zig-zig" — поворот]]====zig-zag====Если <tex>p</tex> — не корень дерева и "<tex>x</tex> — левый ребенок, а <tex>p</tex> — правый, или наоборот, то делаем поворот вокруг ребра <tex>(x, p)</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.

===Findmerge(tree1, tree2)===Эта операция выполняется как для обычного бинарного У нас есть два дерева <tex>\mathtt{tree1}</tex> и <tex>\mathtt{tree2}</tex>, причём подразумевается, что все элементы первого дереваменьше элементов второго. Запускаем splay от самого большого элемента в дереве <tex>\mathtt{tree1}</tex> (пусть это элемент <tex>i</tex>). После этого корень <tex>\mathtt{tree1}</tex> содержит элемент <tex>i</tex>, только после нее запускается операция Splayпри этом у него нет правого ребёнка. Делаем <tex>\mathtt{tree2}</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево.

===Mergesplit(tree, x)===Merge(Запускаем splay от элемента <tex>T_1x</tex>, <tex>T_2</tex>). У нас есть и возвращаем два дерева <tex>T_1</tex> и <tex>T_2</tex>, причём подразумеваетсяполученные отсечением правого или левого поддерева от корня, что все элементы первого дерева меньше элементов второго. Запускаем Splay в зависимости от самого большого элемента в дереве <tex>T_1</tex> (пусть это элемент <tex>i</tex>). После этого того, содержит корень <tex>T_1</tex> содержит элемент <tex>i</tex>больше или не больше, при этом у него нет правого ребёнка. Делаем <tex>T_2</tex> правым поддеревом чем <tex>ix</tex> и возвращаем полученное дерево.

===Split===Splitadd(<tex>i</tex>tree, <tex>T</tex>x). Запускаем Splay от элемента <tex>i</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>i</tex>.===Add===Add(<tex>i</tex>, <tex>T</tex>). Запускаем Splitsplit(<tex>i</tex>tree, <tex>T</tex>x), который нам возвращает деревья <tex>T_1\mathtt{tree1}</tex> и <tex>T_2\mathtt{tree2}</tex>, их подвешиваем к <tex>ix</tex> как левое и правое поддеревья соответственно.

===Removeremove(tree, x)=== Remove(<tex>i</tex>, <tex>T</tex>). Запускаем Splay splay от <tex>ix</tex>-го элемента и возвращаем Merge от его детей.

== Анализ операции splay ==

[[Амортизационный анализ | Амортизационный анализ]] сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>vx</tex> — это величина, обозначаемая <tex>r(vx)</tex> и равная <tex>\log_2 C(vx)</tex>, где <tex>C(vx)</tex> — количество вершин в поддереве с корнем в <tex>vx</tex>.

Амортизированное время операции splay вершины <tex>vx</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(vx) + 1</tex>

Проанализируем каждый шаг операции 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>. Далее, так как <tex>r'(p) \leqslant r'(x)</tex>, получаем, что <tex>T \leqslant 2 + r'(x) + r'(g) - 2r(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>.

'''Zig-zig'''. Выполнено два поворотаИз рисунка видно, амортизированное время выполнения шага что <tex>T = 2 + rC'(vg) + r'C(ux) + r\leqslant C'(w) - r(u) - r(v) - r(wx)</tex>, значит, сумма выражений под логарифмами не превосходит единицы. Поскольку после поворотов поддерево с корнем в Далее, рассмотрим сумму логарифмов <tex>v\log_2 a + \log_2 b = \log_2 ab</tex> будет содержать все вершины, которые были в поддереве с корнем в . При <tex>wa + b \leqslant 1</tex> (и только их), поэтому произведение <tex>r'(v) = r(w)ab</tex>. Используя это равенство, получаем: по неравенству между средними не превышает <tex>T = 2 + r'(u) + r'(w) - r(v) - r(u) \le 2 + r'(u) + r'(w) - 2r(v)dfrac{1}{4}</tex>. А поскольку логарифм — функция возрастающая, поскольку то <tex>r(v) \le r(u)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'(ux) \le leqslant r'(vp)</tex>, получаем, что то <tex>T \le leqslant 2 + r'(vp) + r'(wg) - 2r(vx)</tex>.

Мы утверждаем, что эта сумма не превосходит <tex>32(r'(vx) - r(vx))</tex>, то есть, что <tex>r'(vp) + r'(wg) - 2r'(vx) \le leqslant -2</tex>. Преобразуем полученное выражение следующим образом: Но, поскольку <tex>(r(v) - r'(v)p) + (r'(wg) - r2r'(v)x) = \log_2 \fracdfrac {C'(vp)}{C'(vx)} + \log_2 \fracdfrac {C'(wg)}{C'(vx)}\leqslant -2</tex>- аналогично доказанному ранее, что и требовалось доказать.

Из рисунка видноИтого, получаем, что амортизированное время шага zig-zag не превосходит <tex>C2(r'(wx) + C- r(vx)) \le Cleqslant 3(r'(vx) - r(x))</tex>. Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, значит, сумма выражений под логарифмами то суммарное время не превосходит единицы. Далее, рассмотрим сумму логарифмов будет превосходить <tex>\log_2 3r(t) - 3r(x ) + \log_2 y = \log_2 xy1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом). При Тогда суммарное время работы splay <tex>T_{splay} \leqslant 3\log_2 N - 3\log_2 C(x ) + y 1 = O(\le 1</tex> произведение <tex>xy</tex> по неравенству между средними не превышает <tex>1/4log_2 N)</tex>. А поскольку логарифм - функция возрастающая, то где <tex>\log_2 xy \le -2N</tex>, что и является требуемым неравенством— число элементов в дереве.}}

'''Zig== Статическая оптимальность сплей-дерева =={{Теорема|statement=Если к ключам <tex>1 \ldots n</tex>, сложенным в сплей-zag'''. Выполнено два поворотадерево выполняется <tex>m</tex> запросов, амортизированное время выполнения шага к <tex>i</tex>T = 2 + r'(v) + r'(u) + r'(w) - r(v) - r(u) - r(w)му ключу осуществляется <tex>k_i</tex>. Поскольку запросов, где <tex>r'(v) = r(w)k_i > 0</tex>, то суммарное время работы не превышает <tex>T = 2 + r'O(u) + r'm \cdot H(wp_1, p_2, \ldots , p_n) - r(v) - r(u)</tex>. Далее, так как где <tex>p_i = k_i / m</tex>, <tex>r(v) \le r(u)H</tex>— шенноновская энтропия|proof=Известно, то что <tex>T H(p_1, p_2, \le 2 + r'(u) + r'(wldots , p_n) = - 2rc \cdot \displaystyle \sum_{i=1}^n (vp_i \cdot \log_{2}p_i)</tex>{{---}} [[Энтропия_случайного_источника | шенноновская энтропия]].

Мы утверждаем, что эта сумма не превосходит Пусть <tex>2s(r'(vx) - r= \displaystyle \sum_{y} w(v)y)</tex>, то есть, что {{---}} количество вершин в поддереве с корнем в <tex>r'(u) + r'(w) - 2r'(v) \le -2x</tex>. Но, поскольку А <tex>r'(u) + r'(w) - 2r'(vx) = \log_2 \fraclog_{C'(u)}{C'(v)} + \log_2 \frac{C'(w)2}{C's(vx)} \le -2</tex> {{--- аналогично доказанному ранее, что и требовалось доказать}} ранг вершины.

Итого, получаемОбозначим за <tex>r</tex> корень <tex>splay</tex>-дерева.Из предыдущей теоремы известно, что амортизированное время шага zig-zag не превосходит <tex>2(r'(v) - r(v)) a_{splay} \le leqslant 1+3(r'(vr) - r(vx))</tex>.

Поскольку за время выполнения операции splay выполняется не более одного шага типа zigПусть <tex dpi="130">w(x_i) = p_i =</tex> <tex dpi="180"> {k_i \over m}</tex>, то суммарное время не будет превосходить тогда <tex dpi="130">k_i = p_i \cdot m</tex>.<br><tex>m+3mr(r)-3 \displaystyle \sum_{i=1}^n k_ir(x_i) \leqslant m+3mr(r)-3 \displaystyle \sum_{i+1}^n k_i\log_{2}w(x_i) =</tex> <tex>m+3mr(r)-3 \displaystyle \sum_{i=1}^n (p_i\cdot m\cdot \log_{2}p_i) = m(1+3r(tr)-3 \displaystyle \sum_{i=1}^n p_i\log_{2}p_i) = (*) </tex>Так как вершина <tex>r</tex> {{---}} корень <tex>splay</tex>- 3rдерева, то очевидно, что <tex>s = \displaystyle \sum_{y} w(vy) + = 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются следовательно <tex>r(r) = \log_{2}s(r)=0</tex>. Поэтому <tex>(*) = m(1+H(p_1,\ldots ,p_n)) = O(mH(входят в сумму как с плюсомp_1,\ldots , так и с минусомp_n))</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"]