Arbore binar de căutare

Într-un arbore binar de căutare cu chei distincte, toate valorile din subarborele stâng al unui nod sunt mai mici, iar cele din drept sunt mai mari. Pentru rădăcina 5, fiul stâng 2 și drept 8, căutarea lui 8 compară mai întâi cu 5 și merge spre dreapta.

Într-un arbore binar de căutare cu chei distincte, pentru fiecare nod toate cheile din subarborele stâng sunt mai mici decât cheia nodului, iar toate cheile din subarborele drept sunt mai mari. Proprietatea se aplică întregului subarbore, nu doar fiilor direcți: un 9 din subarborele stâng al rădăcinii 5 ar fi invalid, chiar dacă este fiu drept al nodului 2. Parcurgerea în inordine produce cheile în ordine crescătoare. Căutarea costă timp proporțional cu înălțimea arborelui: poate fi logaritmică într-un arbore echilibrat, dar liniară dacă inserările creează un lanț.

Exemplul 1 — inserare, inordine și căutare. La inserare, se compară noua cheie cu cheia nodului curent și se coboară la stânga sau la dreapta până se ajunge la un loc liber. Se inserează, în ordine, 5, 2, 8 și 6:

#include <iostream>
using namespace std;
struct Nod { int v; Nod *s, *d; };
Nod* insereaza(Nod* p, int x) {
    if (!p) return new Nod{x, nullptr, nullptr};
    if (x < p->v) p->s = insereaza(p->s, x);
    else p->d = insereaza(p->d, x);
    return p;
}
void inordine(Nod* p) {
    if (!p) return;
    inordine(p->s);
    cout << p->v << " ";
    inordine(p->d);
}
int main() {
    Nod* r = nullptr;
    for (int x : {5, 2, 8, 6}) r = insereaza(r, x);
    inordine(r);
    int pasi = 0;
    for (Nod* p = r; p;) {
        ++pasi;
        if (p->v == 6) break;
        p = 6 < p->v ? p->s : p->d;
    }
    cout << "\n" << pasi;
}

Se afișează 2 5 6 8, apoi 3. Cheia 6 se compară cu 5 și se coboară la dreapta, se compară cu 8 și se coboară la stânga, deci devine fiu stâng al lui 8. Căutarea lui 6 vizitează 3 noduri.

Exemplul 2 — ștergerea unui nod. Ștergerea are trei cazuri. Dacă nodul este frunză, se elimină și legătura tatălui devine nulă. Dacă are un singur fiu, fiul ia locul nodului în legătura tatălui. Dacă are doi fii, cheia se înlocuiește cu succesorul în inordine (cel mai mic din subarborele drept), apoi se șterge nodul succesor, care are cel mult un fiu:

#include <iostream>
using namespace std;
struct Nod { int v; Nod *s, *d; };
Nod* insereaza(Nod* p, int x) {
    if (!p) return new Nod{x, nullptr, nullptr};
    if (x < p->v) p->s = insereaza(p->s, x);
    else p->d = insereaza(p->d, x);
    return p;
}
Nod* minim(Nod* p) {
    while (p->s) p = p->s;
    return p;
}
Nod* sterge(Nod* p, int x) {
    if (!p) return nullptr;
    if (x < p->v) p->s = sterge(p->s, x);
    else if (x > p->v) p->d = sterge(p->d, x);
    else if (!p->s || !p->d) {
        Nod* fiu = p->s ? p->s : p->d;
        delete p;
        return fiu;
    } else {
        Nod* succ = minim(p->d);
        p->v = succ->v;
        p->d = sterge(p->d, succ->v);
    }
    return p;
}
void preordine(Nod* p) {
    if (!p) return;
    cout << p->v << " ";
    preordine(p->s);
    preordine(p->d);
}
int main() {
    Nod* r = nullptr;
    for (int x : {5, 2, 8, 6}) r = insereaza(r, x);
    preordine(r);
    cout << "\n";
    r = sterge(r, 5);
    preordine(r);
}

Se afișează 5 2 8 6, apoi 6 2 8. Rădăcina 5 are doi fii, iar succesorul ei este 6, cel mai mic element din subarborele drept $\{8,6\}$. Cheia 6 ia locul lui 5, iar vechiul nod 6, o frunză, este eliminat. Inordinea rezultatului, 2 6 8, rămâne crescătoare. Succesorul nu este fiul drept 8, ci cel mai din stânga nod al subarborelui drept.

Arbori degenerați. Cheile 1, 2, 3, 4, 5 inserate în această ordine dau un lanț de înălțime 4, iar căutarea lui 5 vizitează toate cele 5 noduri. În ordinea 3, 1, 2, 5, 4, aceleași chei dau înălțimea 2.

Exemplu în formatul examenului. Într-un arbore binar de căutare inițial vid se inserează, în ordine, cheile 4, 2, 6, 1, 3, 5. Care este parcurgerea în preordine a arborelui obținut?

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

Răspunsul corect este a). Cheia 4 este rădăcina. Cheile 2 și 6 devin fiii ei. Cheia 1 este mai mică decât 4 și decât 2, deci devine fiu stâng al lui 2; 3 este mai mică decât 4 și mai mare decât 2, deci devine fiu drept al lui 2; 5 este mai mare decât 4 și mai mică decât 6, deci devine fiu stâng al lui 6. Preordinea este rădăcina, apoi subarborele stâng (2, 1, 3), apoi cel drept (6, 5). Varianta b) este inordinea, c) este ordinea inserării, iar d) este postordinea.

Greșeli frecvente

• Greșit: este suficient ca fiecare fiu stâng să fie mai mic decât părintele direct.
  Corect: toate valorile subarborelui stâng trebuie să respecte limita dată de fiecare ascendent.
• Greșit: orice arbore de căutare este echilibrat.
  Corect: poate degenera într-un lanț.
• Greșit: inordinea unui arbore de căutare cu chei distincte este aleatoare.
  Corect: este crescătoare.

Înainte și după