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
Riepilogo: alberi AVL
•
•
•
Un albero AVL è un BST in cui ad ogni nodo la differenza tra
l’altezza del sottoalbero sinistro e l’altezza del sottoalbero
destro (detta fattore di bilanciamento) è al più pari ad 1 in
valore assoluto (si osservi che la definizione non specifica
come tale proprietà debba essere garantita e mantenuta nel
caso in cui che il BST sia soggetto ad inserimenti e
cancellazioni)
Abbiamo dimostrato che un AVL con n nodi ha altezza
h=Θ(log n), e che lo sbilanciamento di un nodo può essere
corretto attraverso alcune operazioni di rotazione
 Oggi vedremo che la insert e la delete danno luogo a
sbilanciamenti correggibili in O(log n) rotazioni
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Riepilogo ribilanciamenti
Tipo
Altezza dopo la/le
rotazione/i
Causa
SS (i)
Diminuisce di 1
Inserimento/Cancellazione
SS (ii)
Rimane la stessa
Cancellazione
SD
Diminuisce di 1
Inserimento/Cancellazione
Ovviamente i casi DD e DS sono simmetrici
3
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 nodo più profondo
con fattore di bilanciamento pari a ±2 (nodo critico)
4. Esegui una rotazione opportuna su v
Oss.: un solo ribilanciamento è sufficiente, poiché l’altezza del
sottoalbero coinvolto nella/e rotazione/i diminuisce di 1 (sottocaso
(i) del caso SS o DD, o casi SD o DS), e quindi torna ad essere
uguale all’altezza che aveva prima dell’inserimento, ribilanciando
così automaticamente tutti i nodi eventualmente sbilanciati nel
cammino verso la radice
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio: 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
Esempio: 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
Esempio: 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.
2.
Cancella il nodo come in un BST
Ricalcola il fattore di bilanciamento del padre del nodo eliminato fisicamente
(che potrebbe essere diverso dal nodo contenente e), ed esegui l’opportuna
rotazione semplice o doppia ove necessario
Ripeti questo passo, sino ad arrivare eventualmente alla radice dell’AVL:
3.
–
Se l’altezza del sottoalbero appena ribilanciato è uguale a quella che aveva prima
della cancellazione, termina. Invece, se tale altezza è diminuita, risali verso l’alto
(cioè vai nel padre del sottoalbero appena ribilanciato), calcola il fattore di
bilanciamento, e applica l’opportuno ribilanciamento.
Oss.: potrebbero essere necessarie O(log n) rotazioni: infatti
eventuali diminuzioni di altezza indotte dalle rotazioni
(sottocaso (i) del caso SS o DD, o casi SD o DS) possono
propagare lo sbilanciamento verso l’alto nell’albero (l’altezza
del sottoalbero in cui è avvenuto il ribilanciamento diminuisce
di 1 rispetto a quella che aveva prima della cancellazione)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esempio: delete (18)
+1
15
-1 -2
-1
6
0
2
18
17
0
-1
3
8
0
4
0
17
+1
13
0
7
caso DD (i)
Calcolo il fattore
di bilanciamento
-1
20
0
Predecessore di 18
25
Rotazione a sinistra
0
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ribilanciamento DD e aggiornamento del fattore di
bilanciamento del padre del sottoalbero ruotato
+1 +2
15
caso SD (rotazione a cascata!)
0
-1
6
0
2
20
0
-1
3
8
0
4
0
17
0
25
+1
13
0
7
0
9
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ribilanciamento SD
+1 +2
15
+1
0
8
20
+1
+1
13
6
0
7
0
3
0
2
0
17
0
25
0
9
0
4
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Albero ribilanciato
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
Classe AlberoAVL
• 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 (alberi AVL)
– 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