Сведение задачи LCA к задаче RMQ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (Доказательство корректности алгоритма)
Строка 21: Строка 21:
 
== Доказательство корректности алгоритма ==
 
== Доказательство корректности алгоритма ==
 
Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел <tex>w</tex> - наименьший общий предок узлов <tex>u, v.</tex> Очевидно, что в поддереве с корнем <tex>w</tex> узел <tex>w</tex> будет иметь наименьшую глубину.
 
Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел <tex>w</tex> - наименьший общий предок узлов <tex>u, v.</tex> Очевидно, что в поддереве с корнем <tex>w</tex> узел <tex>w</tex> будет иметь наименьшую глубину.
Осталось доказать, что всегда выполняется неравенство <tex>I[u] \le I[w] \le I[v]\;(*).</tex>
+
Осталось доказать, что для любых значений <tex>I[u],\; I[v]\; \exists</tex> значение <tex>I[w]</tex>, что выполняется неравенство <tex>I[u] \le I[w] \le I[v]\;(*).</tex>
 
Пусть вершина <tex>u</tex> посещается раньше, чем вершина <tex>v.</tex> Тогда, если вершина <tex>v</tex> не явлется потомком вершины <tex>u,</tex> будет выполняться неравенство <tex>\;(*)</tex> (так как после посещения поддерева, содержащего вершину <tex>u</tex>, в список будет добавлена вершина <tex>w</tex>, а после - вершина <tex>v</tex>). А если вершина <tex>u</tex> является предком вершины <tex>v,</tex> то вершина <tex>u</tex> будет наименьшим общим предком вершин <tex>u, v</tex>. Очевидно, что неравенство выполняется.
 
Пусть вершина <tex>u</tex> посещается раньше, чем вершина <tex>v.</tex> Тогда, если вершина <tex>v</tex> не явлется потомком вершины <tex>u,</tex> будет выполняться неравенство <tex>\;(*)</tex> (так как после посещения поддерева, содержащего вершину <tex>u</tex>, в список будет добавлена вершина <tex>w</tex>, а после - вершина <tex>v</tex>). А если вершина <tex>u</tex> является предком вершины <tex>v,</tex> то вершина <tex>u</tex> будет наименьшим общим предком вершин <tex>u, v</tex>. Очевидно, что неравенство выполняется.
  

Версия 21:19, 15 мая 2011

Постановка задачи LCA

Определение:
Наименьшим общим предком (least common ancestor) двух узлов [math]u, v[/math] в корневом дереве [math]T[/math] называется узел [math]w,[/math] который среди всех узлов, являющихся предками как узла [math]u,[/math] так и [math]v,[/math] имеет наибольшую глубину.

Пусть дано корневое дерево [math]T.[/math] На вход подаются запросы вида [math](u,\;v),[/math] для каждого запроса требуется найти их наименьшего общего предка.

Алгоритм

Препроцессинг

1) В каждом узле будет храниться глубина узла в корневом дереве [math]T.[/math]

[math]depth(u)= \begin{cases} 0 & u = root(T),\\ depth(v) + 1 & u = son(v). \end{cases}[/math]

2) Запустим обход в глубину из корня, который будет строить список посещений узлов. Глубина текущей вершины добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына.

Запрос

Обозначим [math]I[u][/math] - функция, возвращающая все индексы ячеек в списке глубин, в которых хранится глубина узла [math]u.[/math] Пусть имеется запрос пара узлов [math]u, v.[/math] В результате получился список глубин вершин, в котором наименьшему общему предку вершин [math]u, v[/math] соответствует минимальная глубина на отрезке [math][I[u], I[v]].[/math] Можно брать любое значение [math]I[u].[/math] Для определённости [math]I[u] \le I[v].[/math]

Доказательство корректности алгоритма

Рассмотрим два узла [math]u, v[/math] корневого дерева [math]T[/math]. Пусть узел [math]w[/math] - наименьший общий предок узлов [math]u, v.[/math] Очевидно, что в поддереве с корнем [math]w[/math] узел [math]w[/math] будет иметь наименьшую глубину. Осталось доказать, что для любых значений [math]I[u],\; I[v]\; \exists[/math] значение [math]I[w][/math], что выполняется неравенство [math]I[u] \le I[w] \le I[v]\;(*).[/math] Пусть вершина [math]u[/math] посещается раньше, чем вершина [math]v.[/math] Тогда, если вершина [math]v[/math] не явлется потомком вершины [math]u,[/math] будет выполняться неравенство [math]\;(*)[/math] (так как после посещения поддерева, содержащего вершину [math]u[/math], в список будет добавлена вершина [math]w[/math], а после - вершина [math]v[/math]). А если вершина [math]u[/math] является предком вершины [math]v,[/math] то вершина [math]u[/math] будет наименьшим общим предком вершин [math]u, v[/math]. Очевидно, что неравенство выполняется.

Пример

Рассмотрим дерево на рисунке 1. Найдем наименьшего общего предка вершин, помеченных красным цветом. Список глубин, получающийся в результате обхода в глубину - [math][0, 1, 2, 1, 2, 1, 0, 1, 0].[/math] Глубина наименьшего общего предка красных вершин равна минимуму на отрезке [math][2, 1, 0, 1].[/math]

рис. 1

Сложность

Для нахождения минимального элемента на отрезке можно использовать дерево отрезков. Длина массива глубин будет равна [math](2n - 1),[/math] т.е. дерево отрезков будет построено за [math]O(n).[/math] Таким образом, препроцессинг работает за [math]O(n).[/math] Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. [math]O(\log n).[/math]

См.также

Ссылки