dizionari

dizionari

alberi bilanciati

maggio 2002 ASD2002 - Alberi bilanciati 2

dizionari

ADT che supportano le seguenti operazionimembership

anche detta search insertdelete

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 bilanciamentotutti i rami di un albero hanno

approssimativamente la stessa lunghezza

ciascun nodo interno ha “molti” figli

caso ideale per un albero k-ariociascun 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 perfettoun 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 = # foglie ni = # nodi interni n = 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 AVLda Adel’son-Vel’skii & Landis, primi

proponenti


fattore di bilanciamento34

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


alberi AVL?


alberi di Fibonacci

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 AVL1. 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)

simmetrici a coppie una rotazione (semplice o doppia) è sempre

sufficiente


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)

gli antenati di P non sono interessati all’inserimento


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 )


cancellazione negli AVL1. cancellare nodo come in un BST “classico”2. ricalcolare i fattori di bilanciamento che

sono mutati in seguito alla cancellazionesolo 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 peggiorepiù costoso dell’inserimento


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 ramopasso 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 )


AVL e dizionari

gli AVL consentono di realizzare dizionari in cui le tre operazionimembership insertdelete

hanno costo O(lg n ) w.c.t.


cancellazione negli AVL/2

gli alberi AVL possono essere estesi consentendo per ogni nodo un FDB limitatose |FDB| 2 altezza 1.81lg n – 0.71se |FDB| 3 altezza 2.15lg n – 1.13


cancellazione negli AVL/esempio

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

Date post:	09-Jan-2016
Category:	Documents
Upload:	oriana
View:	38 times
Download:	1 times

dizionari

Documents