La supressió d'un node d'un arbre AVL és similar a la d'un arbre de cerca binari. La supressió pot alterar el factor d'equilibri d'un arbre AVL i, per tant, cal reequilibrar l'arbre per mantenir l'AVLness. Per a això, hem de fer rotacions. Els dos tipus de rotacions són la rotació L i la rotació R. Aquí, parlarem de les rotacions R. Les rotacions L en són les imatges miralls.
Si el node que s'ha de suprimir està present al subarbre esquerre del node crític, llavors s'ha d'aplicar la rotació L, sinó si el node que s'ha de suprimir està present al subarbre dret del node crític. , s'aplicarà la rotació R.
Considerem que, A és el node crític i B és el node arrel del seu subarbre esquerre. Si el node X, present al subarbre dret de A, s'ha de suprimir, hi pot haver tres situacions diferents:
Rotació R0 (el node B té un factor d'equilibri 0)
Si el node B té un factor d'equilibri 0 i el factor d'equilibri del node A s'ha alterat en eliminar el node X, llavors l'arbre es reequilibrarà fent girar l'arbre mitjançant la rotació R0.
El node crític A es mou a la seva dreta i el node B es converteix en l'arrel de l'arbre amb T1 com a subarbre esquerre. Els subarbres T2 i T3 es converteixen en el subarbre esquerre i dret del node A. el procés implicat en la rotació R0 es mostra a la imatge següent.
Exemple:
Suprimiu el node 30 de l'arbre AVL que es mostra a la imatge següent.
Solució
En aquest cas, el node B té un factor d'equilibri 0, per tant, l'arbre es girarà utilitzant la rotació R0 tal com es mostra a la imatge següent. El node B(10) es converteix en l'arrel, mentre que el node A es mou cap a la seva dreta. El fill dret del node B es convertirà ara en el fill esquerre del node A.
hiba bukhari
Rotació R1 (el node B té un factor d'equilibri 1)
La rotació R1 s'ha de realitzar si el factor d'equilibri del node B és 1. En la rotació R1, el node crític A es mou cap a la seva dreta tenint els subarbres T2 i T3 com a fill esquerre i dret respectivament. T1 s'ha de col·locar com el subarbre esquerre del node B.
El procés implicat en la rotació R1 es mostra a la imatge següent.
Exemple
Suprimiu el node 55 de l'arbre AVL que es mostra a la imatge següent.
Com obtenir emojis d'iPhone a Android
Solució :
L'eliminació de 55 de l'arbre AVL pertorba el factor d'equilibri del node 50, és a dir, el node A que es converteix en el node crític. Aquesta és la condició de rotació R1 en què el node A es mourà a la seva dreta (que es mostra a la imatge següent). La dreta de B es converteix ara en l'esquerra de A (és a dir, 45).
El procés implicat en la solució es mostra a la imatge següent.
Rotació R-1 (el node B té un factor d'equilibri -1)
La rotació R-1 s'ha de realitzar si el node B té un factor d'equilibri -1. Aquest cas es tracta de la mateixa manera que la rotació LR. En aquest cas, el node C, que és el fill dret del node B, es converteix en el node arrel de l'arbre amb B i A com els seus fills esquerre i dret respectivament.
Els subarbres T1, T2 es converteixen en els subarbres esquerre i dret de B mentre que, T3, T4 es converteixen en els subarbres esquerre i dret de A.
El procés implicat en la rotació R-1 es mostra a la imatge següent.
Exemple
Suprimiu el node 60 de l'arbre AVL que es mostra a la imatge següent.
Solució:
en aquest cas, el node B té un factor d'equilibri -1. L'eliminació del node 60 pertorba el factor d'equilibri del node 50, per tant, cal girar-lo R-1. El node C, és a dir, 45, es converteix en l'arrel de l'arbre amb el node B(40) i A(50) com a fill esquerre i dret.
