AVL Tree va ser inventat per GM Adelson - Velsky i EM Landis el 1962. L'arbre rep el nom d'AVL en honor als seus inventors.
L'arbre AVL es pot definir com un arbre de cerca binari equilibrat en alçada en el qual cada node s'associa amb un factor d'equilibri que es calcula restant l'alçada del seu subarbre dret de la del seu subarbre esquerre.
Es diu que l'arbre està equilibrat si el factor d'equilibri de cada node està entre -1 i 1, en cas contrari, l'arbre estarà desequilibrat i caldrà equilibrar-lo.
Factor d'equilibri (k) = alçada (esquerra (k)) - alçada (dreta (k))
Si el factor d'equilibri de qualsevol node és 1, vol dir que el subarbre esquerre és un nivell més alt que el subarbre dret.
Si el factor d'equilibri de qualsevol node és 0, vol dir que el subarbre esquerre i el subarbre dret contenen la mateixa alçada.
Si el factor d'equilibri de qualsevol node és -1, vol dir que el subarbre esquerre és un nivell més baix que el subarbre dret.
A la figura següent es mostra un arbre AVL. Podem veure que, el factor d'equilibri associat a cada node està entre -1 i +1. per tant, és un exemple d'arbre AVL.
Complexitat
| Algorisme | Cas mitjà | Pitjor dels casos |
|---|---|---|
| Espai | o(n) | o(n) |
| Cerca | o (log n) | o (log n) |
| Insereix | o (log n) | o (log n) |
| Suprimeix | o (log n) | o (log n) |
Operacions a l'arbre AVL
A causa del fet que, l'arbre AVL també és un arbre de cerca binari, per tant, totes les operacions es realitzen de la mateixa manera que es realitzen en un arbre de cerca binari. La cerca i la travessa no condueixen a la violació de la propietat de l'arbre AVL. No obstant això, la inserció i la supressió són les operacions que poden violar aquesta propietat i, per tant, s'han de revisar.
| SN | Funcionament | Descripció |
|---|---|---|
| 1 | Inserció | La inserció a l'arbre AVL es realitza de la mateixa manera que es realitza en un arbre de cerca binari. Tanmateix, pot provocar una violació de la propietat de l'arbre AVL i, per tant, l'arbre pot necessitar un equilibri. L'arbre es pot equilibrar aplicant rotacions. |
| 2 | Eliminació | La supressió també es pot realitzar de la mateixa manera que es fa en un arbre de cerca binari. La supressió també pot alterar l'equilibri de l'arbre, per tant, s'utilitzen diversos tipus de rotacions per reequilibrar l'arbre. |
Per què AVL Tree?
L'arbre AVL controla l'alçada de l'arbre de cerca binari sense deixar-lo esbiaixat. El temps necessari per a totes les operacions en un arbre de cerca binari d'alçada h és O(h) . No obstant això, es pot estendre a O(n) si el BST es desvia (és a dir, el pitjor dels casos). En limitar aquesta alçada al registre n, l'arbre AVL imposa un límit superior a cada operació O(log n) on n és el nombre de nodes.
Rotacions AVL
Realitzem la rotació a l'arbre AVL només en cas que el factor d'equilibri sigui diferent -1, 0 i 1 . Bàsicament hi ha quatre tipus de rotacions que són els següents:
- Rotació L L: el node inserit es troba al subarbre esquerre del subarbre esquerre d'A
- Rotació R R: el node inserit es troba al subarbre dret del subarbre dret de A
- Rotació L R: el node inserit es troba al subarbre dret del subarbre esquerre d'A
- Rotació R L: el node inserit es troba al subarbre esquerre del subarbre dret de A
On el node A és el node el factor d'equilibri del qual és diferent de -1, 0, 1.
Les dues primeres rotacions LL i RR són rotacions simples i les dues següents rotacions LR i RL són rotacions dobles. Perquè un arbre estigui desequilibrat, l'alçada mínima ha de ser com a mínim 2, Entenem cada rotació
1. Rotació RR
Quan el BST es desequilibra, a causa que un node s'insereix al subarbre dret del subarbre dret de A, llavors fem la rotació RR, la rotació RR és una rotació en sentit contrari a les agulles, que s'aplica a la vora per sota d'un node amb un factor d'equilibri -2.
A l'exemple anterior, el node A té un factor d'equilibri -2 perquè s'insereix un node C al subarbre dret del subarbre dret A. Realitzem la rotació RR a la vora de sota A.
2. Rotació LL
Quan BST es desequilibra, a causa que un node s'insereix al subarbre esquerre del subarbre esquerre de C, llavors fem la rotació LL, la rotació LL és una rotació en sentit horari, que s'aplica a la vora per sota d'un node amb factor d'equilibri 2.
A l'exemple anterior, el node C té un factor d'equilibri 2 perquè s'insereix un node A al subarbre esquerre del subarbre esquerre C. Realitzem la rotació LL a la vora sota A.
3. Rotació LR
Les rotacions dobles són una mica més dures que la rotació simple que ja s'ha explicat anteriorment. Rotació LR = rotació RR + rotació LL, és a dir, la primera rotació RR es realitza al subarbre i després la rotació LL es realitza a l'arbre complet, per arbre complet ens referim al primer node del camí del node inserit el factor d'equilibri del qual és diferent de -1 , 0 o 1.
Entenem cada pas molt clarament:
| Estat | Acció |
|---|---|
 | S'ha inserit un node B al subarbre dret de A el subarbre esquerre de C, a causa del qual C s'ha convertit en un node desequilibrat amb factor d'equilibri 2. Aquest cas és la rotació L R on: El node inserit es troba al subarbre dret del subarbre esquerre de C |
 | Com que la rotació LR = RR + rotació LL, per tant, RR (en sentit antihorari) en el subarbre arrelat a A es realitza primer. Fent la rotació RR, node A , s'ha convertit en el subarbre esquerre de B . |
 | Després de realitzar la rotació RR, el node C encara està desequilibrat, és a dir, té un factor d'equilibri 2, ja que el node A inserit es troba a l'esquerra de l'esquerra de C |
 | Ara fem la rotació LL en sentit horari a l'arbre complet, és a dir, al node C. node C ara s'ha convertit en el subarbre dret del node B, A és el subarbre esquerre de B |
 | El factor d'equilibri de cada node és ara -1, 0 o 1, és a dir, BST està equilibrat ara. |
4. Rotació RL
Com ja s'ha comentat, aquestes rotacions dobles són una mica més dures que la rotació simple que ja s'ha explicat anteriorment. Rotació RL = rotació LL + rotació RR, és a dir, la primera rotació LL es realitza al subarbre i després la rotació RR es realitza a l'arbre complet, per arbre complet ens referim al primer node del camí del node inserit el factor d'equilibri del qual és diferent de -1 , 0 o 1.
| Estat | Acció |
|---|---|
 | Un node B s'ha inserit al subarbre esquerre de C el subarbre dret de A , per la qual cosa A s'ha convertit en un node desequilibrat amb un factor d'equilibri - 2. Aquest cas és la rotació RL on: El node inserit es troba al subarbre esquerre del subarbre dret d'A |
 | Com a rotació RL = rotació LL + rotació RR, per tant, LL (en el sentit de les agulles del rellotge) al subarbre arrelat a C es realitza primer. Fent la rotació RR, node C s'ha convertit en el subarbre adequat de B . |
 | Després de realitzar la rotació LL, node A encara està desequilibrat, és a dir, té un factor d'equilibri -2, que es deu al subarbre dret del node A del subarbre dret. |
 | Ara fem la rotació RR (rotació en sentit contrari a les agulles de les agulles) a l'arbre complet, és a dir, al node A. C ara s'ha convertit en el subarbre dret del node B i el node A s'ha convertit en el subarbre esquerre de B. |
 | El factor d'equilibri de cada node és ara -1, 0 o 1, és a dir, BST està equilibrat ara. |
P: Construeix un arbre AVL amb els elements següents
H, I, J, B, A, E, C, F, D, G, K, L
1. Insereix H, I, J
En inserir els elements anteriors, especialment en el cas de H, el BST es desequilibra ja que el factor d'equilibri de H és -2. Com que el BST està esbiaixat a la dreta, realitzarem la rotació RR al node H.
L'arbre d'equilibri resultant és:
2. Insereix B, A
En inserir els elements anteriors, especialment en el cas d'A, el BST es desequilibra ja que el factor d'equilibri de H i I és 2, considerem el primer node de l'últim node inserit, és a dir, H. Com que el BST de H està esbiaixat a l'esquerra, realitzarem la rotació LL al node H.
L'arbre d'equilibri resultant és:
3. Insereix E
En inserir E, BST es desequilibra ja que el factor d'equilibri de I és 2, ja que si viatgem d'E a I trobem que està inserit al subarbre esquerre del subarbre dret de I, realitzarem la rotació LR al node I. LR = Rotació RR + LL
ls comanda linux
3 a) Primer realitzem la rotació RR al node B
L'arbre resultant després de la rotació RR és:
3b) Primer realitzem la rotació LL al node I
L'arbre equilibrat resultant després de la rotació LL és:
4. Insereix C, F, D
En inserir C, F, D, BST es desequilibra ja que el factor d'equilibri de B i H és -2, ja que si viatgem de D a B trobem que s'insereix al subarbre dret del subarbre esquerre de B, realitzarem RL Rotació al node I. RL = LL + RR rotació.
4a) Primer realitzem la rotació LL al node E
L'arbre resultant després de la rotació LL és:
4b) A continuació, realitzem la rotació RR al node B
L'arbre equilibrat resultant després de la rotació RR és:
5. Insereix G
En inserir G, BST es desequilibra ja que el factor d'equilibri de H és 2, ja que si viatgem de G a H, trobem que s'insereix al subarbre esquerre del subarbre dret de H, realitzarem la rotació LR al node I. LR = RR + LL rotació.
5 a) Primer realitzem la rotació RR al node C
L'arbre resultant després de la rotació RR és:
5 b) A continuació, fem la rotació LL al node H
L'arbre equilibrat resultant després de la rotació LL és:
6. Insereix K
En inserir K, BST es desequilibra ja que el factor d'equilibri de I és -2. Com que el BST està esbiaixat a la dreta de I a K, per tant realitzarem la rotació RR al node I.
L'arbre equilibrat resultant després de la rotació RR és:
7. Insereix L
En inserir l'arbre L encara està equilibrat, ja que el factor d'equilibri de cada node és ara -1, 0, +1. Per tant, l'arbre és un arbre AVL equilibrat
