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 ABR 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 l’ABR 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 ABR
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 l’opportuna rotazione semplice o doppia su v
Oss.: un solo ribilanciamento è sufficiente, poiché l’altezza del
sottoalbero radicato nel nodo critico 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
ricalcolo dei fattori di
bilanciamento
-1
0
17
20
0
nodo critico
(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
0
9
10
-1
20
0
25
rotazione verso sinistra sul
figlio sinistro del nodo critico
(ovvero il nodo 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
-1
3
2
4
-1
18
-2
0
+1
6
0
0
+2 +1
15
-1
-1
0
17
8
0
7
-1
0
10
0
9
rotazione verso destra sul
nodo critico (ovvero il nodo
13)
-1
20
0
0
25
+2
+1
0
13
ricalcolo dei fattori di
bilanciamento
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 ABR
Ricalcola il fattore di bilanciamento del padre del nodo eliminato fisicamente
(che potrebbe essere quello contenente il predecessore di e, se e ha due figli), ed
esegui l’opportuna rotazione semplice o doppia ove necessario
3.
Se è stato fatto un ribilanciamento, ripeti questo passo, sino ad arrivare
eventualmente alla radice dell’AVL:
–
Se l’altezza del sottoalbero appena ribilanciato è uguale a quella che aveva
prima della cancellazione (sottocaso (ii) del caso SS o DD), 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 ove necessario (se no, esci).
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
radicato nel nodo critico 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