Cel mai mic stramos comun al mai multor noduri dintr-un n-arbore

I am trying to implement LCA of multiple nodes in an n-ary tree in java. I am working with parse trees of sentences, So its reasonable to assume that number of children of a node <= 6. Multiple nodes here are two phrases(continuous word sequence) in a sentence. Let k be the number of nodes involved.

O modalitate este de a găsi LCA a două noduri pentru k/2 perechi și vom obține k/2 noduri. Acum folosiți aceste noduri k/2. Ordinea va fi O (nlog k), unde O (n) este complexitatea algoritmilor liniari de găsire a LCA. Pot să o fac mai eficient?

0
@VSOverFlow Voi avea etape log (k) și fiecare pas ia O (n), prin urmare, în general O (nlog k). Ce este O (k) în calculele tale?
adăugat autor damned, sursa
Cred că complexitatea este O (n.k) nu O (n.log (k)). Veți avea etape log (k) de k/2, k/4 .. care este O (k).
adăugat autor VSOverFlow, sursa
Presupun că LCA (2, n) este O (n). Când construiți arborele binar, numărul total de apeluri LCA este O (k) (k/2 + k/4 + ....). Astfel, complexitatea runtime-ului total este O (n * k) (adică k apelurile lui O (n)). Fiecare dintre etapele log (k) are mai multe etape O (n) (k/2, k/4, k/8, ...)
adăugat autor VSOverFlow, sursa

1 răspunsuri

Am rezolvat problema utilizând faptul că nodurile expresiilor sunt continue, adică au indici continuu în lista de noduri de frunze ale unui arbore de analiză.

Fie segment1 indicii de la start1 la end1 . Același lucru este cazul segment2 = (start2, end2) .

Stâlpul obișnuit necesar al (start1, end1) și (start2, end2) este strămoșul comun al nodurilor cu indicii min (start1, start2) > și max (sfârșitul1, sfârșitul2) .

0
adăugat
Ideea este că, dacă toate nodurile sunt noduri frunze consecutive, LCA a tuturor acestor noduri va fi LCA de prim și ultim nod.
adăugat autor damned, sursa
poți să dai o metodă completă? Nu reușesc să convertesc algoritmul în cod real.
adăugat autor javafan, sursa