LCA: Lowest common ancestor

(Creat de wickedman la data de 2004-11-08 categoria Arbori, autor(i) Miron Emilian)

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

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

• lca(2,3) = 1
• lca(4,5) = 1
• lca(5,6) = 3
• lca(1,5) = 1
• lca(5,3) = 3

Aplicabilitate

Dandu-se un arbore cu costuri sa se raspunda rapid la intrebari de genul: "care este distanta minima intre doua noduri date?".

Solutie:

• 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)

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.

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

• daca nodul curent este frunza il adaugam la parcurgere
• 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:

4 3

lca(4,3)=min(adancimi de la pos⁴ la pos³) = 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]⁰ = a[i], minpos[i]⁰ = i;

pt k > 0
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, r procedam astfel:
Fie k cel mai mare nr astfel incat 2^k <= lungimea intervalului (r * l + 1)

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

pozmin(l, r) = pozitia minimului

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