Arbori Binari de Căutare (BST) în C++

Ce este un BST?

Un arbore binar în care pentru fiecare nod:

• •Toate valorile din subarborele stâng sunt mai mici
• •Toate valorile din subarborele drept sunt mai mari

Implementare

Copiază
1#include <iostream>
2using namespace std;
3
4struct Nod {
5    int valoare;
6    Nod* stang;
7    Nod* drept;
8    
9    Nod(int val) : valoare(val), stang(nullptr), drept(nullptr) {}
10};
11
12class BST {
13private:
14    Nod* radacina;
15    
16    Nod* inserare(Nod* nod, int val) {
17        if (!nod) return new Nod(val);
18        
19        if (val < nod->valoare)
20            nod->stang = inserare(nod->stang, val);
21        else if (val > nod->valoare)
22            nod->drept = inserare(nod->drept, val);
23        
24        return nod;
25    }
26    
27    Nod* minim(Nod* nod) {
28        while (nod->stang)
29            nod = nod->stang;
30        return nod;
31    }
32    
33    Nod* sterge(Nod* nod, int val) {
34        if (!nod) return nullptr;
35        
36        if (val < nod->valoare)
37            nod->stang = sterge(nod->stang, val);
38        else if (val > nod->valoare)
39            nod->drept = sterge(nod->drept, val);
40        else {
41            // Nodul de șters găsit
42            if (!nod->stang) {
43                Nod* temp = nod->drept;
44                delete nod;
45                return temp;
46            }
47            if (!nod->drept) {
48                Nod* temp = nod->stang;
49                delete nod;
50                return temp;
51            }
52            
53            // Nod cu 2 copii: înlocuim cu succesorul inordine
54            Nod* temp = minim(nod->drept);
55            nod->valoare = temp->valoare;
56            nod->drept = sterge(nod->drept, temp->valoare);
57        }
58        return nod;
59    }
60    
61    void inordine(Nod* nod) {
62        if (!nod) return;
63        inordine(nod->stang);
64        cout << nod->valoare << " ";
65        inordine(nod->drept);
66    }
67    
68public:
69    BST() : radacina(nullptr) {}
70    
71    void inserare(int val) {
72        radacina = inserare(radacina, val);
73    }
74    
75    bool cauta(int val) {
76        Nod* curent = radacina;
77        while (curent) {
78            if (val == curent->valoare) return true;
79            if (val < curent->valoare)
80                curent = curent->stang;
81            else
82                curent = curent->drept;
83        }
84        return false;
85    }
86    
87    void sterge(int val) {
88        radacina = sterge(radacina, val);
89    }
90    
91    void afisareInordine() {
92        inordine(radacina);
93        cout << endl;
94    }
95};
96
97int main() {
98    BST arbore;
99    arbore.inserare(50);
100    arbore.inserare(30);
101    arbore.inserare(70);
102    arbore.inserare(20);
103    arbore.inserare(40);
104    
105    arbore.afisareInordine();  // 20 30 40 50 70
106    
107    cout << arbore.cauta(30) << endl;  // 1 (true)
108    
109    arbore.sterge(30);
110    arbore.afisareInordine();  // 20 40 50 70
111    
112    return 0;
113}

Complexitate

Cel mai rău caz apare când arborele degenerează în listă.