CNDVinfo: Lectii C++

Arbori binari

În informatică, un arbore binar este un arbore în care fiecare nod are cel mult doi succesori (fii). De obicei, succesorii se numesc „nodul stânga” și „nodul dreapta”. Arborii binari sunt folosiți mai ales drept arbori binari de căutare sau și la structurile de date de tip heap.

În informatica un arbore binar de căutare este un arbore binar cu următoarele proprietăți:

§ fiecare nod are o valoare asociată;

§ o relație de ordine este definită pe aceste valori;

§ pentru fiecare nod, subarborele stâng conține valori mai mici decât cea a nodului, iar cel drept conține valori mai mari decât cea a nodului.

Arborii binari de căutare sunt utili în special în contextul algoritmilor de sortare și de căutare, cum ar fi parcurgerea în in ordine, care sunt foarte eficienți.

Arbore binar

Arbore binar de cautare

Tehnica transformarii 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 preordinesa fie identice in cazul ambilor arbori.

Un arbore generalizat A cu radacina A₁ si subarborii A_1,1, A_1,2, ...,A_1,k se transforma în arbore binar având radacina A₁, A_1,1 fiul sau stâng, iar A_1,i devin fiii drepti ai lui A_1,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.

Arbori binari ordonati. Arbori binari de înaltime minima

Arborele binar ordonat e arborele binar cu proprietatea ca parcurgând nodurile în in ordine, secventa cheilor este monoton crescatoare.

Are proprietatea ca daca un nod oarecare al arborelui are cheia c, toate nodurile din subarborele stâng al nodului au cheile mai mici decât valoarea c, respectiv toate cheile din subarborele drept au cheile mai mari sau egale cu c.

De aici rezulta procedeul de cautare foarte simplu, prin trecerea la fiul stâng sau drept de la nodul curent, functie de relatia dintre cheia cautata si cea a nodului curent.

Cum înaltimea minima a unui arbore binar ordonat cu n noduri este hmin=[log₂ (n+1)],
rezulta ca o cautare într-un arbore binar ordonat necesita aproximativ log₂n comparatii de chei, fata de n/2 comparatii într-o lista liniara.

Tehnica suprimarii unui nod dintr-un arbore binar ordonat

În urma suprimarii unui nod având cheia x dintr-un arbore binar ordonat, acesta trebuie sa ramâna ordonat.

Cazurile ce se disting sunt functie de numarul de fii ai nodului ce se suprima. Daca numarul fiilor este:

cel mult unu - referinta spre nodul de suprimat se inlocuieste cu referinta spre unicul sau fiu ( sau nil daca nodul e terminal );

doi fii - se cauta predecesorul nodului în ordonarea arborelui în in ordine
se demonstreaza ca acesta exista si nu are fiu drept; se gaseste construind secventa formata din fiul stâng al nodului de suprimat si apoi fiii drepti pâna la cel ce nu are descendent drept;
se asigneaza toate câmpurile de informatie ( nu de înlantuire ) ale nodului de suprimat cu cele ale predecesorului sau;
se suprima predecesorul ( nu are fiu drept ).

Arbori binari total echilibrati

Un arbore binar total echilibrat este un arbore binar care îndeplineste urmatoarea conditie: numarul nodurilor unui oricare subarbore stâng difera cu cel mult 1 în plus fata de numarul nodurilor subarborelui corespunzator drept. Rezulta ca frunzele sale se afla pe ultimele doua niveluri.

Algoritmul de construire a unui arbore binar total echilibrat cu n noduri, este urmatorul:

a) un nod este radacina;

b) se iau nstg = [n/2] noduri pentru arborele stâng si se trece la construirea lui (pasul a);

c) se iau cele ndr=n-nstg-1 noduri ramase pentru subarborele drept si se trece la construirea lui (pasul a).

Pentru oricare nod exista relatia:

ndr <= nstg <= ndr + 1

Exemplu de echilibrare: