Arbori de cautare echilibrati

S-a aratat in sectiunea "Arbori de cautare" ca, in cazul arborilor de cautare obisnuiti, complexitatea operatiilor de cautare sau punere a unui nod este situata intre O(log n) si O(n). Cazul cel mai defavorabil se obtine atunci cand nodurile se pun in arbore in ordine crescatoare sau descrescatoare, astfel ca arborele degenereaza practic intr-o lista inlantuita. Pentru ca aceasta complexitate sa fie logaritmica, O(log n), este necesar ca arborele sa fie echilibrat, adica inaltimea subarborelui stang sa fie aproximativ egala cu inaltimea subarborelui drept, aceasta proprietate fiind valabila si pentru toti subarborii pe care ii contine. Pentru ca arborele sa se mentina echilibrat, indiferent de ordinea in care sunt puse sau eliminate nodurile, este necesasr sa se modifice in mod corespunzator algoritmii prin care se fac aceste operatii.
 
Ideea pe care se bazeaza diferitele tipuri de arbori echilibrati este ca, daca la punerea sau eliminarea unui nod arborele se dezechilibreaza, el poate fi reechilibrat prin efectuarea de rotatii. De exemplu, daca se pun in arborele de cautare, in aceasta ordine, elementele 1, 2 si 3, se obtine structura din figura 1,a. Arborele poate fi echilibrat prin rotirea catre stanga in jurul radacinii, ajungandu-se in situatia din figura 1,b.


- Figura 1 -

Astfel de rotatii se pot face nu numai in arbore, ci si in subarborii acestuia. In unele situatii, pentru echilibrarea arborelui, este necesar ca un nod, sau chiar un subarbore, sa "traverseze" radacina, deci sa treaca din dreapta in stanga sau invers. De exemplu, pentru a reduce inaltimea arborelui din figura 2,a, se face o rotatie spre stanga trecand nodul 4 in locul nodului 2 si nodul 2 in locul nodului 1, iar nodul 3 traverseaza din subarborele drept in cel stang, ajungandu-se in situatia din figura 2,b. Deplasarea nodurilor se face impreuna cu subarborii ai caror radacini sunt, eventual, aceste noduri.


- Figura 2 -

Diferite tipuri de arbori echilibrati difera prin algoritmii folositi pentru aceste operatii la punerea si eliminarea nodurilor.

Cei mai cunoscuti arbori binari echilibrati utilizati in prezent sunt arborii AVL si arborii bicolori. Exista, de asemenea, arbori de cautare echilibrati multicai, cum sunt arborii 2-3-4 si arborii B.

Arbori AVL

Conceptul de arbore echilibrat a fost introdus in anul 1962 de catre Adelson-Velski si Landis, de unde si numele de arbore AVL. Exista in prezent mai multe variante, care difera intre ele prin algoritmii folositi la punerea sau adaugarea de noduri.

Arborele AVL este un arbore de cautare binar, care are urmatoarele proprietati:
  - diferenta dintre inaltimile celor doi subarbori este cel mult 1;
  - orice subarbore al arborelui AVL este un arbore AVL.

Daca, prin punerea unui nou nod, arborele se dezechilibreaza, astfel incat nu mai respecta conditiile de mai sus, se fac rotatii si traversari care conduc la reechilibrarea arborelui.
 
Sa consideram ca, la un moment dat, arborele AVL a ajuns in situatia din figura 3,a in care inaltimea subarborelui din stanga  nodului b este cu doua unitati mai mare decat cea a subarborelui din dreapta lui B. La aceasta situatie s-a putut ajunge, de exemplu, daca initial cei doi subarbori de culoare albastra ai lui A aveau inaltimi egale, dar s-a mai pus in arbore un nod mai mic decat A, care a marit inaltimea subarborelui albastru din stanga. Pentru a se restabili proprietatile cerute unui arbore AVL, se procedeaza astfel: 
    - se face o rotatie la dreapta, in care A trece in locul lui B, iar B devine fiu dreapta al lui A;
    - subarborele albastru din dreapta lui A traverseaza din stanga in dreapta, ramanand pe acelasi nivel si devenind subarbore stanga al lui B. Se ajunge astfel la structura din figura 3,b. Se observa ca, datorita rotatiei, a coborat cu un nivel  subarborele verde din dreapta si a urcat cu un nivel subarborele albastru din stanga, astfel ca toti subarborii se termina acum pe acelasi nivel. Inaltimea globala a arborelui a scazut cu o unitate, iar arborele este echilibrat.


- Figura 3 -

Punerea unui nod intr-un arbore se realizeaza deci, in principiu, astfel:
   - in prima etapa se pune nodul in arbore in mod obisnuit;
   - in a doua etapa se verifica daca, in urma operatiei precedente, s-a ajuns in situatia in care unt incalcate conditiile impuse unui arbore AVL si se fac rotatiile si traversarile necesare restabilirii acestor conditii. In acest scop, este necesar ca fiecare nod  sa contina, in afara de informatia atasata, si un camp care indica inaltimea subarborelui a carui radacina este. Echilibrarea subarborilor se propaga de jos in sus, pana la radacina arborelui.

In consecinta, la punerea unui nod in arborele AVL, arborele este parcurs de doua ori: de sus in jos, pentru cautarea locului in care va fi pus noul nod, si de jos in sus pentru echilibrare. In ambele cazuri se efectueaza un numar de pasi avand ca ordin de marime inaltimea arborelui. Intrucat arborele este echilibrat, deci toate nivelurile sunt (aproape) pline, complexitatea algoritmului este O(log n).

Arbori bicolori

Arborele bicolor este un arbore de cautare binar, in care fiecare nod are un atribut suplimentar, numit culoare. Se folosesc doua culori, de unde provine si numele arborelui. Se obisnuieste ca culorile folosite sa fie rosu si negru, din care cauza in engleza un astfel de arbore se numeste red-black tree. In practica, pentru memorarea culorii clasa Nod, in afara de campurile obisnuite ale nodului de arbore binar (Object info si Nod fiuStanga, fiuDreapta) contine un camp suplimentar boolean red, care are valoarea true daca nodul are culoarea rosie sau false in caz ca acesta este negru.
 
Arborele bicolor are urmatoarele proprietati:
    - fiecare nod este rosu sau negru;
    - radacina are intotdeauna culoarea neagra;
    - daca un nod este rosu, fiii sai trebuie sa fie negri (dar nu si reciproc);
    - toate caile de la radacina spre frunze sau spre fiii inexistenti trebuie sa contina un numar egal de noduri negre.

Se demonstreaza ca orice arbore de cautare binar, care are aceste proprietati, este echilibrat. In figura 4 este dat un exemplu de arbore bicolor corect.


- Figura 4 -

La punerea unui nou nod intr-un arbore bicolor, sau la eliminarea unui nod, se verifica respectarea acestor proprietati si se fac rotatii si traversari, insotite de modificarile de culori corespunzatoare ale nodurilor, astfel incat sa fie respectate proprietatile mentionate ale arborelui bicolor. Sa consideram, de exemplu, ca in arborele din figura 4 se pune elementul 52. Cautandu-i locul in arbore, constatam ca acesta trebuie sa fie pus ca fiu stanga al nodului 54. Prin aceasta se incalca insa regulile de colorare: daca noul nod este rosu, inseamna ca vor exista doua noduri rosii adiacente (54 si 12), iar daca este negru, atunci pe calea 50-69-58-54-12 vor exista trei noduri negre, iar pe celelalte cai numai cate doua. Pentru a restabili proprietatile arborelui se face o rotatie la dreapta, astfel incat nodul 54 trece in locul lui 58, iar 58 devine fiu dreapta al lui 54 si se modifica culorile in mod corespunzator, ajungandu-se in situatia din figura 5.


- Figura 5 -

Sa consideram acum ca este necesar sa punem in arborele din figura 5 elementul 76. Locul acestuia este ca fiu dreapta al nodului 73. Prin aceasta, insa, s-ar incalca iarasi conditiile impuse arborilor bicolori. Pentru a restabili proprietatile se face o rotatie la stanga, astfel ca nodul 69 trece in locul lui 50, 50 se deplaseaza spre stanga, iar subarborele cu radacina 54 traverseaza la stanga, devenind fiu dreapta al nodului 50. Se fac si modificarile de culoare corespunzatoare, ajungandu-se in situatia din figura 6, in care pe fiecare cale exista doua noduri negre.


- Figura 6 -

Exista diferite variante de algoritmi pentru punerea si eliminarea nodurilor din arborii bicolori, care sunt prezentati in manualele de specialitate.

Complexitatea operatiilor cu arbori bicolori echilibrati

Intrucat arborii binari echilibrati au toate nivelurile (aproape) complete, inaltimea lor este de ordinul log2n, unde n este numarul de noduri. In consecinta, atat cautarea, cat si punerea sau eliminarea de noduri din acesti arbori au complexitate logaritmica O(log n). Avand in vedere ca la punerea de noduri in arborii AVL sunt necesare doua parcurgeri (de sus in jos pentru cautare si de jos in sus pentru reechilibrare), in timp ce la arborii bicolori este suficienta o singura parcurgere (de sus in jos), timpul de calcul este ceva mai mic la arborii bicolori.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati