Arborii binari de căutare

Definiția

Fiecare nod al arborelui conține o cheie, adică o valoare din informația nodului care identifică nodul în mod unic.

Un arbore binar de căutare este un arbore binar care are următoarea proprietate: pentru orice nod, cheile din subarborele stâng sunt mai mici decât cheia nodului, iar cheile din subarborele drept sunt mai mari decât ea. Din definiție rezultă că toate cheile unui arbore binar de căutare sunt distincte.

Arborele folosit în exemple

struct nod {
    int cheie;
    nod *st, *dr;
};

Inserarea unei chei

void inserare(nod *&r, int k) {
    if (r == NULL) {
        r = new nod;
        r->cheie = k;
        r->st = NULL;
        r->dr = NULL;
    }
    else if (k < r->cheie)
        inserare(r->st, k);
    else if (k > r->cheie)
        inserare(r->dr, k);
}

Căutarea unei chei

nod *cautare(nod *r, int k) {
    while (r != NULL && r->cheie != k)
        if (k < r->cheie)
            r = r->st;
        else
            r = r->dr;
    return r;
}

Exemplu, pe arborele cu nouă noduri, obținut după inserarea cheii 70:

• cheia 35: 35 < 50, se trece la 30; 35 > 30, se trece la 40; 35 < 40, se trece la 35. Cheia este găsită după patru comparații, iar funcția întoarce adresa nodului;
• cheia 68: 68 > 50, se trece la 80; 68 < 80, se trece la 65; 68 > 65, se trece la 70; 68 < 70, iar fiul stâng al lui 70 lipsește. Funcția întoarce NULL, deci cheia 68 nu există în arbore.

Ștergerea unei chei

Descrierea. Se caută nodul care conține cheia. Modul de ștergere depinde de numărul fiilor acestui nod:

• nodul nu are fii: legătura părintelui către el primește valoarea NULL, iar memoria nodului se eliberează;
• nodul are un singur fiu: legătura părintelui către el primește adresa acestui fiu, iar memoria nodului se eliberează;
• nodul are doi fii: se determină cea mai mare cheie din subarborele stâng, care se află în nodul la care se ajunge trecând o dată la fiul stâng și apoi numai la fiii drepți. Cheia acestui nod se copiază în nodul de șters, apoi nodul găsit se șterge din subarborele stâng. Nodul găsit nu are fiu drept, deci ștergerea lui se face ca în unul dintre primele două cazuri.

În al treilea caz, cheia copiată este mai mare decât toate celelalte chei din subarborele stâng și mai mică decât toate cheile din subarborele drept, deci arborele rămâne arbore binar de căutare.

void stergere(nod *&r, int k) {
    nod *q;
    if (r == NULL)
        return;
    if (k < r->cheie)
        stergere(r->st, k);
    else if (k > r->cheie)
        stergere(r->dr, k);
    else if (r->st == NULL) {
        q = r;
        r = r->dr;
        delete q;
    }
    else if (r->dr == NULL) {
        q = r;
        r = r->st;
        delete q;
    }
    else {
        q = r->st;
        while (q->dr != NULL)
            q = q->dr;
        r->cheie = q->cheie;
        stergere(r->st, q->cheie);
    }
}

În subprogram, cazul nodului fără fii este tratat pe ramura r->st == NULL: fiul drept este și el NULL, deci legătura părintelui primește valoarea NULL.

Parcurgerea arborelui

void srd(nod *r) {
    if (r != NULL) {
        srd(r->st);
        cout << r->cheie << " ";
        srd(r->dr);
    }
}

Exemplu, pe arborele cu nouă noduri, obținut după inserarea cheii 70:

Problema rezolvată

Enunț. O bibliotecă identifică fiecare carte printr-un cod, număr natural nenul. Se citesc de la tastatură un număr natural n (n ≤ 1000), apoi n numere naturale distincte, reprezentând codurile cărților aflate în bibliotecă. Se citesc apoi un număr natural m (m ≤ 1000) și m coduri de cărți cerute de cititori. Pentru fiecare cod cerut, dacă în bibliotecă se află o carte cu acest cod, ea se împrumută, adică este eliminată din evidență, și se afișează mesajul DA; altfel se afișează mesajul NU. Mesajele se afișează pe câte un rând. La final se afișează, pe un rând, în ordine crescătoare, codurile cărților rămase în bibliotecă, separate prin câte un spațiu.

Exemplu: pentru n = 7, codurile 50 30 70 20 40 60 80, m = 3 și codurile cerute 30 65 50, se afișează:

DA
NU
DA
20 40 60 70 80

Descrierea soluției. Codurile cărților se memorează ca chei într-un arbore binar de căutare alocat dinamic. Arborele se construiește pornind de la arborele vid, prin inserarea, pe rând, a celor n coduri citite.

Pentru fiecare cod cerut, se caută în arbore nodul care îl conține. Dacă funcția de căutare întoarce o adresă diferită de NULL, cartea există: nodul se șterge din arbore și se afișează DA. Dacă funcția întoarce NULL, se afișează NU.

După prelucrarea tuturor cererilor, arborele se parcurge în inordine, iar cheile se afișează în ordine crescătoare, fără o sortare separată.

Implementarea soluției.

#include <iostream>
using namespace std;

struct nod {
    int cheie;
    nod *st, *dr;
};

void inserare(nod *&r, int k) {
    if (r == NULL) {
        r = new nod;
        r->cheie = k;
        r->st = NULL;
        r->dr = NULL;
    }
    else if (k < r->cheie)
        inserare(r->st, k);
    else if (k > r->cheie)
        inserare(r->dr, k);
}

nod *cautare(nod *r, int k) {
    while (r != NULL && r->cheie != k)
        if (k < r->cheie)
            r = r->st;
        else
            r = r->dr;
    return r;
}

void stergere(nod *&r, int k) {
    nod *q;
    if (r == NULL)
        return;
    if (k < r->cheie)
        stergere(r->st, k);
    else if (k > r->cheie)
        stergere(r->dr, k);
    else if (r->st == NULL) {
        q = r;
        r = r->dr;
        delete q;
    }
    else if (r->dr == NULL) {
        q = r;
        r = r->st;
        delete q;
    }
    else {
        q = r->st;
        while (q->dr != NULL)
            q = q->dr;
        r->cheie = q->cheie;
        stergere(r->st, q->cheie);
    }
}

void srd(nod *r) {
    if (r != NULL) {
        srd(r->st);
        cout << r->cheie << " ";
        srd(r->dr);
    }
}

int main() {
    nod *rad = NULL;
    int n, m, i, cod;

    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> cod;
        inserare(rad, cod);
    }

    cin >> m;
    for (i = 1; i <= m; i++) {
        cin >> cod;
        if (cautare(rad, cod) != NULL) {
            stergere(rad, cod);
            cout << "DA\n";
        }
        else
            cout << "NU\n";
    }

    srd(rad);
    return 0;
}

Verificarea pe exemplul din enunț. După inserarea codurilor, rădăcina are cheia 50, cu fiii 30 și 70; 30 are fiii 20 și 40, iar 70 are fiii 60 și 80.

Parcurgerea SRD a arborelui rămas afișează 20 40 60 70 80.