Arbori AVL

Definirea Arborelui Avl

Se numeste înalțime a unui arbore ca fiind
lungimea celui mai lung drum de la nodul
rădacină la unul din nodurile terminale.
Se numește factor de echilibrare diferența
dintre înalțimea subarborelui drept și înălțimea
subarborelui stâng.
Atașând fiecărui nod un câmp care reprezintă
factorul de echilibrare al său, se spune ca
arborele binar este echilibrat când toți factorii
de echilibrare ai nodurilor sunt -1,0,+1.
Exemplu printr-un desen
| hs – hd | ≤ 1, oricare ar fi
nodul X aparținând arborelui,
unde hs si hd reprezinta
înlățimea subarborelui stâng,
respective înălțimea
subarborelui drept.
Exemple de proceduri pentru calculul
Înălțimii unui subarbore și a factorilor de
echilibru
Înălțimea întregului arbore este 5.
Înălțimea subarborelui stâng al radăcinii este 4.
Pentru a afla factorul de echilibru al radăcinii
scădem înălțimea subarborelui stâng din înălțimea
subarborelui drept.
Factorul de echilibru al nodului cu eticheta 6 este 0.
Factorul de echilibru al nodului cu eticheta 5 este 1.
Practic, arborii AVL se comportă la fel ca arborii binari ordonați simpli, mai puțin
în cazul operațiilor de inserție și suprimare de chei .
O inserție într-un arbore binar ordonat poate duce la dezechilibrarea anumitor
noduri, dezechilibrare manifestată prin nerespectarea formulei | hs – hd | ≤ 1 pentru
respectivele noduri.
În principiu, o cheie se inserează într-o primă fază, ca și într-un arbore binar
ordonat obișnuit, adică se pornește de la rădăcină și se urmează fiul stâng sau fiul
drept, în funcție de relația dintre cheia de inserat și cheia nodurilor prin care se
trece, până se ajunge la un fiu nul, unde se realizează inserția propriu-zisă.
În acest moment se parcurge drumul invers (care este unic) și se caută pe acest
drum primul nod care nu este echilibrat, adică primul nod ai cărui subarbori diferă
ca înălțime prin 2 unități.
Acest nod trebuie echilibrat și el se va afla întotdeauna într-unul din cele 4 cazuri.
•Cazul 1-rotație simplă dreaptă
• Cazul 2-rotație simplă stangă – este simetric în
oglindă față de cazul 1-rotatie simplă dreaptă
•Cazul 3-
rotație
dublă
dreaptă
•Cazul 4-rotație dublă
stângă – simetric în
oglindă față de cazul
3-rotație dublă
dreaptă
Tehnica inserției nodurilor în arbori
echilibrati AVL
• Dându-se un arbore cu radacina R si având subarborii stâng si drept notati cu S si D, de
inaltimi hs si hd, la insertia unui nod în S se disting trei cazuri:
• 1. hs=hd - în urma insertiei, S si D devin de înaltimi inegale, verificând însa criteriul
echilibrului;
• 2. hs<hd - în urma insertiei S si D devin de înaltimi egale, deci echilibrul se
îmbunatateste;
• 3. hs>hd - criteriul echilibrului nu se mai verifica, arborele trebuie reechilibrat.
• Cazurile posibile care pot duce la necesitatea reechilibrarii se pot sintetiza in
urmatoarele, tinand cont de subarborele in care se face insertia (subarborele stang sau
drept) si de locul in cadrul subarborelui.
Reechilibrarea la inserția în
arbori AVL - Caz 1 stânga: 
Reechilibrarea la inserția in arbori AVL - Caz 2
stânga:
Reechilibrarea la inserția în arbori AVL - Caz 1
dreapta:
Reechilibrarea la insertia în arbori AVL - Caz
2 dreapta:
• Un algoritm pentru inserție si reechilibrare depinde de maniera în care e memorată informația
referitoare la situația echilibrului arborelui.
• O soluție e cea în care aceasta informație nu e inclusă în structura arborelui, atunci însa, factorul
de echilibrare al unui nod afectat de inserție, trebuind să fie determinat de fiecare dată, ducând
la mărirea regiei.
• Cu soluția a doua, inserția unui nod presupune etapele:
• 1. parcurgerea arborelui binar pentru determinarea locului de inserție sau a existenței deja a
cheii de inserat;
• 2. inserția noului nod și determinarea factorului de echilibrare corespunzator;
• 3. revenirea pe drumul de căutare și verificare a factorului de echilibru pentru fiecare nod -
presupune unele verificări redundante: dacă echilibrul e stabilit, nu ar mai fi necesară
verificarea factorului de echilibru pentru strămoșii nodului.
• Operatia de reechilibrare constă dintr-o secvență de reasignari de pointeri ( pointerii sunt de fapt
schimbați ciclic, rezultând fie o simplă, fie o dublă rotație a două sau trei noduri implicate) si
reajustări ale factorilor de echilibru.
Exemplul : Se consideră secventă de chei 4, 5, 7, 2, 1, 3, 6 care se
inserează într-un arbore AVL inițial vid. Evoluția arborelui AVL și
reechilibrările făcute sunt ilustrate in imagine.
• Arborii AVL se comportă la fel de bine ca cei perfect
echilibrati, fiind însa mai ușor de realizat. Testele
empirice sugerează că în medie, reechilibrarea e
necesară aproximativ la fiecare două inserții, rotațiile
simple si duble fiind echiprobabile.
• Arborii echilibrați trebuie utilizați numai când
operațiile de căutare sunt mult mai frecvente decât
cele de inserare.
 Ștergerea nodurilor în arborii AVL
• Cel mai simplu se pot șterge nodurile terminale și cele care au un singur
fiu. Daca nodul care trebuie să fie șters are doi fii, îl înlocuim prin nodul
aflat în extremă dreapta a subarborelui său stâng. Echilibrarea este
necesară numai dacă în urma ștergerii s-a redus înalțimea subarborelui. În
cazul cel mai defavorabil ștergerea unui nod se realizează in O(log n)
operații.
• Suprimarea sau ștergerea este mai complicată decât inserția, reechilibrarea
ramânând însa aceeasi, reducându-se la una sau două rotații la stânga sau la
dreapta. Tehnica ce stă la baza suprimării este cea prezentată la lucrarea
anterioară.
• În cazul cel mai defavorabil, suprimarea unui nod se realizează în O(log n)
operații. Diferența esențiala dintre inserție si suprimare în cazul arborilor
echilibrați constă în faptul că dacă în urma unei inserții, reechilibrarea se
realizează prin una sau două rotații, a doua sau trei noduri, suprimarea
poate necesita o rotație a fiecărui nod situat pe drumul de căutare.
• În realitate, testele experimentale indica faptul că reechilibrarea devine
necesară aproximativ la fiecare a doua inserție și la fiecare a cincea
suprimare.
 Exemplu: Se consideră arborele din imagine. În urma
ștergerii nodului cu cheia 6 apare necesitatea echilibrarii.
Exempl
u:
• Se va considera secvența de chei 4,5,7,2,1,3,6 care se insereaza într-
un arbore AVL inițial vid. Evoluția arborelui și echilibrările sunt: