dizionari
alberi bilanciati
dizionari

ADT che supportano le seguenti
operazioni

membership



insert
delete


anche detta search
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
nf = # foglie
ni = # nodi interni
n = nf + ni
-1 foglia
+ 1 nodo interno
le foglie sono circa il 50%
dei nodi
+2 foglie
maggio 2002
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
63
16
6
3
30
43
72
18 28 32 37 52
29
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

alberi AVL col minimo numero di nodi
(fissata l’altezza)
h
Fh
AVLh
1
2
4
7
12
maggio 2002
ASD2002 - Alberi bilanciati
0
0
0
1
1
1
2
1
2
3
2
4
4
3
7
5
5
12
6
8
20
7
13
33
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)
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)
P
P
P
P
+1
+2
+2
+2
Q
Q
0
Q
-1
h
R
-1
h
+2
h
h
+1
h
h
0
h
h
h+1
0
P
h
h-1
R
-1
0
h-1
maggio 2002
h
Q
h

h
Q
h-1
h
h
gli antenati di P non sono
interessati all’inserimento
ASD2002 - Alberi bilanciati
16
rappresentazione nodo
class AvlNode {
Comparable element;
AvlNode
left;
AvlNode
right;
int
height;
AvlNode(Comparable el) {
this(el, null, null);
}
AvlNode(Comparable el, AvlNode lt,AvlNode rt) {
element = el;
left
= lt;
right
= rt;
height
= 0;
}
}
maggio 2002
ASD2002 - Alberi bilanciati
17
algoritmo inserimento /1
AvlNode insert(Comparable x, AvlNode t) {
if(t == null) t = new AvlNode(x, null, null);
else if(x.compareTo(t.element) < 0) {
t.left = insert(x, t.left);
if(height(t.left) - height(t.right) == 2)
if(x.compareTo(t.left.element) < 0)
t = rotateWithLeftChild(t); // SS
else t = doubleWithLeftChild(t); // DS
} else …
maggio 2002
ASD2002 - Alberi bilanciati
18
algoritmo inserimento /2
… else if(x.compareTo(t.element) > 0) {
t.right = insert(x, t.right);
if(height(t.right) - height(t.left) == 2)
if(x.compareTo(t.right.element) > 0)
t = rotateWithRightChild(t); // DD
else t = doubleWithRightChild(t); // SD
} else ; // Duplicate; do nothing
t.height=max(height(t.left),height(t.right))+1;
return t;
}
restituisce la nuova radice
maggio 2002
ASD2002 - Alberi bilanciati
19
rotazione semplice (SS)
AvlNode rotateWithLeftChild(AvlNode k2) {
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max(height(k2.left),
height(k2.right)) + 1;
k1.height = max(height(k1.left),
k2.height ) + 1;
return k1;
}
maggio 2002
ASD2002 - Alberi bilanciati
20
rotazione doppia (SD)
AvlNode doubleWithRightChild(AvlNode k1){
k1.right=rotateWithLeftChild(k1.right);
return rotateWithRightChild(k1);
}
maggio 2002
ASD2002 - Alberi bilanciati
21
inserimento negli AVL/costo



passo 1: proporzionale all’altezza
dell’albero (lg n)
passo 2: proporzionale all’altezza
dell’albero (lg n)
passo 3: O(lg n)
in totale: (lg n)
maggio 2002
ASD2002 - Alberi bilanciati
22
cancellazione negli AVL
1.
2.
cancellare nodo come in un BST “classico”
ricalcolare i fattori di bilanciamento che
sono mutati in seguito alla cancellazione
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
maggio 2002
ASD2002 - Alberi bilanciati
23
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
24
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
25
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
26
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
27
cancellazione negli
AVL/esempio
animazione tratta dal sito Web
http://www.seanet.com/users/arsen/avltree.html
maggio 2002
ASD2002 - Alberi bilanciati
28