Diferente pentru lowest-common-ancestor intre reviziile #28 si #20

Nu exista diferente intre titluri.

Diferente intre continut:

h1. LCA: Lowest common ancestor
(Categoria _Algoritmi_, Autor _Emilian Miron_)
(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?"_.
(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%!
* 'Exemplu':lca-lowest-common-ancestor#exemplu
* 'Aplicabilitate':lca-lowest-common-ancestor#aplicabilitate
* 'Mod de calcul':lca-lowest-common-ancestor#calcul
h2(#exemplu). Exemplu
!LCA-Lowest-common-ancestor?euler.jpg!
 
Pentru arborele din imagine, avem ca exemplu urmatoarele query-uri:
* $lca(2,3) = 1$
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)$}.
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:

Nu exista diferente intre securitate.

Diferente intre topic forum:

3699