En informática , el algoritmo de ancestros comunes más bajos fuera de línea de Tarjan es un algoritmo para calcular los ancestros comunes más bajos para pares de nodos en un árbol, basado en la estructura de datos de búsqueda de unión . El antepasado común más bajo de dos nodos d y e en un árbol con raíz T es el nodo g que es un antepasado de ambos d y e y que tiene la mayor profundidad en T . Lleva el nombre de Robert Tarjan, quien descubrió la técnica en 1979. El algoritmo de Tarjan es un algoritmo fuera de línea; es decir, a diferencia de otros algoritmos de antepasado común más bajo, requiere que todos los pares de nodos para los que se desee el antepasado común más bajo se especifiquen de antemano. La versión más simple del algoritmo utiliza la estructura de datos de búsqueda de unión, que a diferencia de otras estructuras de datos de ancestro común más bajo, puede tomar más que un tiempo constante por operación cuando el número de pares de nodos es similar en magnitud al número de nodos. Un refinamiento posterior de Gabow y Tarjan (1983) acelera el algoritmo hasta el tiempo lineal .
Pseudocódigo
El pseudocódigo siguiente determina el antepasado común más bajo de cada par en P , dada la raíz r de un árbol en el que los hijos del nodo n están en el conjunto n . Hijos . Para este algoritmo fuera de línea, el conjunto P debe especificarse de antemano. Utiliza las funciones MakeSet , Find y Union de un bosque de conjuntos disjuntos . MakeSet (u) elimina u a un conjunto singleton, Find (u) devuelve el representante estándar del conjunto que contiene u , y Union (u, v) fusiona el conjunto que contiene u con el conjunto que contiene v . TarjanOLCA ( r ) se llama primero en la raíz r .
la función TarjanOLCA (u) es MakeSet (u) u.ancestor: = u por cada v en u. que hacen los niños TarjanOLCA (v) Unión (u, v) Encuentra (u) .ancestro: = u u.color: = negro para cada v tal que {u, v} en P hacer si v.color == negro entonces print "El antepasado común más bajo de Tarjan de" + u + "y" + v + "es" + Find (v) .ancestor + "."
Cada nodo es inicialmente blanco, y después de él, se coloreó de negro y todos sus hijos fueron visitados.
Para cada par de nodos {u, v} a investigar:
- Cuando v ya es negro (es decir, cuando v viene antes que u en un recorrido posterior al orden del árbol): después de que u se colorea de negro, el ancestro común más bajo de este par está disponible como Find (v) .ancestor , pero solo mientras el LCA de u y v no es de color negro.
- De lo contrario: una vez que v sea de color negro, el LCA estará disponible como Find (u) .ancestor , mientras que el LCA no será de color negro.
Como referencia, aquí hay versiones optimizadas de MakeSet , Find y Union para un bosque de conjuntos disjuntos :
la función MakeSet (x) es x.padre: = x rango x: = 1 función Unión (x, y) es xRoot: = Encontrar (x) yRoot: = Encontrar (y) si xRoot.rank> yRoot.rank entonces yRoot.parent: = xRoot de lo contrario, si xRoot.rankentonces xRoot.parent: = yRoot de lo contrario, si xRoot.rank == yRoot.rank entonces yRoot.parent: = xRoot xRoot.rank: = xRoot.rank + 1 la función Find (x) es si x.parent! = x entonces x.parent: = Encontrar (x.parent) retorno x padre
Referencias
- Gabow, HN; Tarjan, RE (1983), "Un algoritmo de tiempo lineal para un caso especial de unión de conjuntos disjuntos", Actas del 15º Simposio ACM sobre Teoría de la Computación (STOC) , págs. 246-251, doi : 10.1145 / 800061.808753.
- Tarjan, RE (1979), "Aplicaciones de la compresión de rutas en árboles equilibrados", Journal of the ACM , 26 (4): 690–715, doi : 10.1145 / 322154.322161.