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?"_.

+Exemplu+

(toc)*{text-align:center} *Continut*
* 'Exemplu':lowest-common-ancestor#exemplu
* 'Aplicabilitate':lowest-common-ancestor#aplicabilitate
* 'Mod de calcul':lowest-common-ancestor#calcul
 
!> 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$

+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?"_.
 
+Solutie:+

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
* precalculam cele necesare pt LCA
* raspundem la intrebari de forma d(i,j) prin dist[i] + dist[j] * 2 * dist(lca(i,j))
* Probleme _adhoc_ care se reduc sau folosesc LCA. (de exemplu problema petrol (baraje Slatina 2003)

* pentru fiecare nod $i$ precalculam {$dist{~i~}$}, reprezentand distanta sa pana la radacina
* precalculam cele necesare pentru algoritmul de _Lowest Common Ancestor_
* distanta dintre doua noduri oarecare $i$ si $j$ va fi egala cu {$dist{~i~} + dist{~j~} - 2*dist{~lca(i,j)~}$}

+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

Ideea este ca {$lca(i, j)$} este chiar nodul cu cea mai mica adancime intre pozitiile lui $i$ si a lui $j$ in parcurgere. Pentru graful din figura avem:

Ideea este ca {$lca(i, j)$} este chiar nodul cu cea mai mica adancime intre pozitiile lui $i$ si a lui $j$ in parcurgere. Pentru graful din figura de mai sus avem:

table(example). |_. Euler|_. Adancimi|

table(example). |_. Euler|_. Adancimi|

|12421353631|12321232321|

4 3
 
lca(4,3)=min(adancimi de la pos[4] la pos[3]) = 1
 
Am redus problema la aflarea minimului intre doua pozitii a unui sir (RMQ * range minimum query). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar (NlgN) a minimelor pe intervale de puteri de 2, incepand de la pozitia i. Timpul de preprocesare este O(N) pentru arbori de intervale si O(NlgN) pentru a doua metoda. Timpul de interogare este O(lgN);
Vom discuta metoda cu spatiu NlgN. Calculam minimele inductiv, pastrand min[i][k] = minimul pe intervalui i..i + 2^k * 1 (de lungime 2^k), si minpos[i][k] pozitia minimului de pe intervalul i..i + 2^k * 1.
 
pt k = 0
min[i][0] = a[i], minpos[i][0] = i;
 

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)$}.

pt k > 0
min[i][k] = minim(min[i][k-1],min[i+2^(k-1)][k-1])
minpos[i][k] = pozitia minimului

Vom prezenta in continuare metoda cu spatiu supraliniar. Calculam minimele inductiv, pastrand:

(minpos[i][k-1] sau minpos[i+2^(k-1)][k-1])

* {$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]$}.

Pentru query intre pozitiile l, r procedam astfel:
Fie k cel mai mare nr astfel incat 2^k <= lungimea intervalului (r * l + 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(l, r) = minim( min[l][k], min[r * 2^k + 1][k])

* {$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~}$})

pozmin(l, r) = pozitia minimului

Pentru _query_ intre pozitiile $l$ si $r$ procedam astfel: fie $k$ cel mai mare numar astfel incat {$2^k^$} ≤ lungimea intervalului {$(l, r)$}.

Daca l = pos[i], r = pos[j] (pos[i] < pos[j]) la sfarsitul query-ului euler[pozmin] este chiar lca(i, j).

     {$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