Splay-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 43 промежуточные версии 15 участников)
Строка 1: Строка 1:
'''Сплей-дерево (Splay-tree)''' {{---}} двоичное дерево поиска, позволяющее находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
+
'''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983</tex> году.
  
Очевидно, что для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя эвристику "Move to Root", которая  совершает повороты вокруг ребра <tex>(x, p)</tex>, где <tex>x</tex> - найденная вершина, а <tex>p</tex> - ее предок, пока <tex>x</tex> не окажется корнем дерева. Но эта эвристика не даст нам никакого улучшения времени работы. Поэтому мы будем использовать операцию "Splay" для перемещения <tex>x</tex> в корень.
+
==Эвристики==
 +
Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя различные эвристики:
 +
* '''Move to Root''' {{---}} совершает повороты вокруг ребра <tex>(x, p)</tex>, где <tex>x</tex> найденная вершина, <tex>p</tex> ее предок, пока <tex>x</tex> не окажется корнем дерева. Однако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет <tex> \Omega(n) </tex>.
 +
* '''Splay''' {{---}} также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.
  
=Операции со splay-деревом=
+
'''Пример''': При последовательном использовании операций "move to root" для вершин <tex>A</tex> и <tex>B</tex> требуется по <tex>6</tex> поворотов, в то время как при использовании операции "splay" для вершины <tex>B</tex> достаточно <tex>3</tex> поворотов.
  
==Splay(Tree, x)==
+
[[file:Move_to_root.png|750px]]
"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов.  Пока <tex>x</tex> не является корнем дерева выполняется следующее:
 
===Zig===
 
Если <tex>p</tex> - корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетной.
 
  
[[file:ZigSplay.gif|500px|Zig - поворот]]
+
[[file:Splay.png|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 - поворот]]
+
==Операции со splay-деревом==
===Zig-Zag===
 
Если <tex>p</tex> - не корень дерева и <tex>x - левый ребенок, а <tex>p</tex> - правый, или наоборот, то делаем поворот вокруг ребра <tex>(x, p)</tex>, а затем поворот нового ребра <tex>(x, g)</tex>, где <tex>g</tex> - бывший родитель <tex>p</tex>.
 
  
[[file:ZigZagSplay.gif|500px|Zig-zag - поворот]]
+
===splay(tree, x)===
 +
"splay" делится на <tex>3</tex> случая:
 +
====zig====
 +
Если <tex>p</tex> — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетной.
  
Данная операция занимает <tex>O(d)</tex> времени, где <tex>d</tex> - длина пути от <tex>x</tex> до корня. В результате этой операции <tex>x</tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
+
[[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>.
  
==Find(Tree, key)==
+
[[file:Зиг_зиг.png|800px|zig-zig — поворот]]
Эта операция выполняется как для обычного бинарного дерева, только после нее запускается операция Splay.
+
====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>.
  
==Merge(Tree1, Tree2)==
+
[[file:Зиг_заг2.png|900px|zig-zag — поворот]]
У нас есть два дерева <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> и возвращаем полученное дерево.
 
  
==Split(Tree, x)==
+
Данная операция занимает <tex>O(d)</tex> времени, где <tex>d</tex> — длина пути от <tex>x</tex> до корня.
Запускаем Splay от элемента <tex>x</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>x</tex>.
 
  
==Add(Tree, x)==
+
===find(tree, x)===
Запускаем Split(Tree, x), который нам возвращает деревья <tex>Tree</tex>1 и <tex>Tree2</tex>, их подвешиваем к <tex>x</tex> как левое и правое поддеревья соответственно.
+
Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного дерева поиска]], только после нее запускается операция splay.
  
==Remove(Tree, x)==
+
===merge(tree1, tree2)===
Запускаем Splay от <tex>x</tex> элемента и возвращаем Merge от его детей.
+
У нас есть два дерева <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> и возвращаем полученное дерево.
  
=Анализ операции splay=
+
===split(tree, x)===
 +
Запускаем splay от элемента <tex>x</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>x</tex>.
  
Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>x</tex> — это величина, обозначаемая <tex>r(x)</tex> и равная <tex>\log_2 C(x)</tex>, где <tex>C(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.right) = 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=
 
|statement=
 
Амортизированное время операции splay вершины <tex>x</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(x) + 1</tex>
 
Амортизированное время операции splay вершины <tex>x</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(x) + 1</tex>
Строка 50: Строка 217:
 
Разберём случаи в зависимости от типа шага:
 
Разберём случаи в зависимости от типа шага:
  
'''Zig'''. Поскольку выполнен один поворот, то время амортизированное время выполнения шага <tex>T = 1 + r'(x) + r'(p) - r(x) - r(p)</tex> (поскольку только у вершин <tex>x</tex> и <tex>p</tex> меняется ранг). Ранг вершины <tex>p</tex> уменьшился, поэтому <tex>T \le 1 + r'(x) - r(x)</tex>. Ранг вершины <tex>x</tex> увеличился, поэтому <tex>r'(x) - r(x) \ge 0</tex>. Следовательно, <tex>T \le 1 + 3r'(x) - 3r(x)</tex>.
+
'''zig'''. Поскольку выполнен один поворот, то амортизированное время выполнения шага <tex>T = 1 + r'(x) + r'(p) - r(x) - r(p)</tex> (поскольку только у вершин <tex>x</tex> и <tex>p</tex> меняется ранг). Ранг вершины <tex>p</tex> уменьшился, поэтому <tex>T \leqslant  1 + r'(x) - r(x)</tex>. Ранг вершины <tex>x</tex> увеличился, поэтому <tex>r'(x) - r(x) \geqslant  0</tex>. Следовательно, <tex>T \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'(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) \le 2 + r'(p) + r'(g) - 2r(x)</tex>, поскольку <tex>r(x) \le r(p)</tex>.
+
Первое неравенство верно, так как максимальное значение потенциала достигается при <tex> s(q) = W </tex>, а минимальное при <tex> s(q) = w(q) </tex>, а значит изменение потенциала не превышает разности этих величин.  
  
Далее, так как <tex>r'(p) \le r'(x)</tex>, получаем, что <tex>T \le 2 + r'(x) + r'(g) - 2r(x)</tex>.
+
Обозначим за <tex> t </tex> корень сплей-дерева. Тогда, воспользовавшись вышеуказанной [[#Lemma1|леммой]] (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что
  
Мы утверждаем, что эта сумма не превосходит <tex>3(r'(x) - r(x))</tex>, то есть, что <tex>r(x) + r'(g) - 2r'(x) \le -2</tex>. Преобразуем полученное выражение следующим образом: <tex>(r(x) - r'(x)) + (r'(g) - r'(x)) = \log_2 \frac{C(x)}{C'(x)} + \log_2 \frac{C'(g)}{C'(x)}</tex>.
+
<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>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>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) \le r(p)</tex>, то <tex>T \le 2 + r'(p) + r'(g) - 2r(x)</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>2(r'(x) - r(x))</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> - аналогично доказанному ранее, что и требовалось доказать.
+
Тогда, подставляя найденные значения в формулу <tex> (\ast) </tex>, получаем, что  
  
Итого, получаем, что амортизированное время шага zig-zag не превосходит <tex>2(r'(x) - r(x)) \le 3(r'(x) - r(x))</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 выполняется не более одного шага типа 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://en.wikipedia.org/wiki/Splay_tree Википедия - Splay tree]
+
==Источники информации==
 +
*[[wikipedia:en: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"]
 
*[http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf Sleator, Daniel D.; Tarjan, Robert E."Self-Adjusting Binary Search Trees"]
  

Текущая версия на 19:30, 4 сентября 2022

Сплей-дерево (англ. Splay-tree) — это двоичное дерево поиска. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в [math]1983[/math] году.

Эвристики

Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя различные эвристики:

  • Move to Root — совершает повороты вокруг ребра [math](x, p)[/math], где [math]x[/math] — найденная вершина, [math]p[/math] — ее предок, пока [math]x[/math] не окажется корнем дерева. Однако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет [math] \Omega(n) [/math].
  • Splay — также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.

Пример: При последовательном использовании операций "move to root" для вершин [math]A[/math] и [math]B[/math] требуется по [math]6[/math] поворотов, в то время как при использовании операции "splay" для вершины [math]B[/math] достаточно [math]3[/math] поворотов.

Move to root.png

Splay.png

Операции со splay-деревом

splay(tree, x)

"splay" делится на [math]3[/math] случая:

zig

Если [math]p[/math] — корень дерева с сыном [math]x[/math], то совершаем один поворот вокруг ребра [math](x, p)[/math], делая [math]x[/math] корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина [math]x[/math] была нечетной.

zig — поворот

zig-zig

Если [math]p[/math] — не корень дерева, а [math]x[/math] и [math]p[/math] — оба левые или оба правые дети, то делаем поворот ребра [math](p, g)[/math], где [math]g[/math] отец [math]p[/math], а затем поворот ребра [math](x, p)[/math].

zig-zig — поворот

zig-zag

Если [math]p[/math] — не корень дерева и [math]x[/math] — левый ребенок, а [math]p[/math] — правый, или наоборот, то делаем поворот вокруг ребра [math](x, p)[/math], а затем поворот нового ребра [math](x, g)[/math], где [math]g[/math] — бывший родитель [math]p[/math].

zig-zag — поворот

Данная операция занимает [math]O(d)[/math] времени, где [math]d[/math] — длина пути от [math]x[/math] до корня.

find(tree, x)

Эта операция выполняется как для обычного бинарного дерева поиска, только после нее запускается операция splay.

merge(tree1, tree2)

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

split(tree, x)

Запускаем splay от элемента [math]x[/math] и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем [math]x[/math].

add(tree, x)

Запускаем split(tree, x), который нам возвращает деревья [math]\mathtt{tree1}[/math] и [math]\mathtt{tree2}[/math], их подвешиваем к [math]x[/math] как левое и правое поддеревья соответственно.

remove(tree, x)

Запускаем splay от [math]x[/math] элемента и возвращаем Merge от его детей.

Реализация операции splay

Bottom-up

В этой реализации операция splay производится при подъеме от целевой вершины до корня путем применения поворотов. Для подъема по дереву требуется доступ к вершине-родителю. Этого можно достичь либо путем хранения в каждой вершине ссылки на родителя, либо с помощью стека вершин на пути от корня к целевой.

Определим вспомогательные функции:

  • [math]\mathrm{rotate\_left}(v)[/math] — поворот ребра, соединяющего v и его правого сына
  • [math]\mathrm{rotate\_right}(v)[/math] — симметрично [math]\mathrm{rotate\_left}[/math]
  • [math]\mathrm{p}(v)[/math] — родитель вершины [math]v[/math]
  • [math]\mathrm{g}(v)[/math] — родитель родителя вершины [math]v[/math]

Приведем реализацию [math]\mathrm{p}[/math], [math]\mathrm{g}[/math], [math]\mathrm{rotate\_left}[/math]. Реализация [math]\mathrm{rotate\_right}[/math] симметрична. Положим, что для доступа к родительской вершине имеется соответствующее поле.

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.right) = 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 дерево разбивается на три части: [math]L[/math], [math]M[/math], [math]R[/math]. Деревья [math]L[/math] и [math]R[/math] содержат все вершины исходного дерева, для которых на данном этапе известно, что они меньше или больше искомого элемента соответственно. Дерево [math]M[/math] содержит вершины, принадлежащие поддереву текущей вершины на пути к целевой в исходном дереве. Изначально деревья [math]L[/math] и [math]R[/math] пусты, а текущая вершина пути к целевой — корень.

За одну итерацию операции splay производится спуск на две вершины по пути поиска целевой. Пройденные ребра удаляются, и отсоединившиеся при этом поддеревья добавляются правым ребенком наибольшей по значению вершине дерева [math]L[/math] или левым ребенком к наименьшей по значению вершине дерева [math]R[/math]. При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот.

Top-Down Splay.png

В конце пути производится слияние деревьев [math]L[/math], [math]M[/math] и [math]R[/math] таким образом, что новым корнем дерева становится вершина с целевым значением.

Top-Down Assembly.png

Приведем реализацию. Определим переменные:

  • [math]val[/math] — значение в целевой вершине
  • [math]t[/math] — текущая вершина, до и после splay — корень дерева
  • [math]l[/math] — наибольшая по значению вершина дерева [math]L[/math]
  • [math]r[/math] — наименьшая по значению вершина дерева [math]R[/math]
  • [math]l\_root[/math] — корень дерева [math]L[/math]
  • [math]r\_root[/math] — корень дерева [math]R[/math]

Определим вспомогательные функции:

  • [math]\mathrm{rotate\_left}(v)[/math] — поворот ребра, соединяющего [math]v[/math] и его правого сына
  • [math]\mathrm{rotate\_right}(v)[/math] — симметрично [math]\mathrm{rotate\_left}[/math]
  • [math]\mathrm{break\_left}(v)[/math] — удалить ребро, соединяющее [math]v[/math] и его правого сына, соединить [math]l[/math] с полученным деревом
  • [math]\mathrm{break\_right}(v)[/math] — симметрично [math]\mathrm{break\_left}[/math]
  • [math]\mathrm{assemble}()[/math] — слить деревья [math]L[/math], [math]M[/math] и [math]R[/math]

Приведем реализацию [math]\mathrm{rotate\_left}[/math], [math]\mathrm{break\_left}[/math], [math]\mathrm{assemble}[/math]. Реализация и [math]\mathrm{break\_right}[/math] симметрична.

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()

Время работы

В обеих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из [math]O(\log n)[/math] вершин. Обработка каждой вершины имеет сложность [math]O(1)[/math]. Таким образом, сложность приведенных выше операции splay — [math]O(\log n)[/math]

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

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

Лемма:
Амортизированное время операции splay вершины [math]x[/math] в дереве с корнем [math]t[/math] не превосходит [math]3r(t) - 3r(x) + 1[/math]
Доказательство:
[math]\triangleright[/math]

Проанализируем каждый шаг операции splay. Пусть [math]r'[/math] и [math]r[/math] — ранги вершин после шага и до него соответственно, [math]p[/math] — предок вершины [math]x[/math], а [math]g[/math] — предок [math]p[/math] (если есть).

Разберём случаи в зависимости от типа шага:

zig. Поскольку выполнен один поворот, то амортизированное время выполнения шага [math]T = 1 + r'(x) + r'(p) - r(x) - r(p)[/math] (поскольку только у вершин [math]x[/math] и [math]p[/math] меняется ранг). Ранг вершины [math]p[/math] уменьшился, поэтому [math]T \leqslant 1 + r'(x) - r(x)[/math]. Ранг вершины [math]x[/math] увеличился, поэтому [math]r'(x) - r(x) \geqslant 0[/math]. Следовательно, [math]T \leqslant 1 + 3r'(x) - 3r(x)[/math].

zig-zig. Выполнено два поворота, амортизированное время выполнения шага [math]T = 2 + r'(x) + r'(p) + r'(g) - r(p) - r(x) - r(g)[/math]. Поскольку после поворотов поддерево с корнем в [math]x[/math] будет содержать все вершины, которые были в поддереве с корнем в [math]g[/math] (и только их), поэтому [math]r'(x) = r(g)[/math]. Используя это равенство, получаем: [math]T = 2 + r'(p) + r'(g) - r(x) - r(p) \leqslant 2 + r'(p) + r'(g) - 2r(x)[/math], поскольку [math]r(x) \leqslant r(p)[/math].

Далее, так как [math]r'(p) \leqslant r'(x)[/math], получаем, что [math]T \leqslant 2 + r'(x) + r'(g) - 2r(x)[/math].

Мы утверждаем, что эта сумма не превосходит [math]3(r'(x) - r(x))[/math], то есть, что [math]r(x) + r'(g) - 2r'(x) \leqslant -2[/math]. Преобразуем полученное выражение следующим образом: [math](r(x) - r'(x)) + (r'(g) - r'(x)) = \log_2 \dfrac {C(x)}{C'(x)} + \log_2 \dfrac {C'(g)}{C'(x)}[/math].

Из рисунка видно, что [math]C'(g) + C(x) \leqslant C'(x)[/math], значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов [math]\log_2 a + \log_2 b = \log_2 ab[/math]. При [math]a + b \leqslant 1[/math] произведение [math]ab[/math] по неравенству между средними не превышает [math]\dfrac{1}{4}[/math]. А поскольку логарифм — функция возрастающая, то [math]\log_2 ab \leqslant -2[/math], что и является требуемым неравенством.

zig-zag. Выполнено два поворота, амортизированное время выполнения шага [math]T = 2 + r'(x) + r'(p) + r'(g) - r(x) - r(p) - r(g)[/math]. Поскольку [math]r'(x) = r(g)[/math], то [math]T = 2 + r'(p) + r'(g) - r(x) - r(p)[/math]. Далее, так как [math]r(x) \leqslant r(p)[/math], то [math]T \leqslant 2 + r'(p) + r'(g) - 2r(x)[/math].

Мы утверждаем, что эта сумма не превосходит [math]2(r'(x) - r(x))[/math], то есть, что [math]r'(p) + r'(g) - 2r'(x) \leqslant -2[/math]. Но, поскольку [math]r'(p) + r'(g) - 2r'(x) = \log_2 \dfrac {C'(p)}{C'(x)} + \log_2 \dfrac {C'(g)}{C'(x)} \leqslant -2[/math] - аналогично доказанному ранее, что и требовалось доказать.

Итого, получаем, что амортизированное время шага zig-zag не превосходит [math]2(r'(x) - r(x)) \leqslant 3(r'(x) - r(x))[/math].

Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить [math]3r(t) - 3r(x) + 1[/math], поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом). Тогда суммарное время работы splay [math]T_{splay} \leqslant 3\log_2 N - 3\log_2 C(x) + 1 = O(\log_2 N)[/math], где [math]N[/math] — число элементов в дереве.
[math]\triangleleft[/math]

Статическая оптимальность сплей-дерева

Теорема:
Если к ключам [math]1 \ldots n[/math], сложенным в сплей-дерево выполняется [math]m[/math] запросов, к [math]i[/math]-му ключу осуществляется [math]k_i[/math] запросов, где [math]k_i \gt 0[/math], то суммарное время работы не превышает [math]O(m \cdot H(p_1, p_2, \ldots , p_n))[/math], где [math]p_i = k_i / m[/math], [math]H[/math] — шенноновская энтропия
Доказательство:
[math]\triangleright[/math]

Известно, что [math]H(p_1, p_2, \ldots , p_n) = -c \cdot \displaystyle \sum_{i=1}^n (p_i \cdot \log_{2}p_i)[/math] шенноновская энтропия.

Пусть [math]s(x) = \displaystyle \sum_{y} w(y)[/math] — количество вершин в поддереве с корнем в [math]x[/math]. А [math]r(x) = \log_{2} s(x)[/math] — ранг вершины.

Обозначим за [math]r[/math] корень [math]splay[/math]-дерева. Из предыдущей теоремы известно, что [math]a_{splay} \leqslant 1+3(r(r)-r(x))[/math]

Пусть [math]w(x_i) = p_i =[/math] [math] {k_i \over m}[/math], тогда [math]k_i = p_i \cdot m[/math].
[math]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) =[/math] [math] 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) = (*)[/math]

Так как вершина [math]r[/math] — корень [math]splay[/math]-дерева, то очевидно, что [math]s = \displaystyle \sum_{y} w(y) = 1[/math], следовательно [math]r(r) = \log_{2}s(r)=0[/math]. Поэтому [math](*) = m(1+H(p_1,\ldots ,p_n)) = O(mH(p_1,\ldots ,p_n))[/math], ч.т.д.
[math]\triangleleft[/math]

Теорема о близких запросах в сплей-дереве

Теорема (о близких запросах в сплей-дереве):
Пусть в сплей-дерево сложены ключи [math] 1, \dotsc, n [/math]. Зафиксируем один из ключей [math] f [/math]. Пусть выполняется [math] m [/math] запросов к ключам. Тогда суммарное время на запросы есть [math] \displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1)) [/math], где [math] q_{i} [/math] — значение в вершине, к которой обращаются в [math] i [/math]-ый запрос.
Доказательство:
[math]\triangleright[/math]

Для доказательства теоремы воспользуемся методом потенциалов:

[math] a_{i} = t_{i} + \Phi_{i} - \Phi_{i-1} [/math].

По условию выполняется [math] m [/math] запросов, следовательно

[math] 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) [/math] [math] (\ast) [/math].

Введем следующие обозначения:

  • Весом узла с ключом [math] q [/math] будем называть величину [math] w(q) =\displaystyle \dfrac {1}{\left (\lvert q - f \rvert + 1 \right )^{2}} [/math].
  • Размером узла, содержащего ключ [math] q [/math], будем называть величину [math] s(q) = \displaystyle \sum_{y} w(y) [/math], где [math] y [/math] — узлы поддерева с корнем в [math] q [/math].
  • [math] r(q) = \log_{2}s(q) [/math] — ранг узла.
  • Потенциал дерева после [math] i [/math]-го запроса обозначим как [math] \Phi_{i} = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q) [/math].

Пусть [math] W [/math] — вес дерева. Тогда [math] 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) [/math].

Последнее верно, так как при фиксированном [math] f [/math], начиная с некоторого места, а именно [math] q = f [/math], ряд сходится.

Из определения размера узла следует, что [math] w(q) \leqslant s(q) \leqslant W [/math].

Также заметим, что для любого [math] q [/math] от [math] 1 [/math] до [math] n [/math] верно, что [math] w(q) \geqslant \displaystyle \dfrac {1}{n^{2}} [/math], так как максимальное значение знаменателя в определении [math] w(q) [/math] достигается при [math] q = n [/math] и [math] f = 1 [/math] или наоборот.

Тогда, воспользовавшись полученными оценками, найдем изменение потенциала сплей-дерева после [math] m [/math] запросов:

[math]\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)} [/math] [math] \displaystyle = O \Biggl(\sum_{q=1}^{n} \log_{2} n^{2}\Biggr) = [/math] [math] \displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left (n \log_{2}n\right) [/math].

Первое неравенство верно, так как максимальное значение потенциала достигается при [math] s(q) = W [/math], а минимальное при [math] s(q) = w(q) [/math], а значит изменение потенциала не превышает разности этих величин.

Обозначим за [math] t [/math] корень сплей-дерева. Тогда, воспользовавшись вышеуказанной леммой (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что

[math] \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 = [/math] [math] 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 [/math].

Докажем, что данное определение потенциала удовлетворяет условию теоремы о методе потенциалов.

Для любого [math] i [/math] верно, что [math] a_{i} = O(\log_{2}(n)) [/math], так как [math] \lvert q_{i} - f \rvert + 1 \leqslant n [/math], и [math] \Phi_{i} = O(n\log_{2}(n)) [/math], как было показано выше. Так как количество операций на запрос [math]k = O(n) [/math], то [math] a_{i} = O(f(k,n)) [/math] и [math] \Phi_{i} = O(kf(k,n)) [/math], где [math] f(k,n) [/math] — функция из теоремы о методе потенциалов, равная в данном случае [math] \log_{2}n [/math]. Следовательно, потенциал удовлетворяет условию теоремы.

Тогда, подставляя найденные значения в формулу [math] (\ast) [/math], получаем, что

[math]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) = [/math] [math] \displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_{2} \left ( \lvert q_{i} - f \rvert + 1 \right) \right)[/math].
[math]\triangleleft[/math]

Данная теорема показывает, что сплей-деревья поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу.

Splay-деревья по неявному ключу

Splay-дерево по неявному ключу полностью аналогично декартову дереву по неявному ключу, неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину [math]C(x)[/math] — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет [math]C(x)[/math] в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.

См. также

Источники информации