286
правок
Изменения
Нет описания правки
'''Сплей-дерево ''' (англ. ''Splay-tree)''' {{---}} ) — это [[Дерево поиска, наивная реализация | двоичное дерево поиска, позволяющее ]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983 </tex> году. Основной идеей работы дерева является эвристика "Move to Root", перетаскивающая найденную вершину в корень почти после каждой операции. Для p(x) - предка вершины x "Move to Root" совершает повороты вокруг ребра (x, p(x)), пока x не окажется корнем дерева.
[[file:ZigZigSplayMove_to_root.gifpng|500px|Zig-zig - поворот750px]]===Zig-Zag===Если p - не корень дерева и x - левый ребенок, а p - правый, или наоборот, то делаем поворот вокруг ребра (x, p), а затем поворот нового ребра (x, g), где g - бывший родитель p.
[[file:ZigZagSplaySplay.gifpng|500px|Zig-zag - поворот750px]]
==Find=splay(keytree, x)==="splay" делится на <tex>3</tex> случая:Эта операция выполняется как для обычного бинарного ====zig====Если <tex>p</tex> — корень деревас сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только после нее запускается операция Splayодин раз в конце, если изначальная глубина <tex>x</tex> была нечетной.
[[file:Зиг.png|800px|zig — поворот]]====zig-zig==Merge(Tree1, Tree2)==У нас есть два Если <tex>p</tex> — не корень дерева Tree1 , а <tex>x</tex> и Tree2<tex>p</tex> — оба левые или оба правые дети, причём подразумеваетсято делаем поворот ребра <tex>(p, что все элементы первого дерева меньше элементов второго. Запускаем Splay от самого большого элемента в дереве Tree1 g)</tex>, где <tex>g</tex> отец <tex>p</tex>, а затем поворот ребра <tex>(пусть это элемент ix, p). После этого корень Tree1 содержит элемент i, при этом у него нет правого ребёнка. Делаем Tree2 правым поддеревом i и возвращаем полученное дерево</tex>.
[[file:Зиг_зиг.png|800px|zig-zig — поворот]]====zig-zag==Split(key, Tree)==Запускаем Splay от элемента key Если <tex>p</tex> — не корень дерева и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня<tex>x</tex> — левый ребенок, в зависимости от тогоа <tex>p</tex> — правый, содержит корень элемент больше или не большенаоборот, чем key.==Addто делаем поворот вокруг ребра <tex>(keyx, Treep)==Запускаем Split</tex>, а затем поворот нового ребра <tex>(keyx, Treeg)</tex>, который нам возвращает деревья Tree_1 и Tree_2, их подвешиваем к key как левое и правое поддеревья соответственногде <tex>g</tex> — бывший родитель <tex>p</tex>.
===find(tree, x)===Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного дерева]], только после нее запускается операция splay. ===merge(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>, при этом у него нет правого ребёнка. Делаем <tex>\mathtt{tree2}</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево. ===split(tree, x)===Запускаем splay от элемента <tex>x</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>x</tex>. ===add(tree, x)===Запускаем split(tree, x), который нам возвращает деревья <tex>\mathtt{tree1}</tex> и <tex>\mathtt{tree2}</tex>, их подвешиваем к <tex>x</tex> как левое и правое поддеревья соответственно. ===remove(tree, x)=== Запускаем splay от <tex>x</tex> элемента и возвращаем Merge от его детей. ==Анализ операции 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>. Далее, так как <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>. Из рисунка видно, что <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>. Мы утверждаем, что эта сумма не превосходит <tex>2(r'(x) - r(x))</tex>, то есть, что <tex>r'(p) + r'(g) - 2r'(x) \leqslant -2</tex>. Но, поскольку <tex>r'(p) + r'(g) - 2r'(x) = \log_2 \dfrac {C'(p)}{C'(x)} + \log_2 \dfrac {C'(g)}{C'(x)} \leqslant -2</tex> - аналогично доказанному ранее, что и требовалось доказать. Итого, получаем, что амортизированное время шага zig-zag не превосходит <tex>2(r'(x) - r(x)) \leqslant 3(r'(x) - r(x))</tex>. Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(x) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом). Тогда суммарное время работы splay <tex>T_{splay} \leqslant 3\log_2 N - 3\log_2 C(x) + 1 = O(\log_2 N)</tex>, где <tex>N</tex> — число элементов в дереве.}} == Статическая оптимальность сплей-дерева =={{Теорема|statement=Если к ключам <tex>1 \ldots n</tex>, сложенным в сплей-дерево выполняется <tex>m</tex> запросов, к <tex>i</tex>-му ключу осуществляется <tex>k_i</tex> запросов, где <tex>k_i > 0</tex>, то суммарное время работы не превышает <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> {{---}} [[Энтропия_случайного_источника | шенноновская энтропия]]. Пусть <tex>s(x) = \displaystyle \sum_{y} w(y)</tex> {{---}} количество вершин в поддереве с корнем в <tex>x</tex>. А <tex>r(x) = \log_{2} s(x)</tex> {{---}} ранг вершины. Обозначим за <tex>r</tex> корень <tex>splay</tex>-дерева.Из предыдущей теоремы известно, что <tex>a_{splay} \leqslant 1+3(r(r)-r(x))</tex> Пусть <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(r)-3 \displaystyle \sum_{i=1}^n p_i\log_{2}p_i) = (*)</tex>Так как вершина <tex>r</tex> {{---}} корень <tex>splay</tex>-дерева, то очевидно, что <tex>s = \displaystyle \sum_{y} w(y) = 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 =
}}
Данная теорема показывает, что сплей-деревья поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу. ==ЛитератураSplay-деревья по неявному ключу==Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья. == См. также ==* [[2-3 дерево]]* [[B-дерево]]* [[B+-дерево]]* [[АВЛ-дерево]]* [[Красно-черное дерево]]
==Источники информации==*[http[wikipedia://en.wikipedia.org/wiki/Splay_tree :Splay_Tree|Википедия {{---}} Splay tree - Википедия]]
*[http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf Sleator, Daniel D.; Tarjan, Robert E."Self-Adjusting Binary Search Trees"]