Splay-дерево — различия между версиями
Lirik (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 33 промежуточные версии 13 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Сплей-дерево (Splay-tree | + | '''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983</tex> году. |
==Эвристики== | ==Эвристики== | ||
Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя различные эвристики: | Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя различные эвристики: | ||
− | * '''Move to Root''' {{---}} совершает повороты вокруг ребра <tex>(x, p)</tex>, где <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> поворотов. | ||
+ | |||
+ | [[file:Move_to_root.png|750px]] | ||
+ | |||
+ | [[file:Splay.png|750px]] | ||
==Операции со splay-деревом== | ==Операции со splay-деревом== | ||
− | === | + | ===splay(tree, x)=== |
− | " | + | "splay" делится на <tex>3</tex> случая: |
− | ==== | + | ====zig==== |
− | Если <tex>p</tex> | + | Если <tex>p</tex> — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>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. | ||
+ | |||
+ | ===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== | |
− | + | ===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== | ==Анализ операции splay== | ||
− | Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>x</tex> — это величина, обозначаемая <tex>r(x)</tex> и равная <tex>\log_2 C(x)</tex>, где <tex>C(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>. |
{{Лемма | {{Лемма | ||
+ | |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> | ||
Строка 53: | Строка 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 \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) \ | + | Далее, так как <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) \ | + | Мы утверждаем, что эта сумма не превосходит <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) \ | + | Из рисунка видно, что <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) \ | + | Мы утверждаем, что эта сумма не превосходит <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)) \ | + | Итого, получаем, что амортизированное время шага 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 выполняется не более одного шага типа 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>. | ||
+ | |||
+ | Первое неравенство верно, так как максимальное значение потенциала достигается при <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-деревья по неявному ключу== | ||
+ | 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 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) — это двоичное дерево поиска. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в году.
Эвристики
Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя различные эвристики:
- Move to Root — совершает повороты вокруг ребра , где — найденная вершина, — ее предок, пока не окажется корнем дерева. Однако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет .
- Splay — также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.
Пример: При последовательном использовании операций "move to root" для вершин
и требуется по поворотов, в то время как при использовании операции "splay" для вершины достаточно поворотов.Операции со splay-деревом
splay(tree, x)
"splay" делится на
случая:zig
Если
— корень дерева с сыном , то совершаем один поворот вокруг ребра , делая корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина была нечетной.zig-zig
Если
— не корень дерева, а и — оба левые или оба правые дети, то делаем поворот ребра , где отец , а затем поворот ребра .zig-zag
Если
— не корень дерева и — левый ребенок, а — правый, или наоборот, то делаем поворот вокруг ребра , а затем поворот нового ребра , где — бывший родитель .Данная операция занимает
времени, где — длина пути от до корня.find(tree, x)
Эта операция выполняется как для обычного бинарного дерева поиска, только после нее запускается операция splay.
merge(tree1, tree2)
У нас есть два дерева
и , причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем splay от самого большого элемента в дереве (пусть это элемент ). После этого корень содержит элемент , при этом у него нет правого ребёнка. Делаем правым поддеревом и возвращаем полученное дерево.split(tree, x)
Запускаем splay от элемента
и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем .add(tree, x)
Запускаем split(tree, x), который нам возвращает деревья
и , их подвешиваем к как левое и правое поддеревья соответственно.remove(tree, x)
Запускаем splay от
элемента и возвращаем Merge от его детей.Реализация операции splay
Bottom-up
В этой реализации операция splay производится при подъеме от целевой вершины до корня путем применения поворотов. Для подъема по дереву требуется доступ к вершине-родителю. Этого можно достичь либо путем хранения в каждой вершине ссылки на родителя, либо с помощью стека вершин на пути от корня к целевой.
Определим вспомогательные функции:
- — поворот ребра, соединяющего v и его правого сына
- — симметрично
- — родитель вершины
- — родитель родителя вершины
Приведем реализацию
, , . Реализация симметрична. Положим, что для доступа к родительской вершине имеется соответствующее поле.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 дерево разбивается на три части:
, , . Деревья и содержат все вершины исходного дерева, для которых на данном этапе известно, что они меньше или больше искомого элемента соответственно. Дерево содержит вершины, принадлежащие поддереву текущей вершины на пути к целевой в исходном дереве. Изначально деревья и пусты, а текущая вершина пути к целевой — корень.За одну итерацию операции splay производится спуск на две вершины по пути поиска целевой. Пройденные ребра удаляются, и отсоединившиеся при этом поддеревья добавляются правым ребенком наибольшей по значению вершине дерева
или левым ребенком к наименьшей по значению вершине дерева . При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот.В конце пути производится слияние деревьев
, и таким образом, что новым корнем дерева становится вершина с целевым значением.Приведем реализацию. Определим переменные:
- — значение в целевой вершине
- — текущая вершина, до и после splay — корень дерева
- — наибольшая по значению вершина дерева
- — наименьшая по значению вершина дерева
- — корень дерева
- — корень дерева
Определим вспомогательные функции:
- — поворот ребра, соединяющего и его правого сына
- — симметрично
- — удалить ребро, соединяющее и его правого сына, соединить с полученным деревом
- — симметрично
- — слить деревья , и
Приведем реализацию
, , . Реализация и симметрична.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()
Время работы
В обеих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из
вершин. Обработка каждой вершины имеет сложность . Таким образом, сложность приведенных выше операции splay —Анализ операции splay
Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины — это величина, обозначаемая и равная , где — количество вершин в поддереве с корнем в .
Лемма: |
Амортизированное время операции splay вершины в дереве с корнем не превосходит |
Доказательство: |
Проанализируем каждый шаг операции splay. Пусть и — ранги вершин после шага и до него соответственно, — предок вершины , а — предок (если есть).Разберём случаи в зависимости от типа шага: zig. Поскольку выполнен один поворот, то амортизированное время выполнения шага (поскольку только у вершин и меняется ранг). Ранг вершины уменьшился, поэтому . Ранг вершины увеличился, поэтому . Следовательно, .zig-zig. Выполнено два поворота, амортизированное время выполнения шага . Поскольку после поворотов поддерево с корнем в будет содержать все вершины, которые были в поддереве с корнем в (и только их), поэтому . Используя это равенство, получаем: , поскольку .Далее, так как , получаем, что .Мы утверждаем, что эта сумма не превосходит , то есть, что . Преобразуем полученное выражение следующим образом: .Из рисунка видно, что , значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов . При произведение по неравенству между средними не превышает . А поскольку логарифм — функция возрастающая, то , что и является требуемым неравенством.zig-zag. Выполнено два поворота, амортизированное время выполнения шага . Поскольку , то . Далее, так как , то .Мы утверждаем, что эта сумма не превосходит , то есть, что . Но, поскольку - аналогично доказанному ранее, что и требовалось доказать.Итого, получаем, что амортизированное время шага zig-zag не превосходит Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить . , поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом). Тогда суммарное время работы splay , где — число элементов в дереве. |
Статическая оптимальность сплей-дерева
Теорема: |
Если к ключам , сложенным в сплей-дерево выполняется запросов, к -му ключу осуществляется запросов, где , то суммарное время работы не превышает , где , — шенноновская энтропия |
Доказательство: |
Известно, что шенноновская энтропия. —Пусть — количество вершин в поддереве с корнем в . А — ранг вершины.Обозначим за корень -дерева. Из предыдущей теоремы известно, чтоПусть |
Теорема о близких запросах в сплей-дереве
Теорема (о близких запросах в сплей-дереве): |
Пусть в сплей-дерево сложены ключи . Зафиксируем один из ключей . Пусть выполняется запросов к ключам. Тогда суммарное время на запросы есть , где — значение в вершине, к которой обращаются в -ый запрос. |
Доказательство: |
Для доказательства теоремы воспользуемся методом потенциалов: . По условию выполняется запросов, следовательно. Введем следующие обозначения:
Пусть — вес дерева. Тогда .Последнее верно, так как при фиксированном , начиная с некоторого места, а именно , ряд сходится.Из определения размера узла следует, что .Также заметим, что для любого от до верно, что , так как максимальное значение знаменателя в определении достигается при и или наоборот.Тогда, воспользовавшись полученными оценками, найдем изменение потенциала сплей-дерева после запросов:. Первое неравенство верно, так как максимальное значение потенциала достигается при , а минимальное при , а значит изменение потенциала не превышает разности этих величин.Обозначим за леммой (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что корень сплей-дерева. Тогда, воспользовавшись вышеуказанной. Докажем, что данное определение потенциала удовлетворяет условию теоремы о методе потенциалов. Для любого верно, что , так как , и , как было показано выше. Так как количество операций на запрос , то и , где — функция из теоремы о методе потенциалов, равная в данном случае . Следовательно, потенциал удовлетворяет условию теоремы.Тогда, подставляя найденные значения в формулу , получаем, что . |
Данная теорема показывает, что сплей-деревья поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу.
Splay-деревья по неявному ключу
Splay-дерево по неявному ключу полностью аналогично декартову дереву по неявному ключу, неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.