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:

Literatură

Link -uri