Arbore cu rădăcină

Alegerea unei rădăcini dă arborelui o direcție conceptuală de la părinte la fii. În arborele cu muchiile 1–2, 1–3, 3–4 și rădăcina 1, fiii lui 1 sunt 2 și 3, părintele lui 4 este 3, iar frunzele sunt 2 și 4. Structura de graf rămâne aceeași; relațiile de părinte depind de rădăcina aleasă.

Într-un arbore cu rădăcină, orice nod diferit de rădăcină are exact un părinte, adică vecinul de pe lanțul către rădăcină. Vecinii care nu sunt părinți se numesc fii. Nodurile cu același părinte sunt frați. Nodurile fără fii se numesc frunze. Nodurile aflate pe lanțul dintre un nod și rădăcină sunt ascendenții lui, iar nodurile de sub el sunt descendenții lui. Nivelul unui nod este numărul muchiilor până la rădăcină, iar înălțimea arborelui este nivelul maxim.

Arborele cu muchiile 1–2, 1–3, 3–4 și rădăcina 1 are nivelurile: rădăcina 1 are nivel 0, nodurile 2 și 3 au nivel 1, iar 4 are nivel 2. Nodurile 2 și 3 sunt frați, deoarece au același părinte, 1. Nodurile 1 și 3 sunt ascendenți ai lui 4. Pentru 1, nodurile 2, 3 și 4 sunt descendenți; pentru 3, doar 4 este descendent. Dacă schimbăm rădăcina în 3, vechile relații de părinte și nivel se modifică.

Exemplul 1 — nivelul unui nod din vectorul taților.

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

Pentru 4, trecem la 3, apoi la 1; se afișează 2. Aici valoarea 0 marchează lipsa părintelui pentru rădăcina 1, iar etichetele valide sunt 1–4.

Exemplul 2 — nivelurile tuturor nodurilor și frunzele. Arborele are 6 noduri, rădăcina 1 și vectorul taților 0 1 1 3 3 2 pentru nodurile 1–6. Programul calculează nivelul fiecărui nod și numără frunzele:

#include <iostream>
using namespace std;
int main() {
    int n = 6, t[7] = {0, 0, 1, 1, 3, 3, 2}, fii[7] = {};
    for (int v = 2; v <= n; ++v) ++fii[t[v]];
    int frunze = 0, inaltime = 0;
    for (int v = 1; v <= n; ++v) {
        int x = v, nivel = 0;
        while (t[x] != 0) { x = t[x]; ++nivel; }
        cout << nivel << " ";
        if (nivel > inaltime) inaltime = nivel;
        if (fii[v] == 0) ++frunze;
    }
    cout << "\n" << frunze << " " << inaltime;
}

Se afișează 0 1 1 2 2 2, apoi 3 2. Nodul 3 are fiii 4 și 5, nodul 2 are fiul 6, iar nodul 1 are fiii 2 și 3. Frunzele sunt nodurile 4, 5 și 6, adică nodurile care nu apar niciodată ca părinte, iar înălțimea este 2.

Exemplul 3 — numărul de descendenți. Pentru același arbore, cu vectorul taților 0 1 1 3 3 2, numărul de descendenți ai fiecărui nod se obține urcând de la fiecare nod spre rădăcină și mărind contorul fiecărui ascendent întâlnit:

int t[7] = {0, 0, 1, 1, 3, 3, 2}, desc[7] = {};
for (int v = 2; v <= 6; ++v)
    for (int x = t[v]; x != 0; x = t[x])
        ++desc[x];
for (int v = 1; v <= 6; ++v) cout << desc[v] << ' ';

Pentru nodul 6, lanțul spre rădăcină este 6, 2, 1, deci se măresc contoarele nodurilor 2 și 1. Se afișează 5 1 2 0 0 0: rădăcina are cinci descendenți, adică toate celelalte noduri, nodul 3 are doi (4 și 5), nodul 2 are unul (6), iar frunzele nu au niciunul. Numărul de descendenți plus 1 este numărul de noduri din subarborele nodului. Costul este proporțional cu suma nivelurilor nodurilor, cel mult $n\cdot h$ pentru înălțimea $h$.

Schimbarea rădăcinii. Pentru aceeași structură de graf (muchiile 1–2, 1–3, 3–4), alegerea rădăcinii 3 face ca 3 să aibă fiii 1 și 4, iar 1 să aibă fiul 2. Acum nivelul lui 2 este 2, nodul 1 are nivelul 1, iar nodul 3 nu are părinte. Muchiile rămân aceleași, dar părinții, fiii și nivelurile se schimbă.

La numărarea descendenților, nu include automat nodul însuși; descendenții unui nod sunt nodurile de sub el, fără nodul însuși. Fiecare nod diferit de rădăcină are exact un părinte. Într-un arbore cu $n$ noduri, sunt $n-1$ relații părinte–fiu. Din vectorul taților, frunzele sunt nodurile care nu apar printre valorile vectorului, iar numărul fiilor unui nod este de câte ori apare eticheta lui în vector. În arborele cu rădăcină, o frunză este un nod fără fii; o rădăcină cu un singur fiu nu este frunză, chiar dacă gradul ei în graf este 1. Înălțimea se citește din vectorul taților ca cel mai mare număr de pași până la valoarea 0, iar descendenții unui nod se numără adunând fiii lui și descendenții fiilor.

Exemplu în formatul examenului. Un arbore cu rădăcina 1 și 6 noduri este dat prin vectorul taților 0 1 1 3 3 2, unde al $i$-lea element este părintele nodului $i$. Câte frunze are arborele?

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

Răspunsul corect este b). Părinții care apar în vector sunt 1, 3 și 2; nodurile 4, 5 și 6 nu apar niciodată ca părinte, deci sunt frunze. Varianta a) este înălțimea arborelui, nu numărul frunzelor. Varianta c) ar număra și rădăcina ca frunză, deși ea are fiii 2 și 3. Varianta d) este numărul tuturor nodurilor.

Exemplu în formatul examenului — alt tip de cerință. Același arbore, dat prin vectorul taților 0 1 1 3 3 2, se reorientează cu rădăcina în nodul 3. Care este înălțimea arborelui cu această rădăcină?

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

Răspunsul corect este b). Cu rădăcina 3, fiii ei sunt 1, 4 și 5, iar muchiile 1–2 și 2–6 formează lanțul 3, 1, 2, 6, cu trei muchii. Varianta a) este înălțimea arborelui cu rădăcina 1. Varianta c) numără nodurile lanțului, nu muchiile lui. Varianta d) este numărul muchiilor arborelui, care nu depinde de rădăcină.

Greșeli frecvente

• Greșit: rădăcina are un părinte.
  Corect: nu are.
• Greșit: nivelul lui 4 în exemplu este 1.
  Corect: este 2 dacă rădăcina are nivel 0.
• Greșit: schimbarea rădăcinii schimbă muchiile grafului.
  Corect: schimbă doar interpretarea relațiilor.

Înainte și după