Arbori Binari

Definire:

Arborii sunt structuri de date dinamice şi omogene. In arborescenţă, există un nod numit rădăcină sau părinte. Acesta are descendenţi. Fiecare descendent poate fi, la rândul său, părinte şi, în acest caz, are descendenţi.

Arborele binar este caracterizat prin aceea că, orice nod al său are un singur părinte şi maxim doi descendenţi. Fiecare nod este reprezentat prin trei informaţii şi anume:

- informaţia utilă care face obiectul prelucrării, ea descriind elementul sau fenomenul asociat nodului;

- informaţia care localizează nodul părinte;

- informaţia (informaţiile) care localizează nodul (nodurile) descendent (descendente).

Arborele binar A este o mulţime de chei care poate fi, fie vidă, fie conţine un element numit rădacină şi exact doi arbori binari As şi Ad, A= .

Rangul unui nod reprezintă numărul de subarbori asociaţi cu acel nod. Un nod care are rangul 0 se numeşte frunză. Pentru arborele binar A, definit mai sus, radăcinile rs şi rd ale subarborilor As şi Ad, se numesc fii ai rădăcinii r a arborelui A, iar r se numeşte părintele lui rs şi rd.

Din definiţie se observă că oricare dintre mulţimile A, As şi Ad poate fi vidă, în consecinţă orice nod din arborele binar poate avea 0, 1 sau 2 fii.

Reprezentarea pe niveluri determina sa nu mai fie necesar sensul arcelor. Fiecare varf poate fi considerat radacina pentru un subarbore. Evident, pentru fiecare varf vom avea subarborele stang si subarborele drept, eventual unul din ei sau amandoi putand fi arbori vizi (fara nici un varf).

Arborii binari sunt arbori în care nodurile conţin cel mult doi descendenţi. Pentru reprezentarea în memorie a unui nod dintr-un arbore binar este nevoie de 3 câmpuri: un câmp ce conţine informaţia utilă, şi două câmpuri pentru a memora legăturile nodului cu subarborele stâng, respectiv subarborele drept. Pentru memorarea acestor arbori se poate folosi o structură mai simplă de forma:

struct nod_arb

{

int inf;

nod_arb *st, *dr;

};

Un arbore in care operaţiile de căutare sunt foarte rapide se numşte arbore de căutare. Arborii de căutare sunt folosiţi pentru a memora o mulţime finită de chei alese dintr-o multime total ordonată de chei. Fiecare nod din arborii de căutare conţine una sau mai multe chei şi toate cheile din arbore sunt unice. Nu se memorează chei duplicate. Diferenţa dintre arborii oarecare şi arborii de căutare este că în arborii de căutare cheile nu sunt memorate în noduri arbitrare din arbore. În schimb, există un criteriu de ordine care determină unde trebuie memorată o cheie ce se află în relaţie cu alte chei din arbore.

Arborii binari de căutare sunt arbori binari în care nodurile sunt memorate ordonat în funcţie de o cheie. Toate nodurile din arbore au în subarborele stâng noduri care au chei mai mici şi în subarborele drept chei mai mari.

Parcurgerea unui arbore de căutare în ordinea stânga – rădăcină – dreapta conduce la obţinerea listei nodurilor în ordinea crescătoare a cheilor.

Arborii binari de căutare sunt perfect echilibraţi dacă pentru fiecare nod din arbore numărul de noduri din subarborele stâng diferă de numărul de noduri din subarborele drept prin cel mult un nod. Deoarece operaţiile de inserare şi ştergere nu permit menţinerea echilibrării perfecte a unui arbore, iar restructurarea arborelui după aceste operatii este o procedură foarte complexă, de obicei se preferă arbori imperfect echilibraţi care vor fi numiţi arbori echilibraţi.

Un arbore este echilibrat dacă si numai dacă, pentru orice nod, înaltimile celor doi subarbori diferă cu cel mult 1. Arborele perfect echilibrat este cel în care, pentru fiecare nod, numarul de noduri ale subarborelui stâng difera de cel pentru subarborele drept cu cel mult o unitate. Arborele perfect echilibrat are o serie de proprietati dintre care se remarca faptul ca nodul radacina si nodurile interne au strict 2 descendenti.