Invatare Atomica

Arbori: definitie, proprietati, arbore binar

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei stapani structura de date arbore — cel mai important model ierarhic din informatica — si vei invata sa implementezi si sa parcurgi arbori generali si arbori binari de cautare.

Dupa aceasta lectie vei putea:

  • Sa definesti arborele si sa enunti proprietatile sale esentiale (n noduri, n-1 muchii, conexitate, aciclic)
  • Sa identifici terminologia: radacina, parinte, fiu, frunza, nivel, inaltime, subarbore
  • Sa parcurgi un arbore general in latime (BFS) si in adancime (DFS)
  • Sa definesti arborele binar si cele trei parcurgeri: inordine, preordine, postordine
  • Sa implementezi un Arbore Binar de Cautare (BST) cu inserare si cautare
  • Sa rezolvi exercitii de tip Bacalaureat cu arbori si proprietatile lor

Incearca singur!

Provocare:

Gandeste-te la o organigrama (ex: directorul unei scoli, cu 3 directori adjuncti, fiecare avand 2-4 profesori in subordine). Desenati relatia ierarhica.

Intrebari de reflectie: Cate relatii (muchii) exista daca sunt 10 persoane? Poate un angajat sa aiba doi sefi directi?

💡 Ai nevoie de un indiciu?

O organigrama cu n persoane are exact n-1 relatii (fiecare persoana, exceptand directorul, are exact un sef direct). Aceasta este proprietatea fundamentala a arborilor!

Un angajat nu poate avea doi sefi directi — asta ar crea un ciclu sau ar face structura sa nu mai fie un arbore.

1

1. Definitia arborelui si proprietatile sale

Un arbore este un graf neorientat conex si aciclic. Echivalent, un arbore cu n noduri are exact n-1 muchii.
Proprietatile esentiale ale unui arbore:
  • Conexitate: intre oricare doua noduri exista exact un lant
  • Aciclic: nu contine cicluri (nu exista lant de la un nod la el insusi)
  • n noduri => n-1 muchii (proprietate numerica definitorie)
  • Eliminarea oricarei muchii deconecteaza arborele in doua componente
  • Adaugarea oricarei muchii creeaza exact un ciclu
Verificare in Python — conditia n-1 muchii:
# Un arbore cu n noduri are exact n-1 muchii
n_noduri = 5
muchii = [(1,2), (1,3), (2,4), (2,5)]

print(f"Graf cu {n_noduri} noduri si {len(muchii)} muchii:")
print(f"  Este arbore? {len(muchii) == n_noduri - 1}")
print(f"  Proprietate: n={n_noduri} noduri => n-1={n_noduri-1} muchii (exact {len(muchii)})")
Output real (rulat cu python):
Graf cu 5 noduri si 4 muchii:
  Este arbore? True
  Proprietate: n=5 noduri => n-1=4 muchii (exact 4)
Reprezentare vizuala — arbore cu 6 noduri:
        1          <-- radacina (nivel 0)
       / \
      2   3        <-- nivel 1
     / \   \
    4   5   6      <-- nivel 2 (frunze)

Noduri: 6   Muchii: 5 = 6-1  ✓
2

2. Terminologia arborelui cu radacina

Un arbore cu radacina (rooted tree) este un arbore in care un nod special — radacina — defineste ierarhia. Toate muchiile devin orientate implicit: dinspre parinte spre fii.
Termeni esentiali (cu exemplu pe arborele de mai jos):
        1          Radacina = 1
       / \
      2   3        Parinte(2)=1, Parinte(3)=1, Parinte(6)=3
     / \   \
    4   5   6      Frunze = {4, 5, 6}  (grad 1, fara fii)

Nivel(1)=0, Nivel(2)=Nivel(3)=1, Nivel(4)=Nivel(5)=Nivel(6)=2
Inaltime arbore = max nivel frunza = 2
Subarbore(2) = nodul 2 impreuna cu 4 si 5
Tabel de terminologie:
Termen        | Definitie
--------------+------------------------------------------
Radacina      | Nodul fara parinte (nivelul 0)
Parinte       | Nodul direct superior in ierarhie
Fiu (copil)   | Nod direct inferior unui parinte
Frunza        | Nod fara fii (nod terminal)
Nod intern    | Nod cu cel putin un fiu (non-frunza)
Nivel         | Distanta (nr. muchii) de la radacina
Inaltime (h)  | Nivelul maxim al unei frunze
Subarbore     | Un nod + toti descendentii sai
Adancime nod  | Nivelul nodului (sinonim cu nivel)
Calcul nivel si parinte (Python):
# BFS pe arbore pentru nivel si parinte
from collections import deque

adj = {1:[2,3], 2:[1,4,5], 3:[1,6],
       4:[2], 5:[2], 6:[3]}
nivel = {1: 0}
parinte = {1: "radacina"}
coada = deque([1])
vizitat = {1}

while coada:
    nod = coada.popleft()
    for vecin in adj[nod]:
        if vecin not in vizitat:
            vizitat.add(vecin)
            nivel[vecin] = nivel[nod] + 1
            parinte[vecin] = nod
            coada.append(vecin)

for nod in range(1, 7):
    print(f"  Nod {nod}: nivel={nivel[nod]}, parinte={parinte[nod]}")
Output real (rulat cu python):
  Nod 1: nivel=0, parinte=radacina
  Nod 2: nivel=1, parinte=1
  Nod 3: nivel=1, parinte=1
  Nod 4: nivel=2, parinte=2
  Nod 5: nivel=2, parinte=2
  Nod 6: nivel=2, parinte=3
3

3. Parcurgerea arborelui — DFS si BFS

Algoritmii de parcurgere a grafurilor (DFS si BFS) se aplica direct pe arbori. Pe un arbore, DFS genereaza o parcurgere in adancime (ramura completa inainte de alta ramura), iar BFS genereaza o parcurgere nivel cu nivel.
DFS pe arbore (Python) — O(n+m) = O(n):
# DFS recursiv pe arbore
def dfs_arbore(adj, nod, vizitat, ordine):
    vizitat[nod] = True
    ordine.append(nod)
    for vecin in sorted(adj.get(nod, [])):
        if not vizitat[vecin]:
            dfs_arbore(adj, vecin, vizitat, ordine)

adj = {1:[2,3], 2:[1,4,5], 3:[1,6],
       4:[2], 5:[2], 6:[3]}
vizitat = [False] * 7
ordine = []
dfs_arbore(adj, 1, vizitat, ordine)
print(f"DFS pe arbore (radacina=1):")
print(f"Ordine vizitare: {ordine}")
print(f"Toate 6 noduri vizitate: {all(vizitat[1:])}")
Output real (rulat cu python):
DFS pe arbore (radacina=1):
Ordine vizitare: [1, 2, 4, 5, 3, 6]
Toate 6 noduri vizitate: True
Comparatie DFS vs BFS pe acelasi arbore:
Arbore:   1 - 2 - 4
              |   \- 5
              \- 3 - 6

DFS (adancime):  1, 2, 4, 5, 3, 6   (ramura stanga completa, apoi dreapta)
BFS (latime):    1, 2, 3, 4, 5, 6   (nivel 0, nivel 1, nivel 2)

Pe un arbore, BFS = parcurgere pe niveluri (level-order traversal)
Pe un arbore, DFS = parcurgere preordine (R-S-D) daca vecinii sunt sortati
4

4. Arborele binar si parcurgerile sale

Un arbore binar este un arbore cu radacina in care fiecare nod are cel mult doi fii: fiul stang si fiul drept. Un Arbore Binar de Cautare (BST) adauga proprietatea: valorile din subarborele stang < radacina < valorile din subarborele drept.
Cele trei parcurgeri ale arborelui binar:
Cele trei parcurgeri:
  Inordine   (S-R-D): Stang -> Radacina -> Drept
  Preordine  (R-S-D): Radacina -> Stang -> Drept
  Postordine (S-D-R): Stang -> Drept -> Radacina

BST cu valorile 5, 3, 7, 1, 4, 6, 8:

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

Inordine:   1, 3, 4, 5, 6, 7, 8  (sortat crescator!)
Preordine:  5, 3, 1, 4, 7, 6, 8  (radacina prima)
Postordine: 1, 4, 3, 6, 8, 7, 5  (radacina ultima)
Implementare BST in Python — inserare si parcurgeri:
class Nod:
    def __init__(self, val):
        self.val = val
        self.stang = None
        self.drept = None

def insereaza(radacina, val):
    if radacina is None:
        return Nod(val)
    if val < radacina.val:
        radacina.stang = insereaza(radacina.stang, val)
    else:
        radacina.drept = insereaza(radacina.drept, val)
    return radacina

def inordine(nod, rezultat):
    if nod is None: return
    inordine(nod.stang, rezultat)
    rezultat.append(nod.val)
    inordine(nod.drept, rezultat)

def preordine(nod, rezultat):
    if nod is None: return
    rezultat.append(nod.val)
    preordine(nod.stang, rezultat)
    preordine(nod.drept, rezultat)

def postordine(nod, rezultat):
    if nod is None: return
    postordine(nod.stang, rezultat)
    postordine(nod.drept, rezultat)
    rezultat.append(nod.val)

valori = [5, 3, 7, 1, 4, 6, 8]
radacina = None
for v in valori:
    radacina = insereaza(radacina, v)

rez_in, rez_pre, rez_post = [], [], []
inordine(radacina, rez_in)
preordine(radacina, rez_pre)
postordine(radacina, rez_post)

print(f"Arbore Binar de Cautare (BST) cu valorile: {valori}")
print(f"Parcurgere inordine  (S-R-D): {rez_in}")
print(f"Parcurgere preordine (R-S-D): {rez_pre}")
print(f"Parcurgere postordine(S-D-R): {rez_post}")
print(f"Observatie: inordine produce valorile sortate crescator!")
Output real (rulat cu python):
Arbore Binar de Cautare (BST) cu valorile: [5, 3, 7, 1, 4, 6, 8]
Parcurgere inordine  (S-R-D): [1, 3, 4, 5, 6, 7, 8]
Parcurgere preordine (R-S-D): [5, 3, 1, 4, 7, 6, 8]
Parcurgere postordine(S-D-R): [1, 4, 3, 6, 8, 7, 5]
Observatie: inordine produce valorile sortate crescator!
5

5. Inaltimea arborelui binar si calcul recursiv

Inaltimea unui arbore binar este lungimea celui mai lung lant de la radacina la o frunza. Un arbore cu un singur nod are inaltimea 0. Arborele vid are inaltimea -1 (conventie frecventa in informatica).
Calcul recursiv al inaltimii, numarului de noduri si frunze (Python):
def inaltime(nod):
    if nod is None:
        return -1   # conventie: arborele vid
    return 1 + max(inaltime(nod.stang), inaltime(nod.drept))

def nr_noduri(nod):
    if nod is None: return 0
    return 1 + nr_noduri(nod.stang) + nr_noduri(nod.drept)

def nr_frunze(nod):
    if nod is None: return 0
    if nod.stang is None and nod.drept is None: return 1
    return nr_frunze(nod.stang) + nr_frunze(nod.drept)

# BST cu valorile 5, 3, 7, 1, 4, 6, 8 (construit anterior)
h = inaltime(radacina)
n = nr_noduri(radacina)
f = nr_frunze(radacina)
print(f"BST cu valorile {valori}:")
print(f"  Inaltime h = {h}")
print(f"  Numar noduri n = {n}")
print(f"  Numar frunze = {f}")
print(f"  Numar noduri interne = {n - f}")
Output real (rulat cu python):
BST cu valorile [5, 3, 7, 1, 4, 6, 8]:
  Inaltime h = 2
  Numar noduri n = 7
  Numar frunze = 4
  Numar noduri interne = 3
Relatii importante pentru arbori binari (de memorat):
Arbore binar cu inaltime h:
  - Are MINIM h+1 noduri (lant - arbore degenerat)
  - Are MAXIM 2^(h+1) - 1 noduri (arbore complet)

Arbore binar COMPLET cu n noduri:
  - Inaltime h = floor(log2(n))
  - Ex: n=7 => h=2, n=15 => h=3, n=31 => h=4

Numar frunze = numar noduri interne + 1
  (valabila pentru arbori binari COMPETI cu toti fiii)
6

6. Arbore binar in C++ EXCLUSIV INTENSIV

⚡ Sectiune exclusiv pentru profil intensiv informatica

La profilul intensiv vei implementa BST cu alocare dinamica (new/delete) si pointeri. Parcurgerile sunt identice ca logica cu Python, dar sintaxa C++ impune declararea explicita a tipurilor si gestionarea memoriei.

#include <iostream>
using namespace std;

struct Nod {
    int val;
    Nod* stang;
    Nod* drept;
    Nod(int v): val(v), stang(nullptr), drept(nullptr) {}
};

Nod* insereaza(Nod* radacina, int val) {
    if (!radacina) return new Nod(val);
    if (val < radacina->val)
        radacina->stang = insereaza(radacina->stang, val);
    else
        radacina->drept = insereaza(radacina->drept, val);
    return radacina;
}

void inordine(Nod* nod) {
    if (!nod) return;
    inordine(nod->stang);
    cout << nod->val << " ";
    inordine(nod->drept);
}

int inaltime(Nod* nod) {
    if (!nod) return -1;
    return 1 + max(inaltime(nod->stang), inaltime(nod->drept));
}

int main() {
    int valori[] = {5, 3, 7, 1, 4, 6, 8};
    Nod* radacina = nullptr;
    for (int v : valori) radacina = insereaza(radacina, v);
    cout << "BST cu valorile: 5 3 7 1 4 6 8" << endl;
    cout << "Parcurgere inordine: ";
    inordine(radacina);
    cout << endl;
    cout << "Inaltime: " << inaltime(radacina) << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, apoi rulat):
BST cu valorile: 5 3 7 1 4 6 8
Parcurgere inordine: 1 3 4 5 6 7 8
Inaltime: 2
Diferente C++ fata de Python:
Python                     C++ (intensiv)
--------------------------+---------------------------
class Nod:                 struct Nod {
  self.stang = None          Nod* stang = nullptr;
                           }
  (garbage collector)        delete nod; // manual
  radacina.stang             radacina->stang
  return Nod(val)            return new Nod(val)

Exercitii practice

Exercitiul 1 (Nivel minim) — Proprietati arbore

Un arbore are 12 noduri. Raspunde la urmatoarele:

  1. Cate muchii are arborele?
  2. Poate un nod sa aiba 3 parinti? Justifica.
  3. Daca adaugam o muchie noua intre doua noduri deja existente, mai este arborele un arbore? De ce?
Vezi rezolvarea

Arborele are 12 noduri. Folosind proprietatea n noduri => n-1 muchii din lectie:

  1. Muchii = 12 - 1 = 11 muchii.
  2. Nu. Intr-un arbore, intre oricare doua noduri exista exact un lant, deci fiecare nod (in afara de radacina) are un singur parinte. Trei parinti ar insemna trei drumuri diferite spre acel nod, ceea ce ar crea un ciclu si ar contrazice proprietatea ca arborele e aciclic.
  3. Nu mai este arbore. Conform lectiei, adaugarea oricarei muchii creeaza exact un ciclu. Arborele are deja 11 muchii pentru 12 noduri (numarul corect); o muchie in plus intre doua noduri deja conectate ar da 12 muchii pentru 12 noduri, deci graful nu mai e aciclic si nu mai respecta definitia de arbore.

Exercitiul 2 (Nivel standard) — Parcurgeri BST

Construieste un Arbore Binar de Cautare inserand valorile in ordinea: 10, 5, 15, 3, 7, 12, 20.

  1. Deseneaza arborele rezultat.
  2. Scrie parcurgerea inordine — ce observi?
  3. Scrie parcurgerea preordine.
  4. Care este inaltimea arborelui?
  5. Cate frunze are?
Vezi rezolvarea

Inserare in ordine 10, 5, 15, 3, 7, 12, 20 intr-un BST (mai mic merge la stanga, mai mare la dreapta):

  1. Arbore rezultat: radacina 10; sub ea stanga 5 (cu fii 3 si 7) si dreapta 15 (cu fii 12 si 20).
  2. Parcurgere inordine (S-R-D): 3, 5, 7, 10, 12, 15, 20. Observatie: valorile ies exact in ordine crescatoare — proprietatea de baza a unui BST.
  3. Parcurgere preordine (R-S-D): 10, 5, 3, 7, 15, 12, 20.
  4. Inaltimea: radacina e la nivelul 0, frunzele (3, 7, 12, 20) sunt la nivelul 2, deci inaltime = 2.
  5. Frunze: 3, 7, 12, 20 — 4 frunze.

Exercitiul 3 (Nivel performanta) — Implementare completa BST

Implementeaza in Python o functie cauta(radacina, val) care cauta o valoare in BST si returneaza True/False. Complexitatea trebuie sa fie O(h) unde h este inaltimea arborelui.

Bonus (intensiv): Implementeaza aceeasi functie in C++ cu signatura: bool cauta(Nod* radacina, int val).

Testeaza pe BST-ul cu valorile 5, 3, 7, 1, 4, 6, 8 si cauta valorile 4 (prezent) si 9 (absent).

Vezi rezolvarea

Schita de rezolvare (nu codul complet — construieste-l singur):

  1. cauta(radacina, val) e recursiva: caz de baza radacina este None -> False (val nu exista); caz de baza radacina.val == val -> True.
  2. Pas recursiv: daca val < radacina.val cauta doar in subarborele stang, altfel cauta doar in subarborele drept. Aici e cheia lui O(h): elimini jumatate din arbore la fiecare pas, nu parcurgi ambii subarbori (asta ar da O(n), gresit).
  3. Capcana frecventa: lipsa cazului de baza pentru radacina None duce la eroare.
  4. Pe BST-ul din 5, 3, 7, 1, 4, 6, 8: cauta(radacina, 4) urmeaza 5->3->4 = True; cauta(radacina, 9) urmeaza 5->7->8->None = False.
  5. Bonus C++: aceeasi logica, dar cu Nod* si verificare nod == nullptr. Se evalueaza: cazuri de baza corecte, o singura ramura urmata (O(h)), tip returnat bool, sintaxa C++ corecta (struct, pointeri) la bonus.

Ce ai invatat astazi

  • Definitia arborelui: graf neorientat conex si aciclic cu n noduri si n-1 muchii
  • Terminologia: radacina, parinte, fiu, frunza, nivel, inaltime, subarbore
  • Parcurgerea DFS si BFS pe arbori generali — O(n)
  • Arborele binar: cel mult 2 fii per nod (stang si drept)
  • Cele trei parcurgeri: inordine (S-R-D), preordine (R-S-D), postordine (S-D-R)
  • BST: inordine produce valorile sortate crescator
  • Inaltimea recursiva: h(arbore_vid)=-1, h(nod)=1+max(h(stang),h(drept))
  • [Intensiv] Implementare C++ cu struct si pointeri (Nod*)

Vrei mai mult?

Provocare: Ia BST-ul din Atomul 4 (valorile 5, 3, 7, 1, 4, 6, 8) si insereaza valoarea 2 folosind functia insereaza. Deseneaza noul arbore, scrie parcurgerea inordine (verifica ca ramane sortata crescator) si calculeaza noua inaltime cu functia inaltime. S-a schimbat inaltimea fata de arborele original (h=2)? La ce nivel ajunge nodul 2?

De ce? Parcurgerea inordine a unui BST produce mereu valorile sortate, indiferent de ordinea in care au fost inserate nodurile. Ce anume in regula de inserare (mai mic la stanga, mai mare la dreapta) garanteaza ca S-R-D iese mereu crescator, si nu doar de multe ori?

Dincolo de lectie: Structura de arbore cu radacina e peste tot: sistemul de foldere de pe disc (un folder = un nod, subfolderele = fii), DOM-ul unei pagini HTML parcurs de browser, sau structura de organigrama a unei companii — toate sunt acelasi model matematic din aceasta lectie.

Urmatoarea lectie

Continua cu Lectia 6 — Aplicatii grafuri: probleme tip Bacalaureat cu grafuri si arbori.

Continua →