Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Algoritmi e Strutture Dati
Capitolo 6
Interrogazioni AVL
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Posso usare un albero AVL per
implementare un dizionario?
+1
15
+2 !
-2 -1!
6
0
2
18
0
-1
3
8
0
4
0
-1
0
7
-2 !
0
10
0
9
-1
0
17
0
20
0
-1
25
0
-1
13
14
come implemento Insert(14)?
…e delete(25)?
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Implementazione delle operazioni
• L’operazione search procede come in un BST
• Ma inserimenti e cancellazioni potrebbero
sbilanciare l’albero
• Manteniamo il bilanciamento tramite
opportune rotazioni
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Rotazione di base
• Mantiene la proprietà di ricerca
• Richiede tempo O(1)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ribilanciamento tramite rotazioni
• Le rotazioni sono effettuate su nodi sbilanciati
• Sia v un nodo con fattore di bilanciamento (v) ± 2
• Esiste un sottoalbero T di v che lo sbilancia
• A seconda della posizione di T si hanno 4 casi:
(v)=+2
(v)=-2
• I quattro casi sono simmetrici a coppie (SD (DS) andrebbe meglio
definito come segue: T è nel sottoalbero sinistro (destro) di v, ma non
è il sottoalbero sinistro (destro) del figlio sinistro (destro) di v)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Caso SS
• (v)=+2, l’altezza di T è h+3, e l’altezza di T1 è h+1
• Si applica una rotazione semplice verso destra su v; 2 sottocasi possibili:
(i) l’altezza di T2 è h  l’altezza dell’albero coinvolto nella rotazione passa da h+3
a h+2, e il fattore di bilanciamento di u e v diventa pari a 0
(ii) l’altezza di T2 è h+1 (NOTA: questo può essere visto anche come un caso SD)
 l’altezza dell’albero coinvolto nella rotazione rimane pari a h+3, e il fattore di
bilanciamento di u diventa pari a -1, mentre quello di v diventa pari a 1
0/-1
0/+1
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Osservazioni sul caso SS
• Aggiungendo una foglia a un albero bilanciato si
può verificare solo il caso (i) (perché altrimenti
l’AVL era già sbilanciato!)
• Invece, cancellando una foglia da un albero
bilanciato si possono verificare entrambi i casi
(ad esempio, se cancello una foglia da T3)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Caso SD
• (v)=+2, altezza di T è h+3, altezza di T(z) è h+2, altezza di T1 è h
 sottoalbero destro di z ha altezza h+1 e (z)=-1
• Due sottocasi: (1) altezza di T2 è h (e quindi l’altezza di T3 è h o
h-1); (2) altezza di T2 è h-1 (e quindi l’altezza di T3 è h)
• Applicare due rotazioni semplici: una verso sinistra sul figlio del
nodo critico (nodo z), l’altra verso destra sul nodo critico (nodo v)
• In entrambi i sottocasi, l’altezza dell’albero coinvolto nella
rotazione passa da h+3 a h+2
h+1
h+1
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
0/-1
…i due sottocasi del caso SD…
+1
0
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
insert(elem e, chiave k)
1. Crea un nuovo nodo u con elem=e e chiave=k
2. Inserisci u come in un BST
3. Ricalcola i fattori di bilanciamento dei nodi
nel cammino dalla radice a u: sia v il più
profondo nodo con fattore di bilanciamento
pari a ±2 (nodo critico)
4. Esegui una rotazione opportuna su v
Oss.: un solo ribilanciamento è sufficiente, poiché l’altezza
dell’albero coinvolto diminuisce di 1 (sottocaso 1 caso
SS o DD, o i due sottocasi dei casi SD o DS)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
insert (10,e)
+2 +1
15
-2
-1
6
0
2
18
-2
3
0
-1
0
4
-1
8
+1
+2
13
0
7
-1 0
-1
0
17
20
0
caso SD
25
9
0
10
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
insert (10,e)
+2 +1
15
-2
-1
6
0
2
18
-2
3
0
-1
0
4
-1
0
17
8
+1
+2
13
0
7
-1 0
-1
20
0
25
10
0
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
insert (10,e)
+2 +1
15
-2
-1
6
0
2
18
-2
3
0
-1
0
4
-1
8
0
7
-1
0
9
-1
0
17
20
0
0
10
25
+1
0 +2
13
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
delete(elem e)
1. Cancella il nodo come in un BST
2. Ricalcola i fattori di bilanciamento dei nodi
nel cammino dalla radice al padre del nodo
eliminato fisicamente (che potrebbe essere il
predecessore del nodo contenente e)
3. Ripercorrendo il cammino dal basso verso
l’alto, esegui l’opportuna rotazione semplice o
doppia sui nodi sbilanciati
Oss.: potrebbero essere necessarie O(log n) rotazioni:
infatti eventuali diminuzioni di altezza indotte dalle
rotazioni fanno permanere lo sbilanciamento
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
delete (18)
+1 +2
15
caso SD
-1 0
-1
6
0
2
18
20
0
-1
3
8
0
4
-1
0
17
+1
13
0
7
20
0
successore di 18
25
0
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
delete (18)
+1 +2
15
+1
-1 0
8
20
+1
+1
13
6
0
7
0
3
0
2
0
17
0
0
9
25
0
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
delete (18)
0
8
+1
0
6
15
0
7
0
3
0
2
0
4
+1
13
0
9
0
20
0
17
0
25
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Cancellazione con rotazioni a cascata
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Classe AlberoAVL
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Costo delle operazioni
• Tutte le operazioni hanno costo O(log n)
poiché l’altezza dell’albero è O(log n) e
ciascuna rotazione richiede solo tempo
costante
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Riepilogo
• Mantenere il bilanciamento è risultato cruciale
per ottenere buone prestazioni
• Esistono vari approcci per mantenere il
bilanciamento:
– Tramite rotazioni
– Tramite fusioni o separazioni di nodi (alberi 2-3, Balberi )
• In tutti questi casi si ottengono tempi di
esecuzione logaritmici nel caso peggiore
Copyright © 2004 - The McGraw - Hill Companies, srl