Vähiten yhteinen esi-isä

Juurtun puun T kärkien u ja v vähiten yhteinen esi-isä ( alin yhteinen esi -isä ) on puun juuresta kauimpana oleva kärki, joka sijaitsee molemmilla poluilla u :sta ja v :stä juureen, eli on molempien esi-isä. kärjet. Yleisesti hyväksytty lyhenne on LCA englannista. alin (vähiten) yhteinen esi-isä .  

Algoritmit

Yksinkertaisin ja naiivein algoritmi vähiten yhteisen esivanhemman löytämiseksi on laskea u :n ja v :n syvyydet ja edetä asteittain ylös puuta jokaisesta kärjestä, kunnes yhteinen kärki löytyy:

Toimenpide LCA( u , v ): h1 := syvyys( u ) // syvyys( x ) = kärjen syvyys x h2 := syvyys( v ) kun taas h1 ≠ h2: jos h1 > h2: u  := vanhempi( u ) h1 := h1 - 1 muu : v  := vanhempi( v ) h2 := h2 - 1 kun taas u ≠ v : u  := vanhempi( u ) // vanhempi( x ) = x : n välitön esi-isä v  := vanhempi( v ) palauta u

Tämän algoritmin ajoaika on O ( h ), missä h  on puun korkeus. Lisäksi voidaan vaatia O ( n ) -aikaista esikäsittelyä puun kaikkien solmujen välittömän esivanhemman löytämiseksi (mutta tämä rakenne on yleensä jo olemassa puussa).

On kuitenkin olemassa nopeampia algoritmeja:

• Binäärinen nostoalgoritmi, joka vaatii O ( n log n ) esikäsittelyaikaa ja O (log n ) kyselyaikaa (laskee kahden kärjen vähiten yhteisen esi-isän). Ajatuksena on laskea jokaiselle pisteelle esi-isä, joka on 2k:n päässä siitä kaikelle k : lle , ja käyttää tätä tietoa nopeuttamaan yllä olevaa naiivia algoritmia.
• Tarjanin algoritmi ajassa O ( n α ( n ) + m ), missä m on pyyntöjen lukumäärä . Tämä on kuitenkin niin kutsuttu offline-algoritmi: se edellyttää, että kaikki pyynnöt ovat saatavilla etukäteen, ennen työn aloittamista.
• Bender-Farah-Colton-algoritmi, joka vaatii O ( n ) esikäsittelyaikaa ja O (1) kyselyaikaa.

Kirjallisuus

• Bender M., Farach-Colton M. LCA-ongelma uudelleen  // Proceedings of the 4th Latin American Symposium on Theoretical Informatics. - Springer-Verlag, 2000. - Voi. 1776. - s. 88-94. - doi : 10.1007/10719839_9 .

Linkit

• David Epsteinin Bender-Farah-Colton-algoritmin toteutus