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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Анализ операции splay)
(Анализ операции splay)
Строка 21: Строка 21:
 
Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>v</tex> — это величина, обозначаемая <tex>r(v)</tex> и равная <tex>\log_2 C(v)</tex>, где <tex>C(v)</tex> — количество вершин в поддереве с корнем в <tex>v</tex>.
 
Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>v</tex> — это величина, обозначаемая <tex>r(v)</tex> и равная <tex>\log_2 C(v)</tex>, где <tex>C(v)</tex> — количество вершин в поддереве с корнем в <tex>v</tex>.
  
 +
{{Лемма
 +
|statement=
 
Амортизированное время операции splay вершины <tex>v</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(v) + 1</tex>
 
Амортизированное время операции splay вершины <tex>v</tex> в дереве с корнем <tex>t</tex> не превосходит <tex>3r(t) - 3r(v) + 1</tex>
  
 +
|proof=
 
Проанализируем каждый шаг операции splay. Пусть <tex>r'</tex> и <tex>r</tex> — ранги вершин после шага и до него соответственно, <tex>u</tex> — предок вершины <tex>v</tex>, а <tex>w</tex> — предок <tex>u</tex> (если есть).
 
Проанализируем каждый шаг операции splay. Пусть <tex>r'</tex> и <tex>r</tex> — ранги вершин после шага и до него соответственно, <tex>u</tex> — предок вершины <tex>v</tex>, а <tex>w</tex> — предок <tex>u</tex> (если есть).
  
Строка 44: Строка 47:
  
 
Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(v) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).
 
Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(v) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом).
 +
}}
  
 
==Литература==
 
==Литература==
 
# Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"
 
# Daniel Sleator, Robert Tarjan "A data structure for dynamic trees"

Версия 20:20, 3 мая 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".

Анализ операции 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"