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

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

Псевдокод

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

function TarjanOLCA(u) is
    MakeSet(u)
    u.ancestor := u
    for each v in u.children do
        TarjanOLCA(v)
        Union(u, v)
        Find(u).ancestor := u
    u.color := black
    for each v such that {u, v} in P do
        if v.color == black then
            print "Tarjan's Lowest Common Ancestor of " + u +
                  " and " + v + " is " + Find(v).ancestor + "."

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

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

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

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

function MakeSet(x) is
    x.parent := x
    x.rank   := 1
 
function Union(x, y) is
    xRoot := Find(x)
    yRoot := Find(y)
    if xRoot.rank > yRoot.rank then
        yRoot.parent := xRoot
    else if xRoot.rank < yRoot.rank then
        xRoot.parent := yRoot
    else if xRoot.rank == yRoot.rank then
        yRoot.parent := xRoot
        xRoot.rank := xRoot.rank + 1
  
function Find(x) is
    if x.parent != x then
       x.parent := Find(x.parent)
    return x.parent

Ссылки

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

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