Algoritmi → Grafovi i stabla → Binarna stabla i binarno stablo pretrage

Binarna stabla i binarno stablo pretrage

Zapisivanje binarnog stabla

          1
        /   \
       2     3
      / \     \
     4   5     6

Najjednostavnije je čuvati dva niza: L[v] (levo dete) i R[v] (desno dete), sa 0 kada deteta nema. Za stablo sa slike: L[1]=2, R[1]=3, L[2]=4, R[2]=5, L[3]=0, R[3]=6, a čvorovi 4, 5 i 6 nemaju decu.

Tri obilaska: preorder, inorder, postorder

Obilasci se razlikuju samo po tome kada se ispisuje čvor u odnosu na podstabla:

#include <iostream>
using namespace std;

int L[1001], R[1001];

void preorder(int v) {
    if (v == 0) return;            // nema čvora
    cout << v << " ";
    preorder(L[v]);
    preorder(R[v]);
}
void inorder(int v) {
    if (v == 0) return;
    inorder(L[v]);
    cout << v << " ";
    inorder(R[v]);
}
void postorder(int v) {
    if (v == 0) return;
    postorder(L[v]);
    postorder(R[v]);
    cout << v << " ";
}

int main() {
    int n;
    cin >> n;                       // čvorovi 1..n, koren je 1
    for (int v = 1; v <= n; v++) cin >> L[v] >> R[v];
    preorder(1);  cout << endl;
    inorder(1);   cout << endl;
    postorder(1); cout << endl;
    return 0;
}

Postorder se koristi kada rezultat čvora zavisi od dece (visina, veličina podstabla), a preorder kada se informacija prenosi od korena ka listovima (dubina).

Visina binarnog stabla

Visina praznog stabla je −1, a inače 1 + veća od visina levog i desnog podstabla:

int visina(int v) {
    if (v == 0) return -1;                       // prazno stablo
    return 1 + max(visina(L[v]), visina(R[v]));
}

Binarno stablo pretrage (BST)

U BST-u za svaki čvor važi: sve vrednosti u levom podstablu su manje, a u desnom veće od vrednosti čvora. Traženje počinje od korena: ako je traženi broj manji, idemo levo, ako je veći – desno. Ubacivanje ide istim putem dok se ne dođe do praznog mesta.

Ubacivanje redom: 8 3 10 1 6 14 4

          8
        /   \
       3     10
      / \      \
     1   6      14
        /
       4

#include <iostream>
using namespace std;

const int MAXN = 100001;
int vr[MAXN], L[MAXN], R[MAXN];   // čvorovi se prave redom 1, 2, 3, ...
int brojCvorova = 0;

int ubaci(int v, int x) {         // ubacuje x u podstablo čvora v, vraća (novi) koren podstabla
    if (v == 0) {                 // prazno mesto: novi čvor
        brojCvorova++;
        vr[brojCvorova] = x;
        return brojCvorova;
    }
    if (x < vr[v]) L[v] = ubaci(L[v], x);
    else if (x > vr[v]) R[v] = ubaci(R[v], x);
    return v;                     // jednaki se ne ubacuju ponovo
}

bool nadji(int v, int x) {
    while (v != 0) {
        if (x == vr[v]) return true;
        v = (x < vr[v]) ? L[v] : R[v];
    }
    return false;
}

void inorder(int v) {
    if (v == 0) return;
    inorder(L[v]);
    cout << vr[v] << " ";
    inorder(R[v]);
}

int main() {
    int n, koren = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        koren = ubaci(koren, x);
    }
    inorder(koren);               // ispisuje brojeve sortirano!
    cout << endl;
    cout << (nadji(koren, 6) ? "6 postoji" : "6 ne postoji") << endl;
    cout << (nadji(koren, 7) ? "7 postoji" : "7 ne postoji") << endl;
    return 0;
}

Inorder obilazak BST-a daje vrednosti sortirano – to je ujedno i način da se proveri da li je stablo ispravan BST.

Složenost i balansirana stabla

Traženje i ubacivanje rade onoliko koraka kolika je visina stabla. Ako su brojevi ubacivani u slučajnom redosledu, visina je oko log₂ n. Ali ako se ubacuju već sortirani (1, 2, 3, …), stablo postaje lanac visine n i sve operacije su O(n).

Balansirana stabla (crveno-crna, AVL) se sama preuređuju tako da visina ostane O(log n). Ne treba ih pisati ručno: C++ set i map su upravo balansirana binarna stabla pretrage.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje