antepasado común más bajo
En teoría de grafos e informática , el antepasado común más bajo ( LCA ) (también llamado antepasado menos común) de dos nodos v y w en un árbol o gráfico acíclico dirigido (DAG) T es el nodo más bajo (es decir, el más profundo) que tiene ambos v y w como descendientes, donde definimos cada nodo como un descendiente de sí mismo (por lo que si v tiene una conexión directa con w , w es el ancestro común más bajo).
El LCA de v y w en T es el ancestro compartido de v y w que se encuentra más alejado de la raíz. El cálculo de los ancestros comunes más bajos puede ser útil, por ejemplo, como parte de un procedimiento para determinar la distancia entre pares de nodos en un árbol: la distancia de v a w se puede calcular como la distancia de la raíz a v , más la distancia desde la raíz hasta w , menos el doble de la distancia desde la raíz hasta su ancestro común más bajo ( Djidjev, Pantziou & Zaroliagis 1991 ). En ontologías , el ancestro común más bajo también se conoce como elancestro menos común .
En una estructura de datos de árbol donde cada nodo apunta a su padre, el ancestro común más bajo se puede determinar fácilmente encontrando la primera intersección de las rutas de v y w a la raíz. En general, el tiempo computacional requerido para este algoritmo es O(h) donde h es la altura del árbol (longitud del camino más largo desde una hoja hasta la raíz). Sin embargo, existen varios algoritmos para procesar árboles de modo que los ancestros comunes más bajos se puedan encontrar más rápidamente. El algoritmo de ancestros comunes más bajos fuera de línea de Tarjan , por ejemplo, preprocesa un árbol en tiempo lineal para proporcionar consultas LCA en tiempo constante. En general, los DAG existen algoritmos similares, pero con una complejidad superlineal.
El problema del ancestro común más bajo fue definido por Alfred Aho , John Hopcroft y Jeffrey Ullman ( 1973 ), pero Dov Harel y Robert Tarjan ( 1984 ) fueron los primeros en desarrollar una estructura de datos de ancestro común más bajo óptimamente eficiente. Su algoritmo procesa cualquier árbol en tiempo lineal, utilizando una descomposición de ruta pesada , de modo que las consultas subsiguientes sobre el ancestro común más bajo puedan responderse en un tiempo constante por consulta. Sin embargo, su estructura de datos es compleja y difícil de implementar. Tarjan también encontró un algoritmo más simple pero menos eficiente, basado en la estructura de datos union-find , paracalcular los ancestros comunes más bajos de un lote fuera de línea de pares de nodos .
Baruch Schieber y Uzi Vishkin ( 1988 ) simplificaron la estructura de datos de Harel y Tarjan, lo que llevó a una estructura implementable con el mismo preprocesamiento asintótico y límites de tiempo de consulta. Su simplificación se basa en el principio de que, en dos tipos especiales de árboles, los ancestros comunes más bajos son fáciles de determinar: si el árbol es un camino, entonces el ancestro común más bajo se puede calcular simplemente a partir del mínimo de los niveles de los dos consultados. nodos, mientras que si el árbol es un árbol binario completo, los nodos se pueden indexar de tal manera que los ancestros comunes más bajos se reduzcan a simples operaciones binarias en los índices. La estructura de Schieber y Vishkin descompone cualquier árbol en una colección de caminos, de modo que las conexiones entre los caminos tienen la estructura de un árbol binario, y combina estas dos técnicas de indexación más simples.
