Оффлайновый алгоритм наименьших общих предков Тарьяна

В информатике автономный алгоритм наименьших общих предков Тарьяна — это алгоритм вычисления наименьших общих предков для пар узлов в дереве, основанный на структуре данных union-find . Наименьшим общим предком двух узлов d и e в корневом дереве T является узел g , который является предком как d, так и e и имеет наибольшую глубину в T. Он назван в честь Роберта Тарьяна , который открыл этот метод в 1979 году. Алгоритм Тарьяна — это автономный алгоритм; то есть, в отличие от других алгоритмов наименьшего общего предка, он требует, чтобы все пары узлов, для которых требуется наименьший общий предок, были указаны заранее. Простейшая версия алгоритма использует структуру данных union-find, которая в отличие от других структур данных наименьшего общего предка может занимать больше постоянного времени на операцию, когда количество пар узлов аналогично по величине количеству узлов. Более позднее уточнение Габова и Тарьяна (1983) ускоряет алгоритм до линейного времени .

Псевдокод ниже определяет наименьшего общего предка каждой пары в P , учитывая корень r дерева, в котором дети узла n находятся в наборе n.children . Для этого автономного алгоритма набор P должен быть указан заранее. Он использует функции MakeSet , Find и Union структуры данных непересекающихся множеств . MakeSet(u) удаляет u в одноэлементный набор, Find(u) возвращает стандартного представителя набора, содержащего u , а Union(u,v) объединяет набор, содержащий u , с набором, содержащим v . TarjanOLCA( r ) сначала вызывается для корня r .

Функция TarjanOLCA(u) — это MakeSet(u) u.предок := u для каждого v в u.дети делают TarjanOLCA(v) Союз(у, г) Найти(u).ancestor := u u.color := черный для каждого v такого, что {u, v} в P, сделать  , если v.color == black , то распечатать "Наименьший общий предок Тарьяна" + u + " а " + v + " это " + Find(v).ancestor + "."

Каждый узел изначально белый и окрашивается в черный цвет после того, как он и все его дочерние узлы будут посещены.

Для каждой пары узлов {u,v}, подлежащей исследованию:

• Когда v уже черный (то есть когда v идет перед u при обратном обходе дерева): После того, как u окрашен в черный цвет, наименьший общий предок этой пары доступен как Find(v).ancestor , но только до тех пор, пока LCA u и v не окрашены в черный цвет.
• В противном случае: как только v окрасится в черный цвет, LCA будет доступен как Find(u).ancestor , в то время как LCA не окрасится в черный цвет.

Для справки, вот оптимизированные версии MakeSet , Find и Union для леса непересекающихся множеств :

Функция MakeSet(x) — это x.родитель := x x.ранг := 1 Функция Union(x, y) — это xRoot := Найти(x) yRoot := Найти(y) если xRoot.rank > yRoot.rank тогда yRoot.parent := xRoot иначе если xRoot.rank < yRoot.rank тогда xRoot.parent := yRoot иначе если xRoot.rank == yRoot.rank тогда yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1 функция Find(x) —  если x.parent != x тогда x.parent := Найти(x.parent) вернуть x.parent

• Габов, Х. Н.; Тарьян , Р. Э. (1983), «Линейный алгоритм для специального случая объединения непересекающихся множеств», Труды 15-го симпозиума ACM по теории вычислений (STOC) , стр. 246–251, doi : 10.1145/800061.808753, ISBN 0-89791-099-0.

• Тарьян, Р. Э. (1979), «Применение сжатия путей на сбалансированных деревьях», Журнал ACM , 26 (4): 690–715, doi : 10.1145/322154.322161.