Изменения

Перейти к: навигация, поиск

Splay-дерево

19 402 байта добавлено, 7 октябрь
find(tree, x)
'''Сплей-дерево ''' (англ. ''Splay-tree)''' {{---}} ) — это [[Дерево поиска, наивная реализация | двоичное дерево поиска, позволяющее ]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983 </tex> году.
Очевидно, что для ==Эвристики==Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя эвристику "различные эвристики:* '''Move to Root", которая ''' {{---}} совершает повороты вокруг ребра <tex>(x, p)</tex>, где <tex>x</tex> - найденная вершина, а <tex>p</tex> - ее предок, пока <tex>x</tex> не окажется корнем дерева. Но эта эвристика не даст нам никакого улучшения времени работы. Поэтому мы будем использовать операцию "Splay" для перемещения Однако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет <tex>x\Omega(n) </tex> в корень.* '''Splay''' {{---}} также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.
=Операции со '''Пример''': При последовательном использовании операций "move to root" для вершин <tex>A</tex> и <tex>B</tex> требуется по <tex>6</tex> поворотов, в то время как при использовании операции "splay-деревом=" для вершины <tex>B</tex> достаточно <tex>3</tex> поворотов.
==Splay(Tree, x)=="Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока <tex>x</tex> не является корнем дерева выполняется следующее[[file:===Zig===Если <tex>p</tex> - корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетнойMove_to_root.png|750px]]
[[file:ZigSplaySplay.gifpng|500px|Zig - поворот750px]]===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:ZigZigSplay.gif|500px|Zig-zig - поворот]]===ZigОперации со splay-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===splay(tree, x)==="splay" делится на <tex>3</tex> случая:ZigZagSplay====zig====Если <tex>p</tex> — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетной.gif|500px|Zig-zag - поворот]]
Данная операция занимает [[file:Зиг.png|800px|zig — поворот]]====zig-zig====Если <tex>p</tex> — не корень дерева, а <tex>x</tex> и <tex>p</tex> — оба левые или оба правые дети, то делаем поворот ребра <tex>O(dp, g)</tex> времени, где <tex>dg</tex> - длина пути от отец <tex>xp</tex> до корня. В результате этой операции , а затем поворот ребра <tex>(x, p)</tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
[[file:Зиг_зиг.png|800px|zig-zig — поворот]]====zig-zag=Find===Если <tex>p</tex> — не корень дерева и <tex>x</tex> — левый ребенок, а <tex>p</tex> — правый, или наоборот, то делаем поворот вокруг ребра <tex>(Treex, p)</tex>, а затем поворот нового ребра <tex>(x, g)==Эта операция выполняется как для обычного бинарного дерева</tex>, только после нее запускается операция Splayгде <tex>g</tex> — бывший родитель <tex>p</tex>.
==Merge(Tree1, Tree2)==У нас есть два дерева <tex>Tree1</tex> и <tex>Tree2</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay от самого большого элемента в дереве <tex>Tree1</tex> (пусть это элемент <tex>i</tex>). После этого корень <tex>Tree1</tex> содержит элемент <tex>i</tex>, при этом у него нет правого ребёнка. Делаем <tex>Tree2</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево[[file:Зиг_заг2.png|900px|zig-zag — поворот]]
==SplitДанная операция занимает <tex>O(Treed)</tex> времени, x)==Запускаем Splay от элемента где <tex>xd</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева — длина пути от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>x</tex>до корня.
==Add=find(Treetree, x)===Запускаем Split(TreeЭта операция выполняется как для обычного [[Дерево поиска, x), который нам возвращает деревья <tex>Tree1</tex> и <tex>Tree2</tex>наивная реализация|бинарного дерева поиска]], их подвешиваем к <tex>x</tex> как левое и правое поддеревья соответственнотолько после нее запускается операция splay.
==Remove=merge(Treetree1, xtree2)== =У нас есть два дерева <tex>\mathtt{tree1}</tex> и <tex>\mathtt{tree2}</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay splay от самого большого элемента в дереве <tex>\mathtt{tree1}</tex> (пусть это элемент <tex>i</tex>). После этого корень <tex>\mathtt{tree1}</tex> содержит элемент <tex>i</tex>, при этом у него нет правого ребёнка. Делаем <tex>x\mathtt{tree2}</tex> правым поддеревом <tex>i</tex> элемента и возвращаем Merge от его детейполученное дерево.
=Анализ операции ==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== ===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>.
{{Лемма
|id = Lemma1
|statement=
Амортизированное время операции splay вершины <tex>x</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(x) + 1</tex>
Разберём случаи в зависимости от типа шага:
'''Zigzig'''. Поскольку выполнен один поворот, то время амортизированное время выполнения шага <tex>T = 1 + r'(x) + r'(p) - r(x) - r(p)</tex> (поскольку только у вершин <tex>x</tex> и <tex>p</tex> меняется ранг). Ранг вершины <tex>p</tex> уменьшился, поэтому <tex>T \le leqslant 1 + r'(x) - r(x)</tex>. Ранг вершины <tex>x</tex> увеличился, поэтому <tex>r'(x) - r(x) \ge geqslant 0</tex>. Следовательно, <tex>T \le leqslant 1 + 3r'(x) - 3r(x)</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 =  Для доказательства теоремы воспользуемся методом потенциалов:  <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>.
'''Zig-zig'''. Выполнено два поворотаПервое неравенство верно, амортизированное время выполнения шага так как максимальное значение потенциала достигается при <tex>T = 2 + r's(xq) + r'(p) + r'(g) - r(p) - r(x) - r(g)</tex>. Поскольку после поворотов поддерево с корнем в <tex>x</tex> будет содержать все вершины, которые были в поддереве с корнем в <tex>g= W </tex> (и только их), поэтому а минимальное при <tex>r's(xq) = rw(gq)</tex>. Используя это равенство, получаем: <tex>T = 2 + r'(p) + r'(g) - r(x) - r(p) \le 2 + r'(p) + r'(g) - 2r(x)</tex>, поскольку <tex>r(x) \le r(p)</tex>а значит изменение потенциала не превышает разности этих величин.
Далее, так как Обозначим за <tex>r'(p) \le r'(x)t </tex>корень сплей-дерева. Тогда, воспользовавшись вышеуказанной [[#Lemma1|леммой]] (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что <tex>T \le 2 + r'(x) + r'(g) - 2r(x)</tex>.
Мы утверждаем, что эта сумма не превосходит <tex>\displaystyle a_{i} = 3\cdot \left (r'(xt) - r(xq_{i}) \right)+ 1 = O\left (\log_{2} \dfrac {s(t)</tex>, то есть, что <tex>r}{s\left (xq_{i}\right)}\right) + r'1 = O\left (g) - 2r'\log_{2} \dfrac {W}{w(xq_{i}) }\le -2right) + 1 = </tex>. Преобразуем полученное выражение следующим образом: <tex>O\left (\log_{2} \left (rW \cdot \left (x) \lvert q_{i} - r'(x)) f \rvert + (r'(g1 \right) - r'(x^{2} \right )\right ) + 1 = O\log_2 left (\fraclog_{C2} \left (x)}\lvert q_{C'(x)i} - f \rvert + 1 \log_2 right) \frac{C'(gright )}{C'(x)}+ 1 </tex>.
Из рисунка видноДокажем, что <tex>C'(g) + C(x) \le C'(x)</tex>, значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов <tex>\log_2 a + \log_2 b = \log_2 ab</tex>. При <tex>a + b \le 1</tex> произведение <tex>ab</tex> по неравенству между средними не превышает <tex>1/4</tex>. А поскольку логарифм - функция возрастающая, то <tex>\log_2 ab \le -2</tex>, что и является требуемым неравенствомданное определение потенциала удовлетворяет условию [[Амортизационный анализ|теоремы о методе потенциалов]].
'''Zig-zag'''. Выполнено два поворотаДля любого <tex> i </tex> верно, амортизированное время выполнения шага что <tex>T a_{i} = O(\log_{2 + r'}(xn) + r'(p) </tex>, так как <tex> \lvert q_{i} - f \rvert + r'1 \leqslant n </tex>, и <tex> \Phi_{i} = O(g) - rn\log_{2}(xn) - r(p) - r(g)</tex>, как было показано выше. Поскольку Так как количество операций на запрос <tex>r'(x) k = rO(gn)</tex>, то <tex>T a_{i} = 2 + r'O(f(pk,n)) + r'</tex> и <tex> \Phi_{i} = O(g) - rkf(xk,n) - r(p)</tex>. Далее, так как где <tex>rf(x) \le r(pk,n)</tex>{{---}} функция из теоремы о методе потенциалов, то равная в данном случае <tex>T \le log_{2 + r'(p) + r'(g) - 2r(x)}n </tex>. Следовательно, потенциал удовлетворяет условию теоремы.
Мы утверждаемТогда, что эта сумма не превосходит подставляя найденные значения в формулу <tex>2(r'(x) - r(x)\ast)</tex>, то есть, что <tex>r'(p) + r'(g) - 2r'(x) \le -2</tex>. Но, поскольку <tex>r'(p) + r'(g) - 2r'(x) = \log_2 \frac{C'(p)}{C'(x)} + \log_2 \frac{C'(g)}{C'(x)} \le -2</tex> - аналогично доказанному ранее получаем, что и требовалось доказать.
Итого, получаем, что амортизированное время шага zig-zag не превосходит <tex>T=\displaystyle \sum_{i=1}^{m} \left ( O \left ( \log_{2} \left (r'(x\lvert q_{i} - f \rvert + 1 \right) \right) + 1 \right ) - r+ O\left (x)n \log_{2} n \right) = </tex> <tex> \displaystyle O \le 3left (r'n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_{2} \left (x) \lvert q_{i} - r(xf \rvert + 1 \right)\right)</tex>.
Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(x) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).
}}
=SplayДанная теорема показывает, что сплей-деревья по неявному поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу=.
Здесь ==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"]
Анонимный участник

Навигация