Ideea pe care se bazează diferitele tipuri de arbori
echilibrați este că, dacă la punerea sau eliminarea unui nod arborele
se dezechilibrează, el poate fi reechilibrat prin efectuarea de
rotații. De exemplu, dacă se pun în arborele de căutare, în aceasta
ordine, elementele 1, 2 si 3, se obține structura din figura 1,a.
Arborele poate fi echilibrat prin rotirea către stânga în jurul
rădacinii, ajungându-se în situația din figura 1,b.
Astfel de rotații se pot face nu numai în arbore, ci și în subarborii acestuia. În unele situații, pentru echilibrarea arborelui, este necesar ca un nod, sau chiar un subarbore, sa "traverseze" rădăcina arborelui (subarborelui), deci să treacă din dreapta în stânga sau invers. De exemplu, pentru a reduce înalțimea arborelui din figura 2,a, se face o rotație spre stânga trecând nodul 4 în locul nodului 2 și nodul 2 în locul nodului 1, iar nodul 3 traversează din subarborele drept în cel stâng, ajungându-se în situația din figura 2,b. La traversare, deplasarea nodurilor se face împreună cu subarborii ai caror rădăcini sunt, eventual, aceste noduri.
Diferite tipuri de arbori echilibrați diferă prin algoritmii folosiți pentru aceste operații la punerea și eliminarea nodurilor. |
Cei mai cunoscuți arbori binari echilibrați utilizați în prezent sunt arborii AVL și arborii bicolori. Există, de asemenea, arbori de căutare echilibrați multicăi, cum sunt arborii 2-3-4 și arborii B.
Arborele AVL este un arbore de căutare binar,
care are următoarele proprietăți:
- diferența dintre înălțimile celor doi subarbori este
cel mult 1;
- orice subarbore al arborelui AVL este un arbore AVL.
Dacă, prin punerea unui nou nod, arborele se dezechilibrează, astfel
încât nu mai respecta proprietățile de mai sus, se fac rotații și
traversări care conduc la reechilibrarea arborelui.
Să considerăm că, la un moment dat, arborele AVL a ajuns în
situația din figura 3,a în care înălțimea subarborelui din
stânga nodului b este cu două unități mai mare decât cea a
subarborelui din dreapta lui B. La această situație s-a putut ajunge,
de exemplu, dacă initial cei doi subarbori de culoare albastră ai lui A
aveau inălțimi egale, dar s-a mai pus în arbore un nod mai mic decât A,
care a mărit înalțimea subarborelui albastru din stânga. Pentru a se
restabili proprietățile cerute unui arbore AVL, se procedează astfel: - se face o rotație la dreapta, în care A trece în locul lui B, iar B devine fiu dreapta al lui A; - subarborele albastru din dreapta lui A traversează din stânga în dreapta, rămânând pe același nivel și devenind subarbore stânga al lui B. Se ajunge astfel la structura din figura 3,b. Se observă că, datorită rotației, a coborât cu un nivel subarborele verde din dreapta și a urcat cu un nivel subarborele albastru din stânga, astfel ca toti subarborii se termină acum pe același nivel. Înălțimea globală a arborelui a scăzut cu o unitate, iar arborele este echilibrat.
Punerea unui nod într-un arbore AVL se realizează deci, în
principiu, astfel: În consecință, la punerea unui nod în arborele AVL, arborele este parcurs de două ori: de sus in jos, pentru căutarea locului în care va fi pus noul nod, și de jos în sus pentru echilibrare. În ambele cazuri, se efectuează un numar de pași având ca ordin de mărime inălțimea arborelui. Întrucat arborele este echilibrat, deci toate nivelurile sunt (aproape) pline, complexitatea algoritmului este O(log n). |
Arborele bicolor are următoarele proprietăți: - fiecare nod este roșu sau negru; - radăcina are întotdeauna culoarea neagră; - dacă un nod este roșu, fiii săi trebuie să fie negri (dar nu și reciproc); - toate căile de la rădăcină spre frunze sau spre fiii inexistenți trebuie să conțină un număr egal de noduri negre. Se demonstrează că orice arbore de căutare binar, care are aceste proprietăți, este echilibrat. În figura 4 este dat un exemplu de arbore bicolor corect.
La punerea unui nou nod într-un arbore bicolor, sau la eliminarea unui nod, se verifică respectarea acestor proprietăți și se fac rotații și traversări, însoțite de modificările de culori corespunzătoare ale nodurilor, astfel încât să fie respectate proprietățile menționate ale arborelui bicolor. Să considerăm, de exemplu, că în arborele din figura 4 se pune elementul 52. Căutându-i locul în arbore, constatăm că acesta trebuie să fie pus ca fiu stânga al nodului 54. Prin aceasta se încalcă însă regulile de colorare: dacă noul nod este roșu, înseamnă că vor exista două noduri rosii adiacente (54 si 12), iar dacă este negru, atunci pe calea 50-69-58-54-12 vor exista trei noduri negre, iar pe celelalte căi numai câte două. Pentru a restabili proprietățile arborelui se face o rotație la dreapta, astfel încât nodul 54 trece în locul lui 58, iar 58 devine fiu dreapta al lui 54 și se modifică culorile în mod corespunzător, ajungându-se în situația din figura 5.
Să considerăm acum că este necesar să punem în arborele din figura 5 elementul 76. Locul acestuia este ca fiu dreapta al nodului 73. Prin aceasta, însă, s-ar încălca iarăși condițiile impuse arborilor bicolori. Pentru a restabili proprietățile se face o rotație la stânga, astfel că nodul 69 trece în locul lui 50, astfel că 50 se deplasează spre stânga, iar subarborele cu rădacina 54 traversează la stânga, devenind fiu dreapta al nodului 50. Se fac și modificările de culoare corespunzătoare, ajungându-se în situația din figura 6, în care pe fiecare cale există două noduri negre.
Există diferite variante de algoritmi pentru punerea și eliminarea nodurilor din arborii bicolori, care sunt prezentați in manualele de specialitate. |