L'eliminazione di un nodo da un albero AVL è simile a quella in un albero di ricerca binario. La cancellazione può disturbare il fattore di equilibrio di un albero AVL e pertanto l'albero deve essere ribilanciato per mantenere l'AVLness. A questo scopo è necessario eseguire delle rotazioni. I due tipi di rotazioni sono la rotazione L e la rotazione R. Qui discuteremo delle rotazioni R. Le rotazioni L sono le loro immagini speculari.
Se il nodo da eliminare è presente nel sottoalbero sinistro del nodo critico, allora è necessario applicare la rotazione L altrimenti se il nodo da eliminare è presente nel sottoalbero destro del nodo critico , verrà applicata la rotazione R.
Consideriamo che A sia il nodo critico e B sia il nodo radice del suo sottoalbero sinistro. Se si vuole eliminare il nodo X, presente nel sottoalbero destro di A, si possono verificare tre diverse situazioni:
Rotazione R0 (il nodo B ha fattore di bilanciamento 0)
Se il nodo B ha un fattore di bilanciamento pari a 0 e il fattore di bilanciamento del nodo A viene disturbato dopo l'eliminazione del nodo X, l'albero verrà ribilanciato ruotando l'albero utilizzando la rotazione R0.
Il nodo critico A viene spostato alla sua destra e il nodo B diventa la radice dell'albero con T1 come sottoalbero sinistro. I sottoalberi T2 e T3 diventano i sottoalberi sinistro e destro del nodo A. il processo coinvolto nella rotazione R0 è mostrato nell'immagine seguente.
Esempio:
Elimina il nodo 30 dall'albero AVL mostrato nell'immagine seguente.
Soluzione
In questo caso il nodo B ha fattore di equilibrio 0, pertanto l'albero verrà ruotato utilizzando la rotazione R0 come mostrato nell'immagine seguente. Il nodo B(10) diventa la radice, mentre il nodo A viene spostato alla sua destra. Il figlio destro del nodo B diventerà ora il figlio sinistro del nodo A.
stringa di array in c
Rotazione R1 (il nodo B ha il fattore di equilibrio 1)
La rotazione R1 deve essere eseguita se il fattore di equilibrio del nodo B è 1. Nella rotazione R1, il nodo critico A viene spostato alla sua destra avendo i sottoalberi T2 e T3 rispettivamente come figlio sinistro e destro. T1 deve essere posizionato come sottoalbero sinistro del nodo B.
Il processo coinvolto nella rotazione R1 è mostrato nell'immagine seguente.
Esempio
Elimina il nodo 55 dall'albero AVL mostrato nell'immagine seguente.
pronunciare un comando
Soluzione:
L'eliminazione di 55 dall'albero AVL disturba il fattore di equilibrio del nodo 50, ovvero il nodo A, che diventa il nodo critico. Questa è la condizione di rotazione di R1 in cui il nodo A verrà spostato alla sua destra (mostrato nell'immagine sotto). La destra di B diventa ora la sinistra di A (cioè 45).
Il processo coinvolto nella soluzione è mostrato nell'immagine seguente.
Rotazione R-1 (il nodo B ha un fattore di equilibrio -1)
La rotazione R-1 deve essere eseguita se il nodo B ha fattore di equilibrio -1. Questo caso viene trattato allo stesso modo della rotazione LR. In questo caso, il nodo C, che è il figlio destro del nodo B, diventa il nodo radice dell'albero con B e A rispettivamente come figli sinistro e destro.
I sottoalberi T1, T2 diventano i sottoalberi sinistro e destro di B mentre, T3, T4 diventano i sottoalberi sinistro e destro di A.
Il processo coinvolto nella rotazione R-1 è mostrato nell'immagine seguente.
Esempio
Elimina il nodo 60 dall'albero AVL mostrato nell'immagine seguente.
Soluzione:
in questo caso il nodo B ha fattore di equilibrio -1. L'eliminazione del nodo 60 disturba il fattore di equilibrio del nodo 50 pertanto è necessario ruotarlo R-1. Il nodo C cioè 45 diventa la radice dell'albero con il nodo B(40) e A(50) come figlio sinistro e destro.
