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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Splay)
Строка 12: Строка 12:
 
[[file:zig.jpg|500px|Zig - поворот]]
 
[[file:zig.jpg|500px|Zig - поворот]]
 
# Zig-Zig. Если <tex> p(x) </tex> - не корень дерева, а <tex> x </tex> и <tex> p(x) </tex> - оба левые или оба правые дети, то делаем поворот ребра <tex> \langle p(x), p(p(x)) \rangle </tex>, а затем поворот ребра <tex> \langle x, p(x) \rangle </tex>.
 
# Zig-Zig. Если <tex> p(x) </tex> - не корень дерева, а <tex> x </tex> и <tex> p(x) </tex> - оба левые или оба правые дети, то делаем поворот ребра <tex> \langle p(x), p(p(x)) \rangle </tex>, а затем поворот ребра <tex> \langle x, p(x) \rangle </tex>.
(NB: так только наркоманы поворачивают)[[file:Zigzig.PNG|500px|Zig-zig - поворот]]
+
[[file:Zigzig.PNG|500px|Zig-zig - поворот]]
 
# Zig-Zag. Если <tex> p(x) </tex> - не корень дерева и <tex> x </tex> - левый ребенок, а <tex> p(x) </tex> - правый, или наоборот, то делаем поворот вокруг ребра <tex> \langle x, p(x) \rangle </tex>, а затем поворот нового ребра <tex> \langle x, p(x) \rangle </tex>, где <tex> p(x) </tex> - новый родитель <tex> x </tex>.
 
# Zig-Zag. Если <tex> p(x) </tex> - не корень дерева и <tex> x </tex> - левый ребенок, а <tex> p(x) </tex> - правый, или наоборот, то делаем поворот вокруг ребра <tex> \langle x, p(x) \rangle </tex>, а затем поворот нового ребра <tex> \langle x, p(x) \rangle </tex>, где <tex> p(x) </tex> - новый родитель <tex> x </tex>.
(wtf??? Что за отстой?)[[file:zigzag.PNG|500px|Zig-zag - поворот]]
+
[[file:zigzag.PNG|500px|Zig-zag - поворот]]
  
 
Данная операция занимает <tex> O(d) </tex> времени, где <tex> d </tex> - длина пути от <tex> x </tex> до корня. В результате этой операции <tex> x </tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".
 
Данная операция занимает <tex> O(d) </tex> времени, где <tex> d </tex> - длина пути от <tex> x </tex> до корня. В результате этой операции <tex> x </tex> становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".

Версия 16:50, 30 июня 2011

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

Основной идей для сохранение баланса дерева является перетаскивание найденной вершины в корень после каждой операции поиска.

Move to Root

Пусть [math] p(x) [/math] - предок вершины [math] x [/math]. Эвристика "Move to Root" совершает повороты вокруг ребра [math] \langle x, p(x) \rangle [/math], пока [math] x [/math] не окажется корнем дерева. Данный поворот аналогичен zig - повороту.

Splay

"Splay" так же как и "Move to Root" перетаскивает вершину в корень дерева, но при этом она использует другую последовательность поворотов. Пока [math] x [/math] не является корнем дерева выполняется следующее :

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

Zig - поворот

  1. Zig-Zig. Если [math] p(x) [/math] - не корень дерева, а [math] x [/math] и [math] p(x) [/math] - оба левые или оба правые дети, то делаем поворот ребра [math] \langle p(x), p(p(x)) \rangle [/math], а затем поворот ребра [math] \langle x, p(x) \rangle [/math].

Zig-zig - поворот

  1. Zig-Zag. Если [math] p(x) [/math] - не корень дерева и [math] x [/math] - левый ребенок, а [math] p(x) [/math] - правый, или наоборот, то делаем поворот вокруг ребра [math] \langle x, p(x) \rangle [/math], а затем поворот нового ребра [math] \langle x, p(x) \rangle [/math], где [math] p(x) [/math] - новый родитель [math] x [/math].

Zig-zag - поворот

Данная операция занимает [math] O(d) [/math] времени, где [math] d [/math] - длина пути от [math] x [/math] до корня. В результате этой операции [math] x [/math] становится корнем дерева, а расстояние до корня от каждой вершины сокращается примерно пополам, что связано с разделением случаев "zig-zig" и "zig-zag".

Merge

Merge([math]T_1[/math], [math]T_2[/math]). У нас есть два дерева [math]T_1[/math] и [math]T_2[/math], причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay от самого большого элемента в дереве [math]T_1[/math] (пусть это элемент [math]i[/math]). После этого корень [math]T_1[/math] содержит элемент [math]i[/math], при этом у него нет правого ребёнка. Делаем [math]T_2[/math] правым поддеревом [math]i[/math] и возвращаем полученное дерево.

Split

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

Add

Add([math]i[/math], [math]T[/math]). Запускаем Split([math]i[/math], [math]T[/math]), который нам возвращает деревья [math]T_1[/math] и [math]T_2[/math], их подвешиваем к [math]i[/math] как левое и правое поддеревья соответственно.

Remove

Remove([math]i[/math], [math]T[/math]). Запускаем Splay от [math]i[/math]-го элемента и возвращаем Merge от его детей.

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

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

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

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

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

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

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

Далее, так как [math]r'(u) \le r'(v)[/math], получаем, что [math]T \le 2 + r'(v) + r'(w) - 2r(v)[/math].

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

Из рисунка видно, что [math]C'(w) + C(v) \le C'(v)[/math], значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов [math]\log_2 x + \log_2 y = \log_2 xy[/math]. При [math]x + y \le 1[/math] произведение [math]xy[/math] по неравенству между средними не превышает [math]1/4[/math]. А поскольку логарифм - функция возрастающая, то [math]\log_2 xy \le -2[/math], что и является требуемым неравенством.

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

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

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

Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить [math]3r(t) - 3r(v) + 1[/math], поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).
[math]\triangleleft[/math]

Литература

  1. Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"