Algorytm offline Tarjana do znajdowania najniższego wspólnego przodka
Algorytm offline Tarjana to metoda obliczania najniższego wspólnego przodka dla pary węzłów w drzewie, oparta na strukturze zbiorów rozłącznych.
Najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki węzeł, który jest najbliższym wspólnym przodkiem d i e, mającym najwyższy poziom w drzewie T. Algorytm ten został opracowany przez Roberta Tarjana w 1979 roku. Należy on do klasy algorytmów offline, co oznacza, że przed jego uruchomieniem należy dostarczyć wszystkie pary wierzchołków, dla których będzie obliczany najniższy wspólny przodek.
Najprostsza wersja algorytmu wykorzystuje strukturę „find union”, jednak w przeciwieństwie do innych algorytmów wyszukiwania wspólnego przodka, może nie zapewniać stałego czasu działania dla każdej operacji, gdy liczba par wierzchołków jest zbliżona do liczby węzłów w drzewie. Ostatnie udoskonalenia przyspieszają działanie algorytmu do czasów liniowych.
Pseudokod
Poniższy pseudokod oblicza najniższego wspólnego przodka dla każdej pary z zestawu P. Korzeń drzewa jest przechowywany w zmiennej r, natomiast dzieci węzła n znajdują się w zbiorze n.children. W przypadku tego algorytmu offline zbiór P musi być zdefiniowany przed rozpoczęciem działania algorytmu. W procedurze wykorzystywane są funkcje MakeSet, Find oraz Union ze zbiorów rozłącznych. MakeSet(u) tworzy singleton z u, Find(u) zwraca reprezentanta zbioru, do którego należy u, a Union(u, v) łączy zbiory, które zawierają węzły u oraz v.
Funkcja TarjanOLCA(r) jest na początku wywoływana z parametrem równym korzeniowi r.
funkcja TarjanOLCA(u)
MakeSet(u)
u.ancestor := u
dla każdego v należącego do u.children wykonaj
TarjanOLCA(v)
Union(u,v)
Find(u).ancestor := u
u.color := black;
dla każdego v takiego, że {u,v} należy do P wykonaj
if v.colour == black
zwróć wynik: Find(v).ancestor
Po początkowej inicjalizacji każdy węzeł ma kolor biały, a na czarno zostaje pokolorowany w momencie, gdy wszystkie jego dzieci zostaną odwiedzone. Najniższy wspólny przodek pary {u,v} może być wyznaczony przez wywołanie funkcji Find(v).ancestor w momencie, gdy węzeł u jest pokolorowany na czarno, a v jest już czarny. W przeciwnym razie, wynik będzie dostępny później jako Find(u).ancestor, gdy v również zostanie pokolorowane na czarno.
Poniżej przedstawiono zoptymalizowaną wersję funkcji MakeSet, Find oraz Union działających na zbiorach rozłącznych.
funkcja MakeSet(x)
x.parent := x
x.rank := 0
funkcja 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
funkcja Find(x)
if x.parent == x
return x
else
x.parent := Find(x.parent)
return x.parent
Przypisy
Bibliografia
H. N. Gabow, R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. „Proceedings of the 15th ACM Symposium on Theory of Computing (STOC)”, s. 246–251, 1983. DOI: 10.1145/800061.808753.
Tarjan. Applications of path compression on balanced trees. „Journal of the ACM”. 4 (26), s. 690–715, 1979. DOI: 10.1145/322154.322161.
