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?". 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 pentru algoritmul de Lowest Common Ancestor
• raspundem la intrebari de forma d_i,j prin dist_i + dist_j - dist_lcai,j

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 de mai sus avem:

Pentru perechea de noduri (4, 3), avem lca(4, 3) egal cu nodul care se gaseste intre poz₄ si poz₃ 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₂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₂N) pentru a doua metoda. In ambele variante timpul de interogare este O(log₂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})
* 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

Daca l = pos_i si r = pos_j (pos_i < pos_j) la sfarsitul query-ului euler_pozmin este chiar lca(i, j).