Splay-дерево - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:30:49Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:25, 1 сентября 2022

2022-09-01T04:25:24Z

Mitya: /* Correction in code */

2020-06-21T11:07:40Z

‎Correction in code

94.233.229.185: /* find(tree, x) */

2019-10-07T14:58:30Z

‎find(tree, x)

94.188.15.214: /* Время работы */

2019-10-03T18:51:53Z

‎Время работы

Garuda-1: Добавлены иллюстрации к реализации операции splay

2019-05-18T20:46:32Z

Добавлены иллюстрации к реализации операции splay

Garuda-1: Исправление помарок в разделе

2019-05-18T08:04:56Z

Исправление помарок в разделе

Garuda-1: Добавлены две реализации операции splay

2019-05-17T23:58:57Z

Добавлены две реализации операции splay

Внесённые изменения

Mervap в 00:45, 22 апреля 2018

2018-04-22T00:45:01Z

Mervap в 13:11, 20 апреля 2018

2018-04-20T13:11:50Z

@@ Строка 1: / Строка 1: @@
 '''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983</tex> году.
@@ Строка 333: / Строка 312: @@
 ==Splay-деревья по неявному ключу==
-Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.
+Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.
 == См. также ==

@@ Строка 1: / Строка 1: @@
 '''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983</tex> году.
@@ Строка 312: / Строка 333: @@
 ==Splay-деревья по неявному ключу==
-Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.
+Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.
 == См. также ==

@@ Строка 80: / Строка 80: @@
     p(r) = p
     '''if''' (v.right != '''null''')
-      p(v) = v
+      p(v.right) = v
 Реализация splay:

@@ Строка 32: / Строка 32: @@
 ===find(tree, x)===
-Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного дерева]], только после нее запускается операция splay.
+Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного дерева поиска]], только после нее запускается операция splay.
 ===merge(tree1, tree2)===

@@ Строка 201: / Строка 201: @@
 ===Время работы===
-В обоих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из <tex>O(\log n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log n)</tex>
+В обеих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из <tex>O(\log n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log n)</tex>
 ==Анализ операции splay==

@@ Строка 113: / Строка 113: @@
 В процессе спуска во время операции 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>. При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот. В конце пути производится слияние деревьев <tex>L</tex>, <tex>M</tex> и <tex>R</tex> таким образом, что новым корнем дерева становится вершина с целевым значением.
+За одну итерацию операции splay производится спуск на две вершины по пути поиска целевой. Пройденные ребра удаляются, и отсоединившиеся при этом поддеревья добавляются правым ребенком наибольшей по значению вершине дерева <tex>L</tex> или левым ребенком к наименьшей по значению вершине дерева <tex>R</tex>. При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот.
 Приведем реализацию. Определим переменные:

@@ Строка 54: / Строка 54: @@
 Определим вспомогательные функции:
 *<tex>\mathrm{rotate\_left}(v)</tex> {{---}} поворот ребра, соединяющего v и его правого сына
-*<tex>\mathrm{rotate\_right}(v)</tex> {{---}} симметрично rotate_left
+*<tex>\mathrm{rotate\_right}(v)</tex> {{---}} симметрично <tex>\mathrm{rotate\_left}</tex>
-*<tex>\mathrm{p}(v)</tex> {{---}} родитель вершины v
+*<tex>\mathrm{p}(v)</tex> {{---}} родитель вершины <tex>v</tex>
-*<tex>\mathrm{g}(v)</tex> {{---}} родитель родителя вершины v
+*<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> симметрична. Положим, что для доступа к родительской вершине имеется соответствующее поле.
@@ Строка 69: / Строка 69: @@
     '''Node''' p = p(v)
     '''Node''' r = v.right
-    '''if''' (p != null)
+    '''if''' (p != '''null''')
       '''if''' (p.left == v)
         p.left = r
@@ Строка 79: / Строка 79: @@
     p(v) = r
     p(r) = p
-    '''if''' (v.right != null)
+    '''if''' (v.right != '''null''')
       p(v) = v
@@ Строка 85: / Строка 85: @@
   '''void''' splay('''Node''' v):
-    '''while''' (p(v) != null)
+    '''while''' (p(v) != '''null''')
       '''if''' (v == p(v).left)
         '''if''' (g(v) == '''null''')
@@ Строка 105: / Строка 105: @@
           rotate_right(p(v))
-Преимуществом данного подхода является возможность инкапсуляции всех модификаций структуры дерева, включая создание вспомогательных переменных и нарушение инвариантов. Рекомендуется для использования в случае, когда есть прямой доступ к целевой для операции splay вершине, иначе требуется два прохода по пути от корня до вершины (первый {{---}} поиск вершины стандартным алгоритмом, второй {{---}} splay)
+Преимуществом данного подхода является возможность инкапсуляции всех модификаций структуры дерева, включая создание вспомогательных переменных и нарушение инвариантов. Рекомендуется для использования в случае, когда есть прямой доступ к целевой для операции splay вершине, иначе требуется два прохода по пути от корня до вершины (первый {{---}} поиск вершины стандартным алгоритмом, второй {{---}} splay).
 ===Top-down===
@@ Строка 111: / Строка 111: @@
 Данная реализация не требует прямого доступа к целевой вершине, поскольку процесс перебалансировки происходит во время поиска вершины в дереве.
-В процессе спуска во время операции Splay дерево разбивается на три части: <tex>\mathrm{L}</tex>, <tex>\mathrm{M}</tex>, <tex>\mathrm{R}</tex>. Деревья <tex>\mathrm{L}</tex> и <tex>\mathrm{R}</tex> содержат все вершины исходного дерева, для которых на данном этапе известно, что они меньше или больше искомого элемента соответственно. Дерево <tex>\mathrm{M}</tex> содержит вершины, принадлежащие поддереву текущей вершины на пути к целевой в исходном дереве. Изначально деревья <tex>\mathrm{L}</tex> и <tex>\mathrm{R}</tex> пусты, а текущая вершина пути к целевой {{---}} корень.
+В процессе спуска во время операции 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>\mathrm{L}</tex> или левым ребенком к наименьшей по значению вершине дерева <tex>\mathrm{R}</tex>. При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот. В конце пути производится слияние деревьев <tex>\mathrm{L}</tex>, <tex>\mathrm{M}</tex> и <tex>\mathrm{R}</tex> таким образом, что новым корнем дерева становится вершина с целевым значением.
+За одну итерацию операции splay производится спуск на две вершины по пути поиска целевой. Пройденные ребра удаляются, и отсоединившиеся при этом поддеревья добавляются правым ребенком наибольшей по значению вершине дерева <tex>L</tex> или левым ребенком к наименьшей по значению вершине дерева <tex>R</tex>. При этом если происходит спуск оба раза в левых или правых детей, то перед присоединением производится поворот. В конце пути производится слияние деревьев <tex>L</tex>, <tex>M</tex> и <tex>R</tex> таким образом, что новым корнем дерева становится вершина с целевым значением.
 Приведем реализацию. Определим переменные:
-*<tex>\mathrm{val}</tex> {{---}} значение в целевой вершине
+*<tex>val</tex> {{---}} значение в целевой вершине
-*<tex>\mathrm{t}</tex> {{---}} текущая вершина, до и после splay {{---}} корень дерева
+*<tex>t</tex> {{---}} текущая вершина, до и после splay {{---}} корень дерева
-*<tex>\mathrm{l}</tex> {{---}} наибольшая по значению вершина дерева <tex>\mathrm{L}</tex>
+*<tex>l</tex> {{---}} наибольшая по значению вершина дерева <tex>L</tex>
-*<tex>\mathrm{r}</tex> {{---}} наименьшая по значению вершина дерева <tex>\mathrm{R}</tex>
+*<tex>r</tex> {{---}} наименьшая по значению вершина дерева <tex>R</tex>
-*<tex>\mathrm{l\_root}</tex> {{---}} корень дерева <tex>\mathrm{L}</tex>
+*<tex>l\_root</tex> {{---}} корень дерева <tex>L</tex>
-*<tex>\mathrm{r\_root}</tex> {{---}} корень дерева <tex>\mathrm{R}</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>\mathrm{l}</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{break\_right}(v)</tex> {{---}} симметрично <tex>\mathrm{break\_left}</tex>
-*<tex>\mathrm{assemble}()</tex> {{---}} слить деревья <tex>\mathrm{L}</tex>, <tex>\mathrm{M}</tex> и <tex>\mathrm{R}</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> симметрична.
@@ Строка 177: / Строка 177: @@
           t = break_left(t)
           t = break_right(t)
-    assemble()
+   assemble()
 Реализацию splay можно упростить, опустив вторую операцию удаления ребра в случае zig-zag. Приведем также ее:
@@ Строка 186: / Строка 186: @@
         '''if''' (val < t.left.value)
           t = rotate_right(t)
-         t = break_right(t)
+       t = break_right(t)
       '''else'''
         '''if''' (val > t.right.value)
           t = rotate_left(t)
-         t = break_left(t)
+       t = break_left(t)
-    assemble()
+   assemble()
 ===Время работы===
-В обоих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из <tex>O(\log_2 n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log_2 n)</tex>
+В обоих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из <tex>O(\log n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log n)</tex>
 ==Анализ операции splay==

@@ Строка 1: / Строка 1: @@
-'''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
+'''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983</tex> году.
 ==Эвристики==
@@ Строка 6: / Строка 6: @@
 * '''Splay''' {{---}} также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.
-'''Пример''': При последовательном использовании операций "move to root" для вершин <tex>A</tex> и <tex>B</tex> требуется по 6 поворотов, в то время как при использовании операции "splay" для вершины <tex>B</tex> достаточно 3 поворотов.
+'''Пример''': При последовательном использовании операций "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]]
@@ Строка 15: / Строка 15: @@
 ===splay(tree, x)===
-"splay" делится на 3 случая:
+"splay" делится на <tex>3</tex> случая:
 ====zig====
 Если <tex>p</tex> — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетной.