Introduzione
Durante l’inserimento di nuovi elementi in un albero AVL è probabile che il nuovo elemento assuma una posizione che faccia perdere la sua proprietà di 1-bilanciamento.
Per far fronte a questo problema si ricorre alle operazioni di rotazione, ovvero delle operazioni che riorganizzano una determinata porzione dell’albero, effettuando degli scambi di puntatori.
L’algoritmo d’inserimento (introdotto nell’ultima sezione dell’articolo sugli AVL), dopo aver inserito il nodo, va a varificare che l’albero sia bilanciato, in caso negativo dovrà andare a cercare il nodo critico, ovvero il nodo radice da cui parte il sottoalbero che genera lo sbilanciamento. Vediamo adesso come avvengono queste operazioni.
Tipi di rotazioni
A seconda del tipo di sbilanciamento che presenta l’albero, algoritmo di inserimento dovrà effettuare una specifica rotazione.
Esistono due tipologie di rotazioni, rotazione orarie (clockwise) e antiorarie (counterclockwise).
Queste operazioni richiedono tutte tempo costante.
Nella rotazione oraria, una volta individuato il nodo critico (z), esso diventa il figlio destro del suo figlio sinistro (v), quindi tale figlio diventa la nuova radice, poi si assegna al figlio sinistro di z il figlio destro di v.
La rotazione antioraria, invece è l’esatto contrario.
Vediamo adesso gli pseudocodici e disegni che dovrebbero chiarire le idee.
Rotazione Oraria:
ClockwiseRotation(z):
v = z.sx;
z.sx = v.dx;
v.dx = z;
z.height = max( Heigth(z.sx), Heigth(z.dx) ) + 1;
v.height = max( Heigth(v.sx), Heigth(v.dx) ) + 1;
return v;Rotazione Antioraria:
CounterclockwiseRotation(v):
z = v.dx;
v.dx = z.sx;
z.sx = v;
z.height = max( Heigth(z.sx), Heigth(z.dx) ) + 1;
v.height = max( Heigth(v.sx), Heigth(v.dx) ) + 1;
return z;I 4 casi di sbilanciamento e inserimento
Durante l’inserimento possiamo incontrare quattro casi differenti di sbilanciamento, a seconda del caso dobbiamo effettuare una o due specifiche rotazioni.
Caso Sinistra-Sinistra (SS): la foglia f appartiene al sottoalbero α radicato in u.sx.sx cioè al sottoalbero sinistra del figlio sinistro del nodo critico. Si effettua una rotazione oraria su u.
Caso Destra-Destra (DD): la foglia f appartiene al sottoalbero γ radicato in u.dx.dx, cioè al sottoalbero destro del figlio destro del nodo critivo. Si effettua la rotazione antioraria su u.
Caso Sinistra-Destra (SD): la foglia f appartiene al sottoalbero β radicato in u.sx.dx, cioè al sottoalbero destro del figlio sinistro del nodo critico. Si effettuano due rotazioni, oraria su u e antioraria su u.sx.
Caso Destra-Sinistra (DS): la foglia f appartiene al sottoalbero β radicato in u.dx.sx, cioè al sottoalbero sinistro del filgio desto del nodo critico. Si effetuano due rotazioni, oraria su u.dx e antioraria su u.
