Алгоритм Шибера-Вишкина — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Подготовка)
Строка 39: Строка 39:
  
 
Рассмотрим два случая.  
 
Рассмотрим два случая.  
''Первый случай'' <tex>\operatorname{inorder} v = \operatorname{order} v</tex>
+
 
 +
'''Первый случай''' <tex>\operatorname{inorder} v = \operatorname{order} v</tex>
 
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
 
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
 
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inorder}</tex> отличаются
 
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inorder}</tex> отличаются
 
от <tex>\operatorname{inorder} v</tex>.
 
от <tex>\operatorname{inorder} v</tex>.
  
''Второй случай'' <tex>\operatorname{inorder} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
+
'''Второй случай''' <tex>\operatorname{inorder} v = \operatorname{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
 
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inorder} w = \operatorname{inorder} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inorder} v' = \operatorname{inorder} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
 
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inorder} w = \operatorname{inorder} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inorder} v' = \operatorname{inorder} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
 
}}
 
}}

Версия 17:56, 21 июня 2012

Алгоритм Шибера-Вишкина применяется для нахождения наименьшего общего предка двух вершин в дереве. Он использует [math]O(n)[/math] времени на подготовку и затем отвечает на каждый запрос за [math]O(1)[/math].

Идея алгоритма

Основная идея алгоритма следующая.

  1. Если бы дерево, в котором нужно искать [math]LCA[/math] было бы цепочкой, можно было бы найти [math]LCA(u, v)[/math] просто взяв ту вершину, которая находится в дереве выше.
  2. Если дерево — полное двоичное дерево высоты [math]h[/math], то можно сопоставить каждой вершине битовый вектор длиной [math]h[/math] (целое число от [math]0[/math] до [math]2^h-1[/math]) и с помощью битовых операций над этими векторами найти [math]LCA(u, v)[/math]

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно научиться искать [math]LCA(v, u)[/math] в нем за [math]O(1)[/math].

Подготовка

Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем — поддеревья. Пусть [math]\operatorname{order} : V \to \mathbb{N}[/math] — такой порядок обхода.

Обозначим за [math]\operatorname{size} v[/math] количество вершин в поддереве вершины [math]v[/math]. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.

Утверждение:
Пусть [math]u[/math] — вершина из поддерева [math]v[/math]. Тогда [math]\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1][/math]
[math]\triangleright[/math]

По определению [math]\operatorname{order}[/math], [math]\operatorname{order} u[/math] вершин из поддерева [math]v[/math] образуют отрезок натуральных чисел длиной [math]\operatorname{size} v - 1[/math]. Так как этот отрезок начинается с

[math]\operatorname{order}v + 1[/math], то [math]\operatorname{order} u[/math] — отрезок [math][\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1][/math].
[math]\triangleleft[/math]

Покроем дерево путями. А именно, сопоставим каждой вершине [math]v[/math] число [math]\operatorname{inlabel} v[/math] такое, что прообраз каждого [math]\operatorname{inlabel} v[/math] в [math]T[/math] связен и является простым путем от какой-то вершины вниз до листа.

Утверждение:
В качестве [math]\operatorname{inlabel} v[/math] можно выбрать [math]\operatorname{order} u[/math], кратное максимальной степени двойки, где [math]u \in S(v)[/math].
[math]\triangleright[/math]

Пусть [math]\operatorname{inorder} v = \operatorname{order} u = k2^b[/math], [math]b[/math] — максимально. Пусть есть вершина [math]u' \in S(i)[/math] такая, что [math]\operatorname{order} u' = k'2^b[/math]. Так как в отрезке, соответствующем вершине [math]v[/math] есть два числа, кратных [math]2^b[/math], то там есть и число, кратное [math]2^{b+1}[/math]. Но тогда [math]\operatorname{inorder} v[/math] выбран неверно. Значит, в поддереве [math]v[/math] есть только одна такая вершина [math]u[/math], что [math]\operatorname{order} u \hdots 2^{max}[/math].

Рассмотрим два случая.

Первый случай [math]\operatorname{inorder} v = \operatorname{order} v[/math] Других таких вершин [math]u'[/math], что [math]u'[/math] дает такую же степень двойки, нет. Значит, во всех поддеревьях [math]v[/math] значения [math]\operatorname{inorder}[/math] отличаются от [math]\operatorname{inorder} v[/math].

Второй случай [math]\operatorname{inorder} v = \operatorname{order} u[/math], [math]u \in S(v), u \ne v[/math]

Так как в поддереве [math]v[/math] представлены все [math]\operatorname{order}[/math]-ы из отрезка [math][\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1][/math], то рассмотрим того потомка [math]w[/math] вершины [math]v[/math], что [math]u \in S(w)[/math]. Тогда, так как степень двойки у [math]u[/math] максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то [math]\operatorname{inorder} w = \operatorname{inorder} v = \operatorname{order} u[/math]. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого [math]w'[/math] — потомок [math]v[/math], что в поддереве [math]w'[/math] есть вершина с такой же степенью двойки. Значит, все вершины [math]v'[/math], у которых [math]\operatorname{inorder} v' = \operatorname{inorder} v[/math] находятся в поддереве [math]w[/math]. Проведя аналогичное доказательство для [math]w[/math], получим требуемое.
[math]\triangleleft[/math]

Обработка запроса

Пусть [math]x[/math], [math]y[/math] — вершины в исходном дереве [math]LCA[/math] которых необходимо найти. Если [math]\operatorname{inlabel} x = \operatorname{inlabel} y[/math], то они принадлежат одному простому пути, а следовательно ответом на запрос является [math]x[/math], если [math]\operatorname{level} x \le \operatorname{level} y[/math], и [math]y[/math], в противном случае. Теперь рассмотрим случай, когда [math]\operatorname{inlabel} x \ne \operatorname{inlabel} y[/math], то есть [math]x[/math] и [math]y[/math] принадлежат разным простым путям. Найдем [math]b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)[/math].

Утверждение:
[math]\operatorname{inlabel} (((x \gt \gt (i + 1)) \lt \lt 1) | 1) \lt \lt i[/math], где [math]i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)[/math]
[math]\triangleright[/math]
?
[math]\triangleleft[/math]