BluePink BluePink
XHost 		Oferim servicii de instalare, configurare si monitorizare servere linux (router, firewall, dns, web, email, baze de date, aplicatii, server de backup, domain controller, share de retea) de la 50 eur / instalare. Pentru detalii accesati site-ul BluePink.

*

Inserarea nodurilor in arbori AVL

 

O insertie intr-un arbore binar ordonat poate duce la dezechilibrarea anumitor noduri, dezechilibrare manifestata prin nerespectarea formulei de pe slide-ul anterior pentru respectivele noduri.

*

*Daca in cazul arborilor binari ordonati simpli aceste situatii nu deranjeaza (acestia nefiind suficient de competenti pentru a le rezolva), in cazul arborilor AVL ele trebuie rezolvate pentru a asigura faptul ca si dupa o insertie sau o suprimare, arborele ramane un arbore AVL

*Vom discuta in continuare numai despre cazurile care apar la insertia cheilor, urmand sa tratam la final suprimarea cheilor folosindu-ne de aceleasi cazuri

*Principial, o cheie se insereaza intr-o prima faza, ca si intr-un arbore binar ordonat obisnuit, adica se porneste de la radacina si se urmeaza fiul stang sau fiul drept, in functie de relatia dintre cheia de inserat si cheia nodurilor prin care se trece, pana se ajunge la un fiu nul, unde se realizeaza insertia propriu-zisa

*In acest moment se parcurge drumul invers (care este unic) si se cauta pe acest drum primul nod care nu este echilibrat, adica primul nod ai carui subarbori difera ca inaltime prin 2 unitati

*Acest nod trebuie echilibrat si el se va afla intotdeauna intr-unul din cele 4 cazuri prezentate in continuare

  • Cazul 1-stanga:

  • *Cazul 1-dreapta (simetric in oglinda fata de cazul 1-stanga):

  • Cazul 2-stanga

 

  • *Cazul 2-dreapta (simetric in oglinda fata de cazul 2-stanga):

Pentru exemplificare, vom considera o situatie in care o insertie intr-un arbore AVL necesita reechilibrarea arborelui

 

*

 

*

*

*

*

*

 

*

*Insertia cheii ‘i’ se face ca intr-un arbore binar obisnuit, in dreapta cheii ‘h’

*Dupa insertie, se pleaca de la nodul inserat si se merge inapoi catre radacina, verificand ca toate nodurile intalnite sa respecte formula de echilibru AVL

*Primul nod dezechilibrat pe calea de cautare este nodul ‘g’

Trebuie sa echilibram subarborele care are radacina ‘g’

*Daca echilibram acest subarbore, intreg arborele va deveni un arbore AVL

Pentru aceasta, consideram doar subarborele cu radacina ‘g’ si stabilim in care dintre cele 4 cazuri de echilibrare ne situam

Se observa usor ca este vorba despre cazul 2-dreapta, deoarece cheia ‘i’ (cea care a dus la cresterea arborelui) se afla in subarborele rosu in raport cu cheia ‘g’ (daca s-ar fi aflat in subarborele mov, ne situam in cazul 1-dreapta)

In continuare, identificam pe arborele nostru concret, componentele modelului, folosind culori corespunzatoare

Pentru echilibrare, nu trebuie decat sa echilibram modelul corespunzator cazului 2-dreapta si apoi sa reconstruim arborele concret, pornind de la model si de la componentele identificate

*Reechilibrarea se face relativ simplu:

nRadacina arborelui echilibrat trebuie sa fie nodul albastru deschis, si pe slide-ul anterior am identificat acest nod ca fiind nodul ‘h’

nIdem pentru celelalte doua noduri cu nuante de albastru

nSubarborele verde trebuie legat la stanga nodului albastru inchis, si pe slide-ul anterior am identificat subarborele verde ca fiind cel ce contine doar cheia ‘d’

nIdem pentru ceilalti subarbori colorati, cu mentiunea ca subarborele galben este subarborele vid, deci nu a mai fost reprezentat

*Subarborele echilibrat este desenat mai jos, cu noduri albastre

*Legand acest subarbore de arborele initial, acesta devine echilibrat AVL la randul sau

*Practic, am inserat in arborele initial cheia ‘i’ care a provocat dezechilibrarea arborelui, dupa care am aplicat cazul de reechilibrare 2-dreapta asupra subarborelui corespunzator si am reobtinut un arbore AVL

*