{"id":383,"date":"2022-06-06T16:42:22","date_gmt":"2022-06-06T16:42:22","guid":{"rendered":"https:\/\/solinfo.ro\/blog\/?p=383"},"modified":"2024-05-17T20:31:18","modified_gmt":"2024-05-17T20:31:18","slug":"arbori-cu-radacina-lowest-common-anscestor-folosind-eulers-tour","status":"publish","type":"post","link":"https:\/\/solinfo.ro\/blog\/arbori-cu-radacina-lowest-common-anscestor-folosind-eulers-tour\/","title":{"rendered":"Arbori cu r\u0103d\u0103cin\u0103 – Lowest Common Ancestor folosind Euler’s Tour"},"content":{"rendered":"\n

Fiind date dou\u0103 noduri p \u0219i q dintr-un arbore cu r\u0103d\u0103cin\u0103, numim lowest common ancestor<\/em> nodul de intersec\u021bie al lui p \u0219i q \u00een drumul lor spre r\u0103d\u0103cin\u0103.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

\u00cen acest arbore cu r\u0103d\u0103cina \u00een nodul 1, lca(4, 8) este 2, iar lca(6, 7) este chiar 6. La cazul general, lca(p, q), unde p \u0219i q sunt noduri ale arborelui, este primul str\u0103mo\u0219 comun al celor dou\u0103 noduri. Ca o mic\u0103 observa\u021bie, lca(p, q) poate fi chiar p sau q (exemplu: lca(6, 7) = 6). <\/p>\n\n\n\n

Se pune problema determin\u0103rii lca-ului \u00eentr-un mod c\u00e2t mai eficient. O prim\u0103 variant\u0103, care nu este foarte eficient\u0103 \u0219i care este mai greu de \u00een\u021beles folose\u0219te no\u021biunea de binary lifting.<\/strong> Pentru a folosi ceea ce am prezentat \u00een articolul anterior<\/a>, ne vom concentra pe solu\u021bia cea mai eficient\u0103, folosind euler’s tour.<\/strong><\/p>\n\n\n\n

Pentru \u00eenceput, s\u0103 explic\u0103m la ce se refer\u0103 parcurgerea de tip euler a unui arbore. Vizual, ea poate fi v\u0103zut\u0103 \u00een felul urm\u0103tor:<\/p>\n\n\n\n

\n
\"\"<\/figure>\n<\/figure>\n\n\n\n

Acest tip de parcurgere ne poate ajuta s\u0103 transform\u0103m arborele \u00eentr-un vector. Pe exemplul de mai jos, vectorul, s\u0103-l numim e[]<\/strong>, arat\u0103 astfel:<\/p>\n\n\n\n

e[] = {1, 2, 4, 2, 5, 8, 5, 9, 5, 2, 1, 3, 6, 7, 6, 3, 1} <\/pre>\n\n\n\n
Acest vector \u00eel putem ob\u021bine \u00een urma unei simple parcurgeri DFS, astfel: <\/p>\n\n\n\n
void dfs(int x){\n\n    e[++ne] = x;\n\n    for(auto y : fii[x]){\n\n        dfs(y);\n        e[++ne] = x;\n\n    }\n\n}<\/pre>\n\n\n\n
Dimensiunea vectorului e[]<\/strong> va fi exact 2 * num\u0103rul_de_noduri – 1<\/em> , deoarece trebuie s\u0103 vizit\u0103m de dou\u0103 ori fiecare muchie a arborelui plus r\u0103d\u0103cina arborelui.<\/p>\n\n\n\n
Pentru a r\u0103spunde eficient la \u00eentreb\u0103rile de genul „care este lca-ul nodurilor p<\/strong> \u0219i q<\/strong>„, vom avea nevoie de \u00eenc\u0103 doi vectori, nivel[i] = nivelul pe care se afl\u0103 nodul i<\/strong> \u0219i poz[i] = prima apari\u021bie a nodului x \u00een vectorul e[]. <\/strong>A\u0219adar, noul DFS va ar\u0103ta astfel:<\/p>\n\n\n\n
void dfs(int x){\n\n    e[++ne] = x;\n    poz[x] = ne;\n\n    for(auto y : fii[x]){\n\n        nivel[y] = 1 + nivel[x];\n\n        dfs(y);\n        e[++ne] = x;\n\n    }\n\n}<\/pre>\n\n\n\n
Acum vom \u00eencepe construirea matricei de dimensiune [log2(ne) + 1] * ne<\/strong> cu ajutorul c\u0103reia vom r\u0103spunde la fiecare query. Vom face aproximativ acela\u0219i lucru ca la algoritmul clasic de rmq, doar c\u0103 trebuie s\u0103 fim aten\u021bi s\u0103 lucr\u0103m cu noduri, adic\u0103 prima liniei a matricei va fi chiar vectorul e[]<\/strong>. <\/p>\n\n\n\n
Secven\u021ba \u00een care vom c\u0103uta r\u0103spunsul (nodul cu nivel minim)  este delimitat\u0103 de prima apari\u021bie a nodului p <\/strong>\u00een e[]<\/strong> \u0219i prima apari\u021bie a nodului q<\/strong> \u00een e[]<\/strong>.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Pe acest exemplu, dintre nodurile 4, 2, 5, 8<\/strong>, nodul 2<\/strong> se afl\u0103 pe nivelul minim.<\/p>\n\n\n\n
Fie r[i][j] = nodul care se afl\u0103 pe nivelul minim \u00een arbore, din secven\u021ba de lungime 2^i care se termin\u0103 pe pozi\u021bia j, din vectorul e[]<\/strong><\/pre>\n\n\n\n
Vom construi simultan cu prima liniei a matricei \u0219i vectorul lg2[i] = [log2(i)]<\/strong>, de dimensiune 2 * num\u0103rul_de_noduri – 1<\/em>:<\/p>\n\n\n\n
    lg2[0] = -1; \/\/ pentru ca lg2[1] = 1 + lg2[0], adic\u0103 0\n    for(int i = 1; i <= ne; i++){\n\n        lg2[i] = 1 + lg2[i >> 1];\n        r[0][i] = e[i];\n\n    }<\/pre>\n\n\n\n
Pentru restul matricei, vom aborda o tehnic\u0103 similar\u0103 algoritmului clasic de rmq, unde, pentru o secven\u021b\u0103 care se termin\u0103 pe pozi\u021bia j \u0219i are lungimea 2^i, vom compara nivelele<\/strong> pe care se afl\u0103 nodurile de nivel minim din cele dou\u0103 secven\u021be de lungime 2^(i – 1), care, intersectate sau nu, formeaz\u0103 secven\u021ba curent\u0103, adic\u0103 r[i – 1][j] \u0219i r[i – 1][j – p], unde p = 1 << (i – 1):<\/p>\n\n\n\n
for(int i = 1; (1 << i) <= ne; i++){\n        for(int j = (1 << i); j <= ne; j++){\n\n            r[i][j] = r[i - 1][j]; \/\/ presupunere ini\u021bial\u0103\n            int p = (1 << (i - 1));\n\n            if(nivel[r[i - 1][j - p]] < nivel[r[i - 1][j]]) \/\/ \u00een caz contrar\n                r[i][j] = r[i - 1][j - p];\n\n        }\n    }<\/pre>\n\n\n\n
Ne mai r\u0103m\u00e2ne a\u0219adar s\u0103 r\u0103spundem la \u00eentreb\u0103rile de forma „care este lca-ul nodurilor p <\/strong>\u0219i q<\/strong>?”. A\u0219a cum am spus mai devreme, vom c\u0103uta \u00een secven\u021ba delimitat\u0103 de prima apari\u021bie a nodului p \u0219i cea a nodului q, din e[]<\/strong>, nodul cu nivel minim:<\/p>\n\n\n\n
int lca(int x, int y){\n\n\n\/\/ pentru a \u00een\u021belege mai bine, se recomand\u0103 citirea articolului despre rmq<\/a>\n\n    int st = poz[x], dr = poz[y]; \/\/ secven\u021ba din vectorul e<\/strong>\n    if(st > dr) \n        swap(st, dr);\n\n    int l = lg2[dr - st + 1]; \/\/ similar rmq clasic\n    int p = (1 << l); \/\/ similar rmq clasic\n    x = r[l][st + p - 1]; \n    y = r[l][dr];\n    if(nivel[x] > nivel[y]) \/\/ compar\u0103m nodurile de nivel minim din fiecare secven\u021b\u0103\n        x = y;\n\n    return x;\n}<\/pre>\n\n\n\n
Autor: Pirnog Theodor Ioan<\/p>\n\n\n\n
Colegiul Na\u021bional „B. P. Hasdeu”, Buz\u0103u<\/p>\n","protected":false},"excerpt":{"rendered":"
Fiind date dou\u0103 noduri p \u0219i q dintr-un arbore cu r\u0103d\u0103cin\u0103, numim lowest common ancestor nodul de intersec\u021bie al lui … <\/p>\n","protected":false},"author":3,"featured_media":407,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-383","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/comments?post=383"}],"version-history":[{"count":14,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/383\/revisions"}],"predecessor-version":[{"id":406,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/posts\/383\/revisions\/406"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media\/407"}],"wp:attachment":[{"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/media?parent=383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/categories?post=383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solinfo.ro\/blog\/wp-json\/wp\/v2\/tags?post=383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}