Тарјанов алгоритам за најниже заједничке претке

У рачунарству, Тарјанов алгоритам за најниже заједничке претке је алгоритам који рачуна најниже заједничке претке за пар чворова у стаблу, заснован на структури података дисјунктни сет. Најниже заједнички предак два чвора д и е у кореном стаблу Т је чвор г који је предат и д и е и који има највећу дубини у Т. Алгоритам је назван по Роберту Тарјану, који је открио ову технику 1979. Тарјанов алгоритам је offline алгоритам; за разлику од осталих алгоритама који траже најнижег заједничког претка, овај алгоритам захтева да сви парови чворова за које се тражи најнижи заједничи предак морају бити наведени унапред. Најједноставнија верзија овог алгоритма користи структиру података дисјунктни сет, која за разлику од осталих структура података за најнижег заједничког претка може да траје више од константног времена по операцији када је број парова чворова сличан по величини броју чворова. Године 1983. Габов и Тарјан су успели да убрзају алгоритам до брзине која је еквивалентна субекспоненцијалном времену.

Псеудокод

Псеудокод испод одређује најнижег заједничког претка за сваки пар у P, ако је корен стабла r у којем се деца чвора n налазе у n.children. За овај offline алгоритам, сет P мора да буде наведен унапред.

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

Сваки чвор је иницијално бео, и боји се црно пошто су он и сва његова директна деца посећени. Најнижи заједнички предак једног пара је одмах доступан (и само одмах) пошто су оба чвора обојена у црно. У супротном биће доступан касније одмах пошто је други чвор обојен у црно.

За даље, ево примера оптимизованих MakeSet, Find, and Union за један дисјунктни-сет (структура података).

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

Литература

• Gabow, H. N.; Tarjan, R. E. (1983), „A linear-time algorithm for a special case of disjoint set union”, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), стр. 246—251, doi:10.1145/800061.808753 .