Ancestro comú més baix

Archiu:Lowest common ancestor.svg

En este arbre, el ancestro comú més baix dels nodos color vert clar, és el nodo de color vert obscur.

El ancestro comú més baix (ACB) és un concepte dins de la teoria de grafos i ciències de la computació. Siga T un arbre en raïl i n nodos. El ancestro comú més baix entre dos nodos v i w es definix com el nodo més baix en T que té a v i w com a descendents (a on es permet a un nodo ser descendent d'ell mateixa).

El ACB de v i w en T és el ancestro compartit de v i w que està localisat més llunt de la raïl. El còmput del ancestro comú més baix pot ser útil, per eixemple, com a part d'un procediment per a determinar la distància entre parells de nodos en un arbre: la distància de v a w pot ser calculada com la distància des de la raïl fins a v, sumada en la distància des de la raïl fins a w, menys dos voltes la distància des de la raïl fins a la seua ancestro comuna més baix.

En una estructura de senyes arbre a on cada nodo referència al seu pare, el ancestro comú més baix pot ser determinat de forma molt simple, trobant la primera intersecció dels camins des de v and w fins a la raïl. En general, el temps computacional requerit per este algoritme és O(h) a on h és l'altura de l'arbre (llongitut del camí més llarc des d'un full fins a la raïl). No obstant, existixen molts algoritmes per a processar arbres en els que el ancestro comú més baix pot ser trobat de forma més ràpida.

Es pot buscar en temps constant per pregunta despuix d'un preprocesamiento en temps llineal.

Sense preprocesamiento es pot millorar el temps de còmput de l'algoritme ingenu fins a O(log h) almagasenant els camins a través de l'arbre usant skew-binary random access lists, premitiendo encara a l'arbre ser estés en temps constant (Edward Kmett (2012)).

Història

El problema del ancestro comú més baix va ser definit per Alfred Aho, Jonh Hopcroft i Jeffry Ullman en 1973, pero Harel Dov i Robert Tarjan varen ser els primers en desenrollar una estructura de senyes òptima i eficient per a trobar el ancestro comú més baix. El seu algoritme processa qualsevol arbre en temps llineal, usant una descomposició de camins fort, aixina les preguntes subsegüents pel ancestro comú més baix poden ser respostes en temps constant per pregunta. No obstant, la seua estructura de senyes és complexa i difícil d'implementar. Tarjan també va trobar un simple, pero menys eficient algoritme, basat en l'estructura de senyes conjunts disjuntos.

En 1988 Baruch Schieber i Uzi Vishkin varen simplificar l'estructura de senyes de Harel i Tarjan, conseguint una estructura implementable en el mateix preprocesamiento asintòtic i rancs de temps per pregunta. La seua simplificació està basada en el principi que, en dos tipos especials d'arbres, els ancestros comuns més baixos són fàcils de determinar: si l'arbre és un camí, llavors el ancestro comú més baix pot ser computat simplement del mínim entre els nivells dels dos nodos pels que s'està preguntant, mentres que si l'arbre és un arbre binario complet, els nodos poden ser indexats de forma tal que el ancestro comú més baix es reduïx a una simple operació binaria entre índexs. L'estructura de Schieber i Vishkin descompon qualsevol arbre en una colecció de camins, tal que les conexions entre els camins tenen l'estructura d'arbre binario, i combina abdós d'estes dos simples tècniques d'indexat.

En 1993 Omer Berkman i Uzi Vishkin varen descobrir una forma completament nova per a respondre preguntes sobre el ancestro comú més baix, conseguint de nou preprocesamiento en temps llineal en preguntes en temps constant. El seu método funciona formant un cicle de euler d'un grafo format per l'arbre d'entrada doblant cada aresta, usant este camí per a escriure una seqüència de números de nivells dels nodos en l'orde en que el camí els visita; la pregunta sobre el ancestro comú més baix pugues llavors ser transformada en una pregunta que busque el valor mínim dins d'algun subintervalo d'esta seqüència de números. Ells llavors varen manipular este problema mínim valor en un ranc combinant dos tècniques, una tècnica basada en precomputar les preguntes en intervals llarcs que tenen tamany potencies de dos, i l'atra basada en una taula per a buscar en intervals menuts. Este método va ser presentat més vesprada en una forma simplificada per Michael Bender i Martin Farach-Colton en el 2000. Com va ser prèviament observat per Gabow, Bentley i Tarjan en 1984, el problema del mínim en un ranc pot ser transformat cap a arrere en el problema del ancestro comú més baix usant la tècnica d'arbres cartesianos.

Atres simplificació varen ser fetes per Alstrup, Gavoille, Kaplan i Rauhe en 2004 i Fischer i Heun en 2006.

Referències

• (1973).«Proc. 5th ACM Symp. Theory of Computing (STOC)».

253–265.doi:10.1145/800125.804056..

• . A preliminary version appeared in SPAA 2002.
• .
• .
• .
• .
• .
• .