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.
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.
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.
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.
Punerea unui nod intr-un arbore se realizeaza deci, in principiu, astfel:
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). |
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.
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.
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.
Exista diferite variante de algoritmi pentru punerea si eliminarea nodurilor din arborii bicolori, care sunt prezentati in manualele de specialitate. |