Modul 11 — Arborele binar de căutare

Proprietatea de aur

Un arbore binar e ABC (arbore binar de căutare) dacă, pentru ORICE nod u: tot subarborele stâng < u < tot subarborele drept.

De ce e puternică?

La fiecare nod, o singură comparație ARUNCĂ un subarbore întreg — exact cum căutarea binară arunca jumătate de vector (X·M01). Drumul oricărei operații = cel mult ÎNĂLȚIMEA arborelui.

Față de vectorul sortat

Vector sortat: căutare O(log n), dar INSERAREA mută tot ce-i după — O(n). ABC: și căutarea, și inserarea merg pe același drum scurt. De-asta depozitele, bazele de date și dicționarele reale cresc pe arbori.

Depozitul viu — inserează și caută

Codurile de inventar intră unul câte unul. Auriu = comparația curentă, albastru = nod nou creat, verde = găsit.

cod =

construiește demo-ul, apoi inserează 60 și caută 40 👆

Observația care leagă M10 de M11: apasă „inordine" — valorile ies CRESCĂTOR, mereu. Stânga (mai micii), rădăcina, dreapta (mai marii) — sortare gratuită, direct din structură. La BAC: „parcurgerea în inordine a unui ABC este…?" → sortată!

Codul — și capcana „lianei"

Inserarea și căutarea sunt aceeași plimbare recursivă; diferă doar finalul.

1// C++: noduri în vectori (val, st, dr)

2int inser(int u, int x) {

3 if (u == 0) return nodNou(x);

4 if (x < val[u]) st[u] = inser(st[u], x);

5 else if (x > val[u]) dr[u] = inser(dr[u], x);

6 return u; // x == val[u]: cod unic, ignor

1bool caut(int u, int x) {

2 if (u == 0) return false; // cădere în gol

3 if (x == val[u]) return true;

4 if (x < val[u]) return caut(st[u], x);

5 return caut(dr[u], x);

6} // O(înălțime) — de obicei O(log n)

Capcana lianei: inserează 10, 20, 30, 40, 50 — fiecare merge mereu la dreapta → arborele devine un LANȚ de înălțime n, iar căutarea decade la O(n), ca cea liniară! Încearcă în simulator (golește întâi). Morala pentru evaluări: ABC e rapid DOAR cât e echilibrat — comparația cu căutarea liniară din programă depinde de formă.

Fișa de sinteză

ABC condensat — și Faza 3 (arborii) e completă!

Proprietatea: în FIECARE nod, subarborele stâng < nod < subarborele drept — nu doar fiii direcți!

Căutarea: compară → stânga sau dreapta → repetă; „căderea în gol" (u = 0) = valoarea nu există.

Inserarea: aceeași plimbare; nodul nou apare exact unde ar fi „căzut" căutarea.

Inordinea unui ABC = valorile în ordine CRESCĂTOARE — sortare din structură.

Costul: O(înălțime) — echilibrat ≈ log₂ n; degenerat (valori sortate la inserare) = liană, O(n).

Genealogia ideii: căutarea binară (X·M01) → structură dinamică; rudă cu dict (X·M08) la „acces rapid prin cheie".

Faza 3 încheiată! Grafuri ✔, arbori ✔. Ultimul model din programă: cel OBIECTUAL — clase și obiecte în Python, unde datele și acțiunile locuiesc împreună.