Antepasado menos común

El ancestro menos común ( el ancestro común más bajo ) de los vértices u y v en el árbol con raíz T es el vértice más distante de la raíz del árbol, que se encuentra en ambos caminos desde u y v hasta la raíz, es decir, es el ancestro de ambos vértices. La abreviatura generalmente aceptada es LCA del inglés.  ancestro común más bajo (menos) .

Algoritmos

El algoritmo más simple e ingenuo para encontrar el ancestro menos común es calcular las profundidades de u y v y avanzar gradualmente en el árbol desde cada vértice hasta encontrar un vértice común:

Procedimiento ACV( u , v ): h1 := profundidad( u ) // profundidad( x ) = profundidad del vértice x h2 := profundidad( v ) mientras que h1 ≠ h2: si h1 > h2: u  := padre( u ) h1 := h1 - 1 más : v  := padre( v ) h2 := h2 - 1 while u ≠ v : u  := padre( u ) // padre( x ) = ancestro inmediato de x v  := padre( v ) te devuelvo

El tiempo de ejecución de este algoritmo es O ( h ), donde h  es la altura del árbol. Además, es posible que se requiera un preprocesamiento de tiempo O ( n ) para encontrar el ancestro inmediato de todos los nodos en el árbol (pero esta estructura generalmente ya está presente en el árbol).

Sin embargo, hay algoritmos más rápidos:

• Algoritmo de elevación binaria que requiere un tiempo de preprocesamiento O ( n log n ) y un tiempo de consulta O (log n ) (cálculo del ancestro menos común de dos vértices). La idea es calcular para cada vértice un ancestro a 2k de él para todo k , y usar esa información para acelerar el algoritmo ingenuo anterior.
• Algoritmo de Tarjan en el tiempo O ( n α ( n ) + m ), donde m es el número de solicitudes. Sin embargo, este es el llamado algoritmo fuera de línea: requiere que todas las solicitudes estén disponibles con anticipación, antes de que comience el trabajo.
• Algoritmo de Bender-Farah-Colton que requiere O ( n ) tiempo de preprocesamiento y O (1) tiempo de consulta.

Literatura

• Bender M., Farach-Colton M. El problema LCA revisado  // Actas del 4to Simposio Latinoamericano de Informática Teórica. - Springer-Verlag, 2000. - vol. 1776. - Pág. 88-94. -doi : 10.1007/ 10719839_9 .

Enlaces

• Implementación del Algoritmo de Bender-Farah-Colton por David Epstein