A legkevésbé közös ős

Az u és v csúcsok legkevésbé közös őse ( legalacsonyabb közös őse ) a T gyökerező fában a fa gyökerétől legtávolabbi csúcs, amely mindkét u -tól és v -től a gyökérig vezető úton fekszik, azaz mindkettő őse. csúcsok. Az általánosan elfogadott rövidítés az angol LCA. legalacsonyabb (legkisebb) közös ős .  

Algoritmusok

A legegyszerűbb, legnaivabb algoritmus a legkevésbé közös ős megtalálására az, hogy kiszámítja az u és a v mélységét, és fokozatosan halad felfelé a fán minden csúcstól, amíg meg nem talál egy közös csúcsot:

Eljárás LCA( u , v ): h1 := mélység( u ) // mélység( x ) = csúcsmélység x h2 := mélység( v ) míg h1 ≠ h2: ha h1 > h2: u  := szülő( u ) h1 := h1 - 1 else : v  := szülő( v ) h2 := h2 - 1 míg u ≠ v : u  := szülő( u ) // szülő( x ) = x közvetlen őse v  := szülő( v ) vissza u

Ennek az algoritmusnak a futási ideje O ( h ), ahol h  a fa magassága. Ezen kívül O ( n ) időbeli előfeldolgozásra lehet szükség , hogy megtaláljuk a fa összes csomópontjának közvetlen ősét (de ez a struktúra általában már jelen van a fában).

Vannak azonban gyorsabb algoritmusok:

• Bináris emelési algoritmus, amely O ( n log n ) előfeldolgozási időt és O (log n ) lekérdezési időt igényel (két csúcs legkevésbé közös ősének kiszámítása). Az ötlet az, hogy minden csúcsra kiszámítunk egy tőle 2k távolságra lévő őst minden k esetén , és ezt az információt felhasználjuk a fenti naiv algoritmus felgyorsítására.
• Tarján algoritmusa O időben ( n α ( n ) + m ), ahol m a lekérdezések száma . Ez azonban az úgynevezett offline algoritmus: megköveteli, hogy minden kérés előre, a munka megkezdése előtt elérhető legyen.
• Bender-Farah-Colton algoritmus, amely O ( n ) előfeldolgozási időt és O (1) lekérdezési időt igényel.

Irodalom

• Bender M., Farach-Colton M. The LCA problem revisited  // Proceedings of the 4th Latin American Symposium on Theoretical Informatics. - Springer-Verlag, 2000. - Vol. 1776. - P. 88-94. - doi : 10.1007/10719839_9 .

Linkek

• A Bender-Farah-Colton algoritmus megvalósítása , David Epstein