Arbori cu rădăcină: vector de tați și subarbori

Un arbore cu rădăcină stabilește un vârf de referință și o relație părinte-copil pentru toate celelalte vârfuri. Vectorul de tați memorează părintele fiecărui vârf, iar rădăcina primește un marcaj separat, de obicei zero.

Alegerea rădăcinii nu modifică muchiile arborelui neorientat, dar modifică adâncimile, părinții și subarborii. Aceeași structură poate avea interpretări diferite dacă punctul de pornire se schimbă.

Cum funcționează

Pentru fiecare vârf diferit de rădăcină, părintele este vecinul aflat pe drumul unic spre rădăcină. Copiii unui vârf sunt cei care îl indică drept părinte. Un strămoș se obține urcând de mai multe ori prin vectorul de tați; un descendent se află în direcția opusă. Subarborele unui vârf conține vârful însuși și toți descendenții săi.

Adâncimea rădăcinii este zero în convenția noastră. Pentru fiecare copil y al lui x avem depth[y]=depth[x]+1. Dimensiunea subarborelui se calculează după procesarea copiilor: subtree[x]=1+suma subtree[y]. Momentul calculului diferă: adâncimea copilului este cunoscută înainte de apel, iar contribuția subarborelui este cunoscută după revenire.

Un vector de numere între zero și n nu descrie automat un arbore valid. Pentru n>=1 trebuie să existe exact o rădăcină, fiecare alt vârf să aibă un părinte valid și urmărirea părinților să ajungă la rădăcină fără ciclu. De exemplu, parent[1]=2 și parent[2]=1 formează un ciclu, nu un arbore cu rădăcină. Programul presupune că intrarea este deja un arbore valid, cu 1 <= n <= 100.

Tablourile au capacitatea 101, iar indicii logici sunt 1..n. Pentru fiecare vârf căutăm copiii scanând vectorul de tați; este o alegere simplă, potrivită limitei mici. Pentru arbori mari am construi liste de copii o singură dată. Varianta vector păstrează aceeași scanare, aceleași limite și aceeași convenție pentru rădăcină. Adâncimea recursiei poate ajunge la n într-un arbore în formă de lanț.

Exemplu urmărit pas cu pas

Pentru vectorul de tați 0,1,1,2,2, rădăcina este 1. Copiii săi sunt 2 și 3, iar copiii lui 2 sunt 4 și 5. Adâncimile sunt 0,1,1,2,2.

Frunzele 3,4,5 au subarbori de dimensiune unu. Vârful 2 are dimensiunea 1+1+1=3, iar rădăcina 1+3+1=5. Numărul descendenților proprii ai unui vârf este dimensiunea subarborelui minus unu, deoarece subarborele îl include și pe el.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int n, parent[101], depth[101], subtree[101];
void visit(int x) {
    subtree[x] = 1;
    for (int y = 1; y <= n; ++y)
        if (parent[y] == x) {
            depth[y] = depth[x] + 1;
            visit(y);
            subtree[x] += subtree[y];
        }
}
int main() {
    std::cin >> n;
    int root = 0;
    for (int i = 1; i <= n; ++i) {
        std::cin >> parent[i];
        if (parent[i] == 0)
            root = i;
    }
    depth[root] = 0;
    visit(root);
    for (int i = 1; i <= n; ++i)
        std::cout << depth[i] << ' ' << subtree[i] << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int n;
std::vector<int> parent(101), depth(101), subtree(101);
void visit(int x) {
    subtree[x] = 1;
    for (int y = 1; y <= n; ++y)
        if (parent[y] == x) {
            depth[y] = depth[x] + 1;
            visit(y);
            subtree[x] += subtree[y];
        }
}
int main() {
    std::cin >> n;
    int root = 0;
    for (int i = 1; i <= n; ++i) {
        std::cin >> parent[i];
        if (parent[i] == 0)
            root = i;
    }
    depth[root] = 0;
    visit(root);
    for (int i = 1; i <= n; ++i)
        std::cout << depth[i] << ' ' << subtree[i] << '\n';
}

De ce funcționează și cât costă

Un arbore valid are drum unic de la rădăcină la fiecare vârf, deci propagarea adâncimii nu produce valori contradictorii. Subarborii copiilor sunt disjuncți și împreună cu părintele formează întregul subarbore, justificând suma dimensiunilor.

Implementarea scanează n posibili copii pentru fiecare dintre n vârfuri, deci costă O(n²) timp. Memoria pentru tablouri este O(n), iar stiva O(h), unde h este înălțimea. Cu liste de copii, parcurgerea poate costa O(n).

Greșeli frecvente

Nu confunda gradul din graful neorientat cu numărul copiilor: pentru un vârf nerădăcină intervine și părintele. Nu calcula dimensiunea părintelui înaintea copiilor. Nu presupune că rădăcina este mereu vârful 1.

Exersează

Într-un lanț cu rădăcina la un capăt și patru vârfuri, scrie adâncimile și dimensiunile subarborilor în ordinea de la rădăcină.

Rezolvare explicată: Adâncimile sunt 0,1,2,3, iar dimensiunile subarborilor 4,3,2,1. Acesta este și un exemplu în care stiva recursivă are adâncime liniară.

Continuă să înveți

Arbori, DFS și recursivitate.

Întrebări frecvente

Ce valoare are tatăl rădăcinii?

În convenția lecției, zero. Este un marcaj exterior mulțimii de vârfuri 1..n, nu un vârf suplimentar al arborelui.

Adâncimea și înălțimea sunt același lucru?

Nu. Adâncimea măsoară distanța de la rădăcină la vârf. Înălțimea unui subarbore măsoară lungimea maximă până la o frunză descendentă, conform convenției declarate.

Subarborele include vârful de pornire?

Da. O frunză are subarbore de dimensiune unu și zero descendenți proprii.

Orice vector de tați este valid?

Nu. Trebuie verificate rădăcina unică, domeniul părinților și lipsa ciclurilor, astfel încât toate vârfurile să ajungă la rădăcină.

De ce codul simplu este pătratic?

Pentru fiecare vârf scanează întregul vector ca să găsească fiii. Listele de copii construite în prealabil reduc parcurgerea la timp liniar.