Algoritmo di Tarjan del più basso antenato comune offline
Da Wikipedia, l'enciclopedia encyclopedia
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.