Reprezentarea arborelui

Un arbore cu rădăcină poate fi reprezentat prin vectorul de tați: pentru fiecare nod, memorăm părintele său. În arborele cu rădăcina 1 și muchiile 1–2, 1–3, 3–4, părinții nodurilor 2, 3, 4 sunt 1, 1, 3. Pentru rădăcină folosim un marcaj convenit, de exemplu 0.

Un arbore cu $n$ noduri se poate memora în mai multe moduri, iar alegerea depinde de operația folosită cel mai des. Vectorul taților păstrează, pentru fiecare nod, părintele lui; rădăcina primește un marcaj în afara etichetelor valide, de exemplu 0. Listele de fii păstrează, pentru fiecare nod, fiii lui. Matricea de adiacență și listele de adiacență tratează arborele ca pe un graf neorientat cu $n-1$ muchii. Vectorul taților și listele de fii ocupă $O(n)$ memorie, iar matricea ocupă $O(n^2)$.

Exemplul 1 — urcarea spre rădăcină cu vectorul taților.

#include <iostream>
using namespace std;
int main() {
    int parinte[] = {0, 0, 1, 1, 3};
    int v = 4;
    while (v != 1) {
        cout << v << " ";
        v = parinte[v];
    }
    cout << 1;
}

Se afișează 4 3 1, lanțul de la nodul 4 către rădăcină. Vectorul taților este potrivit pentru urcarea către rădăcină, deoarece fiecare pas citește o singură valoare. Pentru a afla repede fiii fiecărui nod, trebuie construite liste de fii; altfel trebuie căutat printre toți părinții, ceea ce cere $O(n)$ pași pentru fiecare nod.

Exemplul 2 — listele de fii construite din vectorul taților. Pentru arborele cu rădăcina 1 și muchiile 1–2, 1–3, 3–4, vectorul taților este tata[1]=0, tata[2]=1, tata[3]=1, tata[4]=3. Programul adaugă fiecare nod la lista părintelui său:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n = 4, t[5] = {0, 0, 1, 1, 3};
    vector<int> f[5];
    for (int v = 2; v <= n; ++v) f[t[v]].push_back(v);
    for (int i = 1; i <= n; ++i) {
        cout << i << ":";
        for (int x : f[i]) cout << " " << x;
        cout << "\n";
    }
}

Se afișează 1: 2 3, 2:, 3: 4 și 4:. Fiii lui 1 sunt 2 și 3, ai lui 3 este 4, iar 2 și 4 nu au fii, deci sunt frunze. Construirea listelor cere $O(n)$ pași. Vectorul taților economisește spațiu pentru urcarea spre rădăcină; listele de fii fac directă coborârea către descendenții imediați.

Exemplul 3 — matricea de adiacență. Pentru aceleași muchii $[1,2]$, $[1,3]$, $[3,4]$, matricea de adiacență cu indici 1..4 are liniile 0 1 1 0, 1 0 0 0, 1 0 0 1 și 0 0 1 0. Este simetrică fiindcă muchiile sunt neorientate. Un arbore cu $n$ noduri are exact $n-1$ muchii; aici sunt 4 noduri și 3 muchii, deci matricea conține $2\cdot 3=6$ valori egale cu 1. Suma unei linii este gradul nodului: nodul 1 are gradul 2, iar nodul 4 are gradul 1. Din matrice nu se vede care nod este rădăcina; rădăcina trebuie aleasă separat. În listele de adiacență ale aceluiași arbore, fiecare muchie apare în două liste, deci memoria este de $2(n-1)=6$ elemente, ca numărul valorilor 1 din matrice, dar fără cele zerouri.

Exemplul 4 — nivelurile și frunzele din vectorul taților. Fie arborele cu 6 noduri și vectorul taților t[1..6] = 0 1 1 2 2 4. Nivelul unui nod este numărul pașilor de urcare până la rădăcină:

#include <iostream>
using namespace std;
int main() {
    int t[7] = {0, 0, 1, 1, 2, 2, 4};
    int n = 6;
    for (int v = 1; v <= n; ++v) {
        int x = v, k = 0;
        while (x != 1) {
            x = t[x];
            ++k;
        }
        cout << k << " ";
    }
}

Programul afișează 0 1 1 2 2 3: rădăcina are nivelul 0, nodurile 2 și 3 sunt la nivelul 1, nodurile 4 și 5 la nivelul 2, iar nodul 6 la nivelul 3, deci înălțimea arborelui este 3. Frunzele sunt nodurile care nu apar în vector ca părinți. Valorile din vector sunt 1, 2 și 4, deci frunzele sunt 3, 5 și 6. Urcarea de la fiecare nod costă cel mult înălțimea arborelui, deci timpul total este cel mult $n\cdot h$.

Caz-limită — vector care nu descrie un arbore. Pentru t[2]=3 și t[3]=2, urcarea de la nodul 2 alternează între 2 și 3 și nu ajunge niciodată la 1, deci ciclul while (x != 1) nu se mai termină. Algoritmii de mai sus presupun că datele descriu un arbore cu rădăcina 1.

În vectorul taților, fiecare nod nerădăcină apare ca „fiu” al unei singure valori. Dacă două noduri indică reciproc unul spre altul și nu ajung la rădăcină, datele nu descriu un arbore cu rădăcina declarată. Marcajul rădăcinii trebuie ales în afara etichetelor valide. Numărul fiilor unui nod este de câte ori apare eticheta lui în vector, iar frunzele sunt nodurile care nu apar deloc. Nivelul unui nod se află numărând pașii de urcare până la valoarea 0. Dintr-un vector al taților nu se poate deduce ordinea fiilor unui nod, deci nu se poate distinge între fiu stâng și fiu drept.

Exemplu în formatul examenului. Se dă vectorul taților 0 1 1 2 2 4 pentru nodurile 1–6, unde al $i$-lea element este părintele nodului $i$. Care este lanțul de la nodul 6 la rădăcină?

• a) 6 4 2 1
• b) 6 5 2 1
• c) 1 2 4 6
• d) 6 4 1

Răspunsul corect este a). Părintele lui 6 este al șaselea element, 4. Părintele lui 4 este al patrulea element, 2. Părintele lui 2 este al doilea element, 1, iar 1 are marcajul 0, deci este rădăcina. Lanțul este 6 4 2 1, cu trei muchii, deci nodul 6 are nivelul 3. Varianta b) presupune că părintele lui 6 este nodul 5, adică nodul vecin ca poziție, nu valoarea din vector. Varianta c) este lanțul parcurs de la rădăcină spre nod, nu invers, iar d) sare peste nodul 2, deși 4 nu este fiul lui 1.

Exemplu în formatul examenului — numărul fiilor. Se dă vectorul taților 0 1 1 3 3 3 5 pentru nodurile 1–7. Câți fii are nodul 3?

• a) 2
• b) 3
• c) 4
• d) 5

Răspunsul corect este b). Eticheta 3 apare în vector pe pozițiile 4, 5 și 6, deci nodurile 4, 5 și 6 au părintele 3. Varianta a) numără doar nodurile 4 și 5. Varianta c) numără și nodul 7, care este fiul lui 5, nu al lui 3, adică un descendent, nu un fiu. Varianta d) este eticheta părintelui nodului 7, nu un număr de fii.

Greșeli frecvente

• Greșit: parinte[4]=3 înseamnă că 4 este părintele lui 3.
  Corect: 3 este părintele lui 4.
• Greșit: un vector al taților afișează direct toți fiii unui nod.
  Corect: trebuie căutați sau indexați separat.
• Greșit: rădăcina poate avea un părinte obișnuit în același arbore.
  Corect: primește un marcaj special.

Înainte și după