Tarjanov algoritam za najniže zajedničke pretke

U računarstvu, Tarjanov algoritam za najniže zajedničke pretke je algoritam koji računa najniže zajedničke pretke za par čvorova u stablu, zasnovan na strukturi podataka disjunktni set. Najniže zajednički predak dva čvora d i e u korenom stablu T je čvor g koji je predat i d i e i koji ima najveću dubini u T. Algoritam je nazvan po Robertu Tarjanu, koji je otkrio ovu tehniku 1979. Tarjanov algoritam je offline algoritam; za razliku od ostalih algoritama koji traže najnižeg zajedničkog pretka, ovaj algoritam zahteva da svi parovi čvorova za koje se traži najniži zajedniči predak moraju biti navedeni unapred. Najjednostavnija verzija ovog algoritma koristi struktiru podataka disjunktni set, koja za razliku od ostalih struktura podataka za najnižeg zajedničkog pretka može da traje više od konstantnog vremena po operaciji kada je broj parova čvorova sličan po veličini broju čvorova. Godine 1983. Gabov i Tarjan su uspeli da ubrzaju algoritam do brzine koja je ekvivalentna subeksponencijalnom vremenu.

Pseudokod

Pseudokod ispod određuje najnižeg zajedničkog pretka za svaki par u P, ako je koren stabla r u kojem se deca čvora n nalaze u n.children. Za ovaj offline algoritam, set P mora da bude naveden unapred.

 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 + ".";

Svaki čvor je inicijalno beo, i boji se crno pošto su on i sva njegova direktna deca posećeni. Najniži zajednički predak jednog para je odmah dostupan (i samo odmah) pošto su oba čvora obojena u crno. U suprotnom biće dostupan kasnije odmah pošto je drugi čvor obojen u crno.

Za dalje, evo primera optimizovanih MakeSet, Find, and Union za jedan disjunktni-set (struktura podataka).

 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

Literatura

• 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), str. 246—251, doi:10.1145/800061.808753 .