Università degli Studi di Catania Università degli Studi di Catania Facoltà di Scienze Matematiche FF.NN.Facoltà di Scienze Matematiche FF.NN.
Corso di Laurea in InformaticaCorso di Laurea in Informatica
1° Prova in itinere di Algoritmi e complessità
Fast Updating of Well-Balanced Fast Updating of Well-Balanced
Trees Trees
Daniele Contarino
Executive summary Executive summary
●Introduzione agli alberi ben bilanciati;
●Manutenzione di un albero;
● Manutenzione di un albero quasi perfettamente bilanciato
● Manutenzione di un albero perfettamente bilanciato (con solo inserimenti o cancellazioni)
●Alberi densi
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
Cosa intendiamo per “bilanciamento”?
Intuitivamente, possiamo pensare che in un dato albero, tutti i suoi livelli siano completi, lasciando al massimo l'ultimo incompleto.
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
A
lbero bilanciato Albero NON bilanciatoPassando dall'intuizione ai concetti, possiamo dare la seguente
Definizione 1
“Un albero binario ha un'altezza ottimale se e solo se l'altezza dell'albero è ”
dove con intendiamo il numero di nodi dell’albero.
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
⌈log (n+1)⌉
n
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
h = 4
⌈log(n+1)⌉=⌈log(14+1)⌉=⌈3,906⌉=4 Esempio 1
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
h = 4
⌈log(n+1)⌉=⌈log(12+1)⌉=⌈3,700⌉=4 Esempio 2
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
Sicuri che l'albero dell'Esempio 2 sia bilanciato?
Livelli completi
Livelli incompleti Se osserviamo bene, vediamo che quest'albero non rispetta la nostra intuizione iniziale. Il solo concetto di altezza ottimale non basta!
Occore dare un'altra definizione!
La nostra idea era quella di lasciare al più un livello incompleto.
Per marcare questo concetto diamo la seguente
Definizione 2
“Un albero binario si dice perfettamente bilanciato se e solo se la differenza tra l'altezza del percorso più lungo e del più corto è al più uguale a 1”
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
Alberi ben bilanciati - Intro Alberi ben bilanciati - Intro
H = 4
Esempio 2
h = 2
H-h = 2
L'albero non è bilanciato!
Se un albero è ben bilanciato, i tempi delle operazioni
principali (inserimento, ricerca e cancellazione) saranno .
Però i continui inserimenti e cancellazioni posso far
sbilanciare l'albero.
O (log n)
Alberi ben bilanciati – L'idea Alberi ben bilanciati – L'idea
Esistono già algoritmi che permettono l'aggiornamento con un costo ammortizzato . Noi cercheremo di
portare questo costo a , mantenendo per la ricerca.
Θ(n) O (log2n) O (log n)
Alberi quasi ottimamente bilanciati Alberi quasi ottimamente bilanciati
Permettiamo al nostro albero di possedere una altezza quasi ottimale, ovvero fissato un certo , l'altezza massima consentita all'albero sarà ϵ>0
⌈log(n+1)+ϵ⌉
⌈log(n+1)+ϵ⌉
Alberi quasi ottimamente bilanciati Alberi quasi ottimamente bilanciati
Inoltre, permettiamo al nostro albero di avere la lunghezza del path più corto di .
Questo permette di una certa flessibilità nella differenza tra il path più lungo e quello più corto.
⌊log(n+1)−ϵ⌋
⌊log(n+1)−ϵ⌋
Alberi quasi ottimamente bilanciati Alberi quasi ottimamente bilanciati
Combinando l'altezza quasi ottimale e il percorso
minimo vicino al massimo, otteniamo un costo per ogni aggiornamento pari a O
(
logϵ2n)
Abbiamo detto che un albero tende a sbilanciarsi a causa dei continui inserimenti o cancellazioni.
Ma se il nostro albero non necessità eliminazioni, è possibile ottenere un albero perfettamente bilanciato con costo di ristrutturazione di .
Identico costo si ha anche nel caso di un albero in cui vengono effettuate solo delle eliminazioni
Alberi ottimamente bilanciati Alberi ottimamente bilanciati
O
(
log3n)
Abbiamo detto che un albero tende a sbilanciarsi a causa dei continui inserimenti o cancellazioni.
Ma se il nostro albero non necessità eliminazioni, è possibile ottenere un albero perfettamente bilanciato con costo di ristrutturazione di .
Identico costo si ha anche nel caso di un albero in cui vengono effettuate solo delle eliminazioni.
Alberi ottimamente bilanciati Alberi ottimamente bilanciati
O
(
log3n)
L'idea di fondo è quella di effettuare la ricostruzione parziale solo dove serve (ovvero nel sotto albero che fà sforare l'altezza ottimale consentita)
Alberi ottimamente bilanciati Alberi ottimamente bilanciati
Alberi Densi Alberi Densi
Nonostante gli sforzi fatti, il costo minimo per ogni aggiornamento (anche con alcune limitazioni) è di . Siamo ancora lontani da un tempo
logaritmico.
Quindi ora introduciamo una nuova idea: Gli alberi densi.
O
(
logϵ2n)
Alberi Densi Alberi Densi
Nei alberi densi vi troviamo 2 entità:
● L'albero superiore
● Le foglie – sotto alberi
Alberi Densi Alberi Densi
L'idea di fondo è quella di lavorare con delle
ristrutturazioni parziali o nelle foglie-sotto alberi (che vengono trattati come alberi) oppure nell'albero
superiore (e gli alberi sottostanti vengono considerati come foglie, quindi non vengono toccati)
Alberi Densi Alberi Densi
Il vantaggio dei alberi densi è che la maggior parte delle operazioni interesseranno solo le foglie-sotto alberi. Un albero superiore sarà soggetto a ricostruzione solo se una foglia-sotto albero sarà divisa in 2 sotto-alberi o si procederà a un merge di 2 sotto-alberi.
Il costo ammortizzato per l'aggiornamento è di con .
Nel caso di aggiornamenti per l'albero superiore, il costo si avvicina a .
O
(
log nϵ2)
0<ϵ<1 2
Θ
(
log n)
Alberi Densi Alberi Densi
Dove sta l'inghippo?
Per ottenere un albero denso, dobbiamo permettere all'albero di poter tenere fino a 4 livelli incompleti.
Conclusioni Conclusioni
Grazie a queste considerazioni, siamo riusciti a
mantenere un albero binario di ricerca ben bilanciato passando da tempo a , rendendo più
attraente questa struttura dati.
O
(
log n)
Θ
(
n)
Reference Reference
Fast Updating of Well Balanced Trees
A Andersson, T Lai - SWAT 90, 1990 – Springer Alberi bilanciati
F. d'Amore - Università di Roma "La Sapienza", 2002
