dizionari
alberi bilanciati
dizionari
ADT che supportano le seguenti
operazioni

membership

anche detta search
insert
 delete


o remove
le liste e i BST sono dizionari
maggio 2002
ASD2002 - Alberi bilanciati
2
dizionari/2
tutte le implementazioni finora considerate
hanno almeno un’operazione di costo lineare
w.c.t. (worst case time, tempo nel caso
peggiore)
in molti casi un costo lineare è giudicato
inaccettabile

strutture più efficienti?


maggio 2002
alberi bilanciati
tavole hash
ASD2002 - Alberi bilanciati
3
introduzione al bilanciamento
nozione intuitiva di bilanciamento
tutti i rami di un albero hanno
approssimativamente la stessa lunghezza
 ciascun nodo interno ha “molti” figli

caso ideale per un albero k-ario
ciascun nodo ha 0 o k figli
 la lunghezza di due rami qualsiasi
differisce di al più una unità

maggio 2002
ASD2002 - Alberi bilanciati
4
bilanciamento perfetto
34
21
16
6
63
30
43
72
18 28 32 37 52
un albero binario
perfettamente
bilanciato di n nodi ha
altezza lg2 n   1
se ogni nodo ha 0 o 2
figli nf = ni +1



-1 foglia
+ 1 nodo interno
+2 foglie
maggio 2002
nf = # foglie
ni = # nodi interni
n = nf + ni
le foglie sono circa il
50% dei nodi
ASD2002 - Alberi bilanciati
5
bilanciamento perfetto/2
facilmente generalizzabile ad alberi di arità k

nf  (k  1)ni  1
(k  1)n  1
 nf 
k
costo di ricerca/inserimento/eliminazione
O(log n)
ripetuti inserimenti/eliminazioni possono
distruggere il bilanciamento

degrado delle prestazioni
maggio 2002
ASD2002 - Alberi bilanciati
6
bilanciamento in altezza
un albero è bilanciato in altezza se le
altezze dei sottoalberi sinistro e
destro di ogni nodo differiscono di al
più un’unità
gli alberi bilanciati in altezza sono
detti alberi AVL

da Adel’son-Vel’skii & Landis, primi
proponenti
maggio 2002
ASD2002 - Alberi bilanciati
7
fattore di bilanciamento
34
21
16
6
63
30
43
18 28 32 37 52
3
29
72
fattore di bilanciamento
(FDB):
altezza sottoalbero dx –
altezza sottoalbero sx
78
57
+1
-1
0
in un albero bilanciato in altezza
|FDB|  1, per ogni nodo
maggio 2002
ASD2002 - Alberi bilanciati
8
alberi AVL?
maggio 2002
ASD2002 - Alberi bilanciati
9
alberi di Fibonacci
1
2
4
7
12
maggio 2002
h
Fh
AVLh
0
0
0
1
1
1
2
1
2
3
2
4
4
3
7
5
5
12
6
8
20
7
13
33
ASD2002 - Alberi bilanciati
10
alberi di Fibonacci/2
alberi di Fibonacci
alberi bilanciati di
altezza i col minimo
numero di nodi
AVLi +2
AVLi
maggio 2002
AVLi +1
Relazioni
AVLi +2 = AVLi + AVLi +1 + 1
Fi +2 = Fi + Fi +1
AVLi = Fi +2 – 1
ASD2002 - Alberi bilanciati
11
alberi di Fibonacci/3
un albero di Fibonacci ha tutti i fattori di
bilanciamento dei nodi interni pari a ± 1

è l’albero bilanciato più vicino alla condizione di
non bilanciamento
un albero di Fibonacci con n nodi ha altezza
< 1.44 lg(n +2) – 0.328

dimostrato da Adel’son-Vel’skii & Landis

 un AVL di n nodi ha altezza (lg n )
maggio 2002
ASD2002 - Alberi bilanciati
12
inserimento in AVL
1. inserire nuovo nodo come in un BST
“classico”
il nuovo nodo diviene una foglia
2. ricalcolare i fattori di bilanciamento che
sono mutati in seguito all’inserimento
solo nel ramo interessato all’inserimento (gli
altri fattori non possono mutare), dal basso
verso l’alto
3. se nel ramo appare un fattore di
bilanciamento pari a ±2 occorre ribilanciare
tramite “rotazioni”
maggio 2002
ASD2002 - Alberi bilanciati
13
rotazioni negli AVL
casi possibili




DD: inserimento nel sottoalbero destro di un
figlio destro (del nodo che si sbilancia)
SD: inserimento nel sottoalbero sinistro di un
figlio destro (del nodo che si sbilancia)
DS: inserimento nel sottoalbero destro di un
figlio sinistro (del nodo che si sbilancia)
SS: inserimento nel sottoalbero sinistro di un
figlio sinistro (del nodo che si sbilancia)
simmetrici a coppie

una rotazione (semplice o doppia) è sempre
sufficiente
maggio 2002
ASD2002 - Alberi bilanciati
14
rotazione semplice (caso DD)
gli antenati di P non sono interessati
all’inserimento perché in seguito alla
rotazione recuperano il loro fattore di
bilanciamento precedente
maggio 2002
ASD2002 - Alberi bilanciati
15
rotazione doppia (caso SD)
gli antenati di P non sono interessati
all’inserimento
maggio 2002
ASD2002 - Alberi bilanciati
16
inserimento negli AVL/costo
passo 1: proporzionale all’altezza
dell’albero (lg n )
passo 2: proporzionale all’altezza
dell’albero (lg n )
passo 3: (1)
in totale: (lg n )
maggio 2002
ASD2002 - Alberi bilanciati
17
cancellazione negli AVL
cancellare nodo come in un BST “classico”
2. ricalcolare i fattori di bilanciamento che
sono mutati in seguito alla cancellazione
1.
solo nel ramo interessato all’inserimento (gli
altri fattori non possono mutare), dal basso
verso l’alto
3.
per ogni nodo con fattore di
bilanciamento pari a ±2 occorre operare
una rotazione semplice o doppia
O(lg n ) rotazioni nel caso peggiore
più costoso dell’inserimento
maggio 2002
ASD2002 - Alberi bilanciati
18
rotazione semplice
eliminazione foglia da sottoalbero sinistro
di P


il figlio destro ha FDB +1; a), b) e c)
il figlio destro ha FDB 0; d), e) ed f)
maggio 2002
ASD2002 - Alberi bilanciati
19
rotazione doppia
eliminazione foglia da sottoalbero sinistro di
P


FDB(Q) = –1 e FDB(R)= –1; g), h) ed i)
rotazione R-Q (P resta a +2, R e Q vanno a +1) e
rotazione P-R
maggio 2002
ASD2002 - Alberi bilanciati
20
rotazione doppia/2
eliminazione foglia da sottoalbero sinistro
di P

FDB(Q) = -1, FDB(R)=+1, j), k) ed l)
rotazione R-Q (P resta a +2, R va a +2 e Q
va a 0) e rotazione P-R
maggio 2002
ASD2002 - Alberi bilanciati
21
cancellazione negli AVL/costo
nel caso peggiore occorre effettuare
rotazioni (semplici o doppie) lungo tutto il
ramo
passo 1: proporzionale all’altezza dell’albero
(lg n )
passo 2: proporzionale all’altezza
dell’albero (lg n )
passo 3: (lg n ) · (1)
in totale: (lg n )
maggio 2002
ASD2002 - Alberi bilanciati
22
AVL e dizionari
gli AVL consentono di realizzare
dizionari in cui le tre operazioni
membership
 insert
 delete

hanno costo O(lg n ) w.c.t.
maggio 2002
ASD2002 - Alberi bilanciati
23
cancellazione negli AVL/2
gli alberi AVL possono essere estesi
consentendo per ogni nodo un FDB
limitato
se |FDB|  2  altezza  1.81lg n – 0.71
se |FDB|  3  altezza  2.15lg n – 1.13
maggio 2002
ASD2002 - Alberi bilanciati
24
cancellazione negli
AVL/esempio
animazione tratta dal sito Web
http://www.seanet.com/users/
arsen/avltree.html
maggio 2002
ASD2002 - Alberi bilanciati
25