Arbori binari de căutare

Arbori binari de cautare

1. Definiţii

Un arbore este un graf orientat in care nu exista nici un ciclu(graf orientat aciclic)

Un arbore binar este o multime de n >= 0 noduri, care daca nu este vida, contine un nod numit radacina, restul nodurilor formând doi arbori disjuncti numiti subarborele stâng si subarborele drept.

Aceasta structura de date e importanta pentru ca e usor de reprezentat si prelucrat, orice arbore putând fi transformat în arbore binar

2. Transformarea unui arbore generalizat în arbore binar

Un arbore generalizat poate fi transformat intr-un arbore binar, astfel incât secventele de noduri pentru parcurgerea in preordine sa fie identice in cazul ambilor arbori.

Un arbore generalizat A cu radacina A1 si subarborii A1,1, A1,2, ,A1,k se transforma în arbore binar având radacina A1, A1,1 fiul sau stâng, iar A1,i devin fiii drepti ai lui A1,i-1 pentru 2<=i<=k.

Secventele de noduri în parcurgerea în preordine a arborelui generalizat si a celui binar obtinut prin transformare, sunt identice.

Exemplu: Se considera arborele generalizat de mai sus. Aplicând regula descrisa, se obtine arborele binar reprezentat.

Implementarea arborilor binari

Un arbore binar poate fi descris cu ajutorul urmatoarei structuri de date dinamice:

typedef struct informatie{

char nume[100];

long int pret ;

int cantitate;

}s;

typedef struct arbore{

informatie inf;

arbore *st,*dr;

}nod;

nod*prim,*prim1;

3. Operatorii arborelui binar

INITIALIZEAZA(A) - face vid arborele A;

INSEREAZA(X,A) - insereaza cheia X în arborele A;

CAUTA(X,A) - cauta cheia X, returnând true la gasire;

SUPRIMA(X,A) - suprima cheia X, daca exista;

TRAVERSEAZA(A) - parcurge toate cheile arborelui A

4. Arbori binari de cautare- Creare

Se numeste arbore de cautare un arbore binar ale carui noduri au o cheie de identificare, iar pentru fiecare nod sunt valabile proprietatile urmatoare:

- Orice cheie asociata unui nod este mai mare decat cheia subordonatului stang

- Orice cheie asociata unui nod este mai mica decat cheia subordonatului drept

Cheile de identificare sunt distincte.

Fie arborele din figura urmatoare. Cheile sunt : 30, 21 , 27, 15, 37, 31, 33, 36, 35, 24

Observatie: ordinea de inserare a cheilor poate determina o alta configuratie pentru arbore. Spre exemplu daca se insereaza mai intai 30 si apoi 27 si 21 atunci 27 va deveni subordonat stang pentru 30 si 21 subordonat stang pentru 27.

Crearea arborilor de cautare se realizeaza aplicand de un numar de ori operatia de inserare. Inserarea se realizeaza astfel:

-se compara valoarea k de inserat cu cheia asociata nodului curent. Exista urmatoarele posibilitati:

- cheia coincide cu valoarea de inserat si se renunta la inserare

- cheia este mai mica decat k caz in care se incearca inserarea in subarborele drept

- cheia este mai mare decat k caz in care se incearca inserarea in subarborele stang

- inserarea propriuzisa se realizeaza atunci candsubarborele stang , respectiv drept, este vid, altfel se reia.

Parcurgerea arborilor de cautare se face ca orice arbore binar (svd, vsd sdv).

Cautarea unei valori se determina in mod similar cu subprogramul de inserare