Strămoșul cel mai puțin comun

Strămoșul cel mai puțin comun ( cel mai mic strămoș comun ) al vârfurilor u și v din arborele înrădăcinat T este vârful cel mai îndepărtat de rădăcina copacului, situat pe ambele căi de la u și v până la rădăcină, adică fiind strămoșul ambelor vârfuri. Abrevierea general acceptată este LCA din engleză.  cel mai mic (cel mai puțin) strămoș comun .

Algoritmi

Cel mai simplu, cel mai naiv algoritm pentru găsirea strămoșului cel mai puțin comun este să calculați adâncimile lui u și v și să vă urcați treptat în arbore de la fiecare vârf până când este găsit un vârf comun:

Procedura LCA( u , v ): h1 := adâncime( u ) // adâncime( x ) = adâncimea vârfului x h2 := adâncime( v ) în timp ce h1 ≠ h2: dacă h1 > h2: u  := părinte( u ) h1 := h1 - 1 else : v  := părinte( v ) h2 := h2 - 1 în timp ce u ≠ v : u  := părinte( u ) // părinte( x ) = strămoșul imediat al lui x v  := părinte( v ) întoarce- te

Timpul de rulare al acestui algoritm este O ( h ), unde h  este înălțimea arborelui. În plus, poate fi necesară preprocesarea timpului O ( n ) pentru a găsi strămoșul imediat al tuturor nodurilor din arbore (dar această structură este de obicei deja prezentă în arbore).

Cu toate acestea, există algoritmi mai rapizi:

• Algoritm de ridicare binar care necesită timp de preprocesare O ( n log n ) și timp de interogare O (log n ) (calculând cel mai puțin strămoș comun a două vârfuri). Ideea este de a calcula pentru fiecare vârf un strămoș la 2k de acesta pentru toate k și de a utiliza aceste informații pentru a accelera algoritmul naiv de mai sus.
• Algoritmul lui Tarjan în timp O ( n α ( n ) + m ), unde m este numărul de interogări. Cu toate acestea, acesta este așa-numitul algoritm offline: necesită ca toate solicitările să fie disponibile în avans, înainte de începerea lucrărilor.
• Algoritmul Bender-Farah-Colton care necesită O ( n ) timp de preprocesare și O (1) timp de interogare.

Literatură

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

Link -uri

• Implementarea algoritmului Bender-Farah-Colton de David Epstein