En este árbol, el ancestro común más bajo de los nodos color verde claro, es el nodo de color verde oscuro.
El ancestro común más bajo (ACB) es un concepto dentro de la teoría de grafos y ciencias de la computación. Sea T un árbol con raíz y nnodos. El ancestro común más bajo entre dos nodos v y w se define como el nodo más bajo en T que tiene a v y w como descendientes (donde se permite a un nodo ser descendiente de él mismo).
El ACB de v y w en T es el ancestro compartido de v y w que está localizado más lejos de la raíz. El cómputo del ancestro común más bajo 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 puede ser calculada como la distancia desde la raíz hasta v, sumada con la distancia desde la raíz hasta w, menos dos veces la distancia desde la raíz hasta su ancestro común más bajo.
En una estructura de datos árbol donde cada nodo referencia a su padre, el ancestro común más bajo puede ser determinado de forma muy simple, encontrando la primera intersección de los caminos desde v and w hasta la raíz. En general, el tiempo computacional requerido por 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 muchos algoritmos para procesar árboles con los que el ancestro común más bajo puede ser encontrado de forma más rápida.
Se puede buscar en tiempo constante por pregunta después de un preprocesamiento en tiempo lineal.
Sin preprocesamiento se puede mejorar el tiempo de cómputo del algoritmo ingenuo hasta O(log h) almacenando los caminos a través del árbol usando skew-binary random access lists, premitiendo aún al árbol ser extendido en tiempo constante (Edward Kmett (2012)).
Historia
El problema del ancestro común más bajo fue definido por Alfred Aho, Jonh Hopcroft y Jeffry Ullman en 1973, pero Harel Dov y Robert Tarjan fueron los primeros en desarrollar una estructura de datos óptima y eficiente para encontrar el ancestro común más bajo. Su algoritmo procesa cualquier árbol en tiempo lineal, usando una descomposición de caminos fuerte, así las preguntas subsiguientes por el ancestro común más bajo pueden ser respondidas en tiempo constante por pregunta. Sin embargo, su estructura de datos es compleja y difícil de implementar. Tarjan también encontró un simple, pero menos eficiente algoritmo, basado en la estructura de datos conjuntos disjuntos.
En 1988 Baruch Schieber y Uzi Vishkin simplificaron la estructura de datos de Harel y Tarjan, consiguiendo una estructura implementable con el mismo preprocesamiento asintótico y rangos de tiempo por pregunta. Su simplificación está basada en el principio 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 puede ser computado simplemente del mínimo entre los niveles de los dos nodos por los que se está preguntando, mientras que si el árbol es un árbol binario completo, los nodos pueden ser indexados de forma tal que el ancestro común más bajo se reduce a una simple operación binaria entre índices. La estructura de Schieber y Vishkin descompone cualquier árbol en una colección de caminos, tal que las conexiones entre los caminos tienen la estructura de árbol binario, y combina ambas de estas dos simples técnicas de indexado.
En 1993 Omer Berkman y Uzi Vishkin descubrieron una forma completamente nueva para responder preguntas sobre el ancestro común más bajo, logrando de nuevo preprocesamiento en tiempo lineal con preguntas en tiempo constante. Su método funciona formando un ciclo de euler de un grafo formado por el árbol de entrada doblando cada arista, usando este camino para escribir una secuencia de números de niveles de los nodos en el orden en que el camino los visita; la pregunta sobre el ancestro común más bajo puede entonces ser transformada en una pregunta que busque el valor mínimo dentro de algún subintervalo de esta secuencia de números. Ellos entonces manipularon este problema mínimo valor en un rango combinando dos técnicas, una técnica basada en precomputar las preguntas en intervalos largos que tienen tamaño potencias de dos, y la otra basada en una tabla para buscar en intervalos pequeños. Este método fue presentado más tarde en una forma simplificada por Michael Bender y Martin Farach-Colton en el 2000. Como fue previamente observado por Gabow, Bentley y Tarjan en 1984, el problema del mínimo en un rango puede ser transformado hacia atrás en el problema del ancestro común más bajo usando la técnica de árboles cartesianos.
Otras simplificaciones fueron hechas por Alstrup, Gavoille, Kaplan y Rauhe en 2004 y Fischer y Heun en 2006.
Bender, Michael A.; Farach-Colton, Martin (2000), «The LCA problem revisited», Proceedings of the 4th Latin American Symposium on Theoretical Informatics, Lecture Notes in Computer Science 1776, Springer-Verlag, pp. 88-94, doi:10.1007/10719839_9..
Berkman, Omer; Vishkin, Uzi (1993), «Recursive Star-Tree Parallel Data Structure», SIAM Journal on Computing22 (2): 221-242, doi:10.1137/0222017..
Fischer, Johannes; Heun, Volker (2006), «Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE», Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science 4009, Springer-Verlag, pp. 36-48, doi:10.1007/11780441_5..
Harel, Dov; Tarjan, Robert E. (1984), «Fast algorithms for finding nearest common ancestors», SIAM Journal on Computing13 (2): 338-355, doi:10.1137/0213024..
Schieber, Baruch; Vishkin, Uzi (1988), «On finding lowest common ancestors: simplification and parallelization», SIAM Journal on Computing17 (6): 1253-1262, doi:10.1137/0217079..
