h1. LCA: Lowest common ancestor

(Creat de '_wickedman_':user/wickedman la data de _2004-11-08_ categoria _Arbori_, autor(i) _Miron Emilian_)

(Categoria _Algoritmi_, Autor _Emilian Miron_)

Problema luata in discutie este ca, avand un arbore dat, sa putem raspunde rapid la multe intrebari de genul: _"Care este stramosul comun cel mai apropiat dintre doua noduri din arbore?"_.

h2. Exemplu

(toc)*{text-align:center} *Continut*
* 'Exemplu':lowest-common-ancestor#exemplu
* 'Aplicabilitate':lowest-common-ancestor#aplicabilitate
* 'Mod de calcul':lowest-common-ancestor#calcul

!http://www.infoarena.ro/LCA_Lowest_common_ancestor?action=download&file=euler.jpg!

!> Lowest-common-ancestor?euler.jpg 80%!
 
h2(#exemplu). Exemplu

Pentru arborele din imagine, avem ca exemplu urmatoarele query-uri:

* $lca(1,5) = 1$
* $lca(5,3) = 3$

h2. Aplicabilitate

h2(#aplicabilitate). Aplicabilitate

Dandu-se un arbore cu costuri sa se raspunda rapid la intrebari de genul: _"care este distanta minima intre doua noduri date?"_. O solutie pentru problema de fata ar fi:
* agatam arborele intr-un nod oarecare si obtinem un arbore cu radacina

* pentru fiecare nod precalculam {$dist{~i~}$}, reprezentand distanta sa pana la radacina

* pentru fiecare nod $i$ precalculam {$dist{~i~}$}, reprezentand distanta sa pana la radacina

* precalculam cele necesare pentru algoritmul de _Lowest Common Ancestor_

* raspundem la intrebari de forma {$d{~i,j~}$} prin {$dist{~i~} + dist{~j~} - dist{~lca{~i,j~}~}$}

* distanta dintre doua noduri oarecare $i$ si $j$ va fi egala cu {$dist{~i~} + dist{~j~} - 2*dist{~lca(i,j)~}$}

h2. Mod de calcul

h2(#calcul). Mod de calcul

In prima etapa a algoritmului facem o parcurgere euleriana a arborelui dat. O parcurgere euleriana este o parcurgere a arborelui in ordinea din figura: se parcurg fii si se intercaleaza intre ei tatal, obtinand o parcurgere continua.

In prima etapa a algoritmului facem o parcurgere euleriana a arborelui dat. O parcurgere euleriana este o parcurgere a arborelui in ordinea din figura: se parcurg fiii si se intercaleaza intre ei tatal, obtinand o parcurgere continua.

Mai exact pentru fiecare nod procedam astfel, incepand cu radacina:

* daca are fii atunci il punem la inceput, la sfarsit si intre parcurgerile euler ale fiilor
Cand facem aceasta parcurgere retinem de asemenea si urmatoarele informatii suplimentare:

* adancimea fiecarui nod din parcurgere, obtinand un sir de adancimi
* una din pozitiile pe care fiecare nod apare in parcurgere

Pentru perechea de noduri ({$4, 3$}), avem {$lca(4, 3)$} egal cu nodul care se gaseste intre {$poz{~4~}$} si {$poz{~3~}$} in parcurgerea euler si are adancimea minima. Acest nod este $1$, deci {$lca(4, 3) = 1$}.

Am redus problema la aflarea minimului intre doua pozitii ale unui sir (_Range Minimum Query_). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar ({$Nlog{~2~}N$}) a minimelor pe intervale de puteri ale lui {$2$}, incepand de la pozitia {~i~}. Timpul de preprocesare este {~O(N)~} pentru arbori de intervale si {$O(Nlog{~2~}N)$} pentru a doua metoda. In ambele variante timpul de interogare este {$O(log{~2~}N)$}.
Vom prezenta in continuare metoda cu spatiu supraliniar. Calculam minimele inductiv, pastrand {$min{~i,k~}$} = minimul pe intervalul {$[i...i + 2^k^ - 1]$} (de lungime {$2{^k^}$}), si {$minpos{~i,k~}$} = pozitia minimului de pe intervalul {$[i...i + 2^k^ - 1]$}. Acest tablou va fi construit recursiv: pentru $k = 0$ avem {$min{~i,0~} = a~i~$} si {$minpos{~i,0~} = i$} si pentru k > 0 avem:
* {$min{~i,k~}$} = minim({$min{~i,k-1~}$}, {$min{~i+2{^k-1^},k-1~}$})

Am redus problema la aflarea minimului intre doua pozitii ale unui sir ({_Range Minimum Query_}). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar ({$Nlog{~2~}N$}) a minimelor pe intervale de puteri ale lui {$2$}, incepand de la pozitia {$i$}. Timpul de preprocesare este {$O(N)$} pentru arbori de intervale si {$O(Nlog{~2~}N)$} pentru a doua metoda. In ambele variante timpul de interogare este {$O(log{~2~}N)$}.
 
Vom prezenta in continuare metoda cu spatiu supraliniar. Calculam minimele inductiv, pastrand:
 
* {$min{~i,k~}$} = minimul pe intervalul {$[i...i+2^k^-1]$} (de lungime {$2^k^$}), si
* {$minpos{~i,k~}$} = pozitia minimului de pe intervalul {$[i...i+2^k^-1]$}.
 
Acest tablou va fi construit recursiv astfel: pentru $k = 0$ avem {$min{~i,0~} = a{~i~}$} si {$minpos{~i,0~} = i$}, iar pentru k > 0 avem:
 
* {$min{~i,k~}$} = minim({$min{~i,k-1~}$}, {$min{~i+2^k-1^,k-1~}$})

* {$minpos{~i,k~}$} = pozitia minimului ({$minpos{~i,k-1~}$} sau {$minpos{~i+2{^k-1^},k-1~}$})
Pentru _query_ intre pozitiile $l$ si $r$ procedam astfel: fie $k$ cel mai mare numar astfel incat {$2^k^$} ≤ lungimea intervalului {$(l, r)$}.

     min(l, r) = minim( min[l][k], min[r * 2^k + 1][k])
     pozmin(l, r) = pozitia minimului

     {$min(l, r)$} = minim( {$min{~l,k~}$}, {$minimul pe intervalul (l+2^k^, r)$})
     {$pozmin(l, r)$} = pozitia minimului intre $l$ si $r$

Daca {$l = pos{~i~}$} si {$r = pos{~j~}$} ({$pos{~i~} < pos{~j~}$}) la sfarsitul _query_-ului {$euler{~pozmin~}$} este chiar {$lca(i, j)$}.

3699