Algoritmo di Tarjan del più basso antenato comune offline
In informatica, l'algoritmo di Tarjan del più basso antenato comune offline è un algoritmo per il calcolo del più basso antenato comune per una coppia di nodi in un albero, basata sulla struttura dati union-find. Il più basso antenato comune di due nodi d ed e in un albero T è il nodo g antenato sia di d che di e che possiede la profondità maggiore in T. L'algoritmo prende il nome da Robert Tarjan, che sviluppò la tecnica nel 1979. Quello di Tarjan è un algoritmo offline; ovvero, a differenza degli altri algoritmi del più basso antenato comune, richiede di specificare in anticipo tutte le coppie di nodi per cui si vuole individuare il più basso antenato comune. La versione più semplice dell'algoritmo utilizza la struttura dati union-find che, a differenza delle strutture dati usate in altri algoritmi per il più basso antenato comune, può richiedere più di tempo costante per ogni operazione quando il numero delle paia di nodi ha un ordine di grandezza simile a quello dei nodi. Una modifica successiva di Gaboow e Tarjan velocizza l'algoritmo ad un tempo lineare.
Pseudocodice[modifica | modifica wikitesto]
Il seguente pseudocodice determina il più basso antenato comune di ciascuna coppia in P, data la radice r di un albero nel quale i figli del nodo n sono nel set n.children. Per questo algoritmo offline, il set P deve essere specificato in anticipo. Utilizza le funzioni MakeSet, Find e Union di una disjoint-set forest. MakeSet(u) rimuove u da un insieme singoletto, Find(u) mostra i rappresentanti standard dell'insieme contenente u, e Union(u,v) unisce l'insieme contenente u con quello contenente v. TarjanOLCA(r) è chiamato inizialmente sulla radice r.
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.color := black;
for each v such that {u,v} in P do
if v.color == black
print "Tarjan's Lowest Common Ancestor of " + u +
" and " + v + " is " + Find(v).ancestor + ".";
Ciascun nodo inizialmente è bianco, e viene colorato di nero dopo che esso e tutti i suoi figli sono stati visitati. Il più basso antenato comune {u,v} è disponibile come Find(v).ancestor immediatamente (e solo immediatamente) dopo che u è stato colorato di nero, a patto che v sia già nero. Altrimenti, sarà disponibile successivamente con Find(u).ancestor, subito dopo che v è stato colorato di nero.
Qui di seguito sono mostrate delle versioni ottimizzate di MakeSet, Find, and Union per una disjoint-set forest:
function MakeSet(x)
x.parent := x
x.rank := 1
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.rank == yRoot.rank
yRoot.parent := xRoot
xRoot.rank := xRoot.rank + 1
function Find(x)
if x.parent != x
x.parent := Find(x.parent)
return x.parent
Bibliografia[modifica | modifica wikitesto]
- H. N. Gabow e R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union, in Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), 1983, pp. 246–251, DOI:10.1145/800061.808753.
- R. E. Tarjan, Applications of path compression on balanced trees, in Journal of the ACM, vol. 26, n. 4, 1979, pp. 690–715, DOI:10.1145/322154.322161.
