Vectorul de tați la BAC: rădăcină, frunze și niveluri

Vectorul de tați memorează, pentru fiecare nod al unui arbore cu rădăcină, părintele său direct. În convenția folosită aici, rădăcina are valoarea zero în vector. Fiii unui nod sunt pozițiile la care apare eticheta lui, iar frunzele sunt nodurile care nu au fii. Cu aceste trei reguli poți reconstrui arborele fără să ghicești din forma desenului.

Lecția privește arborii cu rădăcină din pregătirea BAC la matematică-informatică. Exemplele pornesc de la vectori declarați valizi. La final verificăm și două erori care împiedică un vector oarecare să reprezinte un arbore.

Ce înseamnă poziția și ce înseamnă valoarea?

În vectorul t, poziția i identifică nodul, iar valoarea t[i] identifică tatăl acelui nod. Dacă t[5]=2, nodul cinci este fiul nodului doi. Nu rezultă că doi este fiul lui cinci; inversarea rolurilor schimbă toate nivelurile.

Folosim etichetele de la unu la n, iar zero este doar un marcaj. Nu desenăm un nod suplimentar cu eticheta zero. Rădăcina nu are tată în arbore, de aceea valoarea ei este diferită de toate etichetele valide.

Un nod poate avea mai mulți fii, dar orice nod diferit de rădăcină are exact un tată. Această asimetrie explică de ce aceeași valoare poate apărea de mai multe ori în vector, în timp ce fiecare poziție conține o singură valoare.

Exemplu complet cu opt noduri

Considerăm vectorul de mai jos. Rândul pozițiilor este inclus pentru a preveni citirea deplasată cu o căsuță.

Nod i	1	2	3	4	5	6	7	8
Tată t[i]	3	3	0	1	1	2	6	6

Zero apare la poziția trei, deci rădăcina este nodul trei. Valoarea trei apare la pozițiile unu și doi, astfel că aceștia sunt fiii rădăcinii. Valoarea unu apare la pozițiile patru și cinci, iar valoarea doi apare la poziția șase.

Nodul șase are fiii șapte și opt. Etichetele patru, cinci, șapte și opt nu apar ca tați ai altor noduri, deci acestea sunt frunzele. Nu căutăm zerouri pentru frunze: zero identifică rădăcina, nu lipsa fiilor.

        3
      /   \
     1     2
    / \    |
   4   5   6
          / \
         7   8

Desenul este o schemă a relațiilor, nu o ordine obligatorie de afișare. Poți inversa poziția din pagină a fiilor unu și doi fără să schimbi vectorul. Etichetele și muchiile determină arborele, nu orientarea hârtiei.

Cum afli nivelul unui nod?

Stabilim rădăcina la nivelul zero. Nivelul unui nod este numărul muchiilor de pe drumul de la rădăcină la acel nod. Pentru a-l calcula din vector, urci repetat la tată până ajungi la rădăcină și numeri trecerile.

Pentru șapte, urcarea este șapte, șase, doi, trei. Sunt trei treceri, deci nivelul este trei. Nu numeri cele patru etichete ca patru muchii. Pentru rădăcină, nu faci nicio trecere, iar nivelul este zero.

Nivel	Noduri
0	3
1	1, 2
2	4, 5, 6
3	7, 8

Înălțimea arborelui este trei dacă o măsurăm în muchii pe cel mai lung drum de la rădăcină la o frunză. Unele enunțuri numerotează nivelurile de la unu sau măsoară înălțimea în noduri. Citește convenția: în acea măsurare, același desen are patru niveluri.

Părinte, strămoș, frate și descendent

Tatăl lui șapte este șase. Strămoșii săi proprii sunt șase, doi și trei. Cuvântul „proprii” exclude nodul însuși; dacă un enunț folosește o altă convenție, urmează definiția dată acolo.

Nodurile șapte și opt sunt frați, fiindcă au același tată. Nodurile patru și șase se află la același nivel, dar nu sunt frați: tații lor sunt unu și doi. Nivelul comun nu este suficient pentru această relație.

Descendenții proprii ai lui doi sunt șase, șapte și opt. Subarborele cu rădăcina în doi îi include și pe aceștia, și pe doi, deci are patru noduri. Nu exclude rădăcina locală când se cere numărul nodurilor subarborelui.

Pentru a înțelege relațiile, nu doar denumirile, alege un nod și scrie separat tatăl, frații și strămoșii. Listele răspund unor întrebări diferite, chiar dacă pot conține uneori aceleași etichete în alte exemple.

Cum verifici rapid un vector propus?

Trebuie să existe exact o rădăcină, deci exact un zero în convenția noastră. Toate celelalte valori trebuie să fie etichete valide. Un nod nu poate fi propriul tată, deoarece ar apărea o buclă.

Aceste controale nu sunt suficiente singure. Vectorul (0,3,2) are exact un zero și tați cu etichete valide, dar nodurile doi și trei se indică reciproc. Urcarea lor nu ajunge la rădăcină; apare un ciclu separat.

O condiție completă, ușor de urmărit pe exemple mici, este ca urcarea de la fiecare nod să ajungă la rădăcina unică fără repetarea unei etichete. Dacă întâlnești din nou un nod înainte să ajungi la rădăcină, ai descoperit un ciclu.

Vectorul (0,0,1) are două zerouri și nu descrie un singur arbore cu rădăcină în convenția stabilită. Nu alege arbitrar unul dintre ele: enunțul trebuie să ofere un vector valid sau să ceară tocmai detectarea acestei erori.

Ce se schimbă când alegi altă rădăcină?

Arborele neorientat poate rămâne același, dar relațiile de părinte se schimbă. Dacă alegi nodul șase drept rădăcină în exemplul nostru, drumul dintre vechea și noua rădăcină își inversează relațiile de tată.

Noul vector este (3,6,2,1,1,0,6,6). Nodul șase are zero, tatăl lui doi devine șase, iar tatăl lui trei devine doi. Muchiile neorientate sunt aceleași șapte; am schimbat doar reperul din care le interpretăm.

Acest exemplu arată de ce vectorul nu este o reprezentare independentă de rădăcină. Dacă un exercițiu cere reconstruirea lui după schimbarea rădăcinii, refă relațiile de pe drumul relevant înainte să copiezi valorile vechi.

Exerciții și răspunsuri

1. Câți fii are nodul unu în vectorul inițial? Doi, identificați la pozițiile patru și cinci. Numărul se obține din frecvența valorii unu, nu din valoarea aflată la poziția unu.
2. Care este drumul de la opt la rădăcină? Opt, șase, doi, trei. Lungimea lui este trei muchii, iar strămoșul imediat este șase.
3. Care noduri sunt la nivelul doi? Patru, cinci și șase. Nodurile șapte și opt au nevoie de încă o urcare pentru a ajunge la rădăcină.
4. Câte noduri are subarborele lui unu? Trei: unu, patru și cinci. Cele două frunze singure reprezintă descendenții proprii, nu întregul subarbore.

Întrebări frecvente

Frunza trebuie să aibă valoarea zero în vector?

Nu. Frunza nu apare ca tată al altui nod. Valoarea de la poziția ei indică propriul tată și, dacă nu este singurul nod al arborelui, este nenulă.

Rădăcina poate fi frunză?

Da, în arborele format dintr-un singur nod, rădăcina nu are fii. Într-un arbore mai mare, rădăcina are cel puțin un fiu și nu este frunză în această convenție.

Cum verific o rezolvare la BAC?

Refă vectorul pornind din desen și compară fiecare poziție cu datele inițiale. Poți alege un exercițiu din arhiva BAC și solicita feedback asupra schemei printr-un profesor de informatică, după compararea informațiilor din anunțuri.