Dizionari alberi bilanciati. maggio 2002ASD2002 - Alberi bilanciati2 dizionari ADT che supportano le...

dizionari

alberi bilanciati

maggio 2002 ASD2002 - Alberi bilanciati 2

dizionari

ADT che supportano le seguenti operazioni membership

anche detta search insert delete

o remove

le liste e i BST sono dizionari


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?

alberi bilanciati tavole hash


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à


-1 foglia+ 1 nodo interno

+2 foglie

bilanciamento perfetto

un albero binario perfettamente bilanciato di n nodi ha altezza

34

21 63

6 18 28 32

16 30

37 52

43 72 1lg2 n

se ogni nodo ha 0 o 2 figli nf = ni +1

nf = # foglieni = # nodi internin = nf + ni

le foglie sono circa il 50% dei nodi


bilanciamento perfetto/2

facilmente generalizzabile ad alberi di arità k

costo di ricerca/inserimento/eliminazione O(log n)

ripetuti inserimenti/eliminazioni possono distruggere il bilanciamento degrado delle prestazioni

knk

nnkn1)1(

1)1( fif


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


fattore di bilanciamento

34

21 63

6 18 28

16 30

37 52

43 72

3 29 57

7832

0

-1

+1

fattore di bilanciamento (FDB):altezza sottoalbero dx – altezza sottoalbero sx

in un albero bilanciato in altezza |FDB| 1, per ogni nodo

28


alberi AVL?


alberi di Fibonacci

alberi AVL col minimo numero di nodi (fissata l’altezza)

1 24

7

12

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


alberi di Fibonacci/2

AVLi AVLi +1

AVLi +2

alberi di Fibonaccialberi bilanciati di altezza i col minimo numero di nodi

RelazioniAVLi +2 = AVLi + AVLi +1 + 1Fi +2 = Fi + Fi +1

AVLi = Fi +2 – 1


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)


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”


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)


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


rotazione doppia (caso SD)

h

h h

+1

0

P

Q

h

h+1h

+2

-1

P

Q

h

h-1

h

+2

-1

P

Q

+1

h

Q

h h

0

h h-1

-1

0 R

P

h h

h

h-1

+2

+2

P

R

0 Q

gli antenati di P non sono interessati all’inserimento


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;

}}


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 …


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 nothingt.height=max(height(t.left),height(t.right))+1;

return t;}

restituisce la nuova radice


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;

}


rotazione doppia (SD)

AvlNode doubleWithRightChild(AvlNode k1){k1.right=rotateWithLeftChild(k1.right);return rotateWithRightChild(k1);

}


inserimento negli AVL/costo

passo 1: proporzionale all’altezza dell’albero (lg n)


passo 3: O(lg n)

in totale: (lg n)


cancellazione negli AVL

1. cancellare nodo come in un BST “classico”

2. 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


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)


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


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


cancellazione negli AVL/costo

nel caso peggiore occorre effettuare rotazioni (semplici o doppie) lungo tutto il ramo



passo 3: (lg n) · (1)

in totale: (lg n)


cancellazione negli AVL/esempio

animazione tratta dal sito Web http://www.seanet.com/users/arsen/avltree.html

Dizionari alberi bilanciati. maggio 2002ASD2002 - Alberi bilanciati2 dizionari ADT che supportano le...

Documents

Transcript of Dizionari alberi bilanciati. maggio 2002ASD2002 - Alberi bilanciati2 dizionari ADT che supportano le...