Arbori de căutare echilibrați

S-a arătat în secțiunea "Arbori de căutare" că, în cazul arborilor de căutare obișnuiți, complexitatea operațiilor de căutare sau punere a unui nod este situată între O(log n) și O(n). Cazul cel mai defavorabil se obține atunci cănd nodurile se pun în arbore în ordine crescătoare sau descrescătoare, astfel că arborele degenerează practic într-o listă înlanțuită. Pentru ca această complexitate sa fie logaritmică, O(log n), este necesar ca arborele să fie echilibrat, adică înaltimea subarborelui stâng să fie aproximativ egală cu înălțimea subarborelui drept, această proprietate fiind valabilă și pentru toți subarborii pe care îi conține. Pentru ca arborele să se mențină echilibrat, indiferent de ordinea în care sunt puse sau eliminate nodurile, este necesasr să se modifice în mod corespunzător algoritmii prin care se fac aceste operații.
 
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.


- Figura 1 -

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.


- Figura 2 -

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.

Arbori AVL

Conceptul de arbore echilibrat a fost introdus în anul 1962 de către Adelson-Velski si Landîș, de unde și numele de arbore AVL. Există în prezent mai multe variante, care diferă între ele prin algoritmii folosiți la punerea sau eliminarea de noduri.

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.


- Figura 3 -

Punerea unui nod într-un arbore AVL se realizează deci, în principiu, astfel:
   - în prima etapă, se pune nodul în arbore în mod obișnuit;
   - în a doua etapă, se verifică dacă, în urma operației precedente, s-a ajuns în situația în care sunt încălcate condițiile impuse unui arbore AVL și se fac rotațiile și traversările necesare restabilirii acestor condiții. În acest scop, este util ca fiecare nod  să conțină, în afară de informația atașata, și un câmp care indică înălțimea subarborelui a cărui rădacină este. Echilibrarea subarborilor se propagă de jos în sus, până la rădăcina arborelui.

Î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).

Arbori bicolori

Arborele bicolor este un arbore de căutare binar, în care fiecare nod are un atribut suplimentar, numit culoare. Se folosesc două culori, de unde provine și numele arborelui. Se obisnuiește ca culorile folosite să fie roșu și negru, din care cauză în engleză un astfel de arbore se numește red-black tree. În practică, pentru memorarea culorii, clasa Nod, în afară de câmpurile obișnuite ale nodului de arbore binar (Object info si Nod fiuStanga, fiuDreapta) conține un câmp suplimentar boolean red, care are valoarea true dacă nodul are culoarea roșie sau false în caz că acesta este negru.
 
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.


- Figura 4 -

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.


- 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.


- Figura 6 -

Există diferite variante de algoritmi pentru punerea și eliminarea nodurilor din arborii bicolori, care sunt prezentați in manualele de specialitate.

Complexitatea operațiilor cu arbori bicolori echilibrați

Întrucât arborii binari echilibrați au toate nivelurile (aproape) complete, înălțimea lor este de ordinul log2n, unde n este numărul de noduri. În consecință, atât căutarea, cât și punerea sau eliminarea de noduri din acești arbori au complexitate logaritmică O(log n). Având în vedere că la punerea de noduri în arborii AVL sunt necesare două parcurgeri (de sus in jos pentru căutare și de jos în sus pentru reechilibrare), în timp ce la arborii bicolori este suficientă o singură parcurgere (de sus în jos), timpul de calcul este ceva mai mic la arborii bicolori.



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