Analisi Ammortizzata

sempre quello mbare

Splay Tree

Si definisca la struttura dati BTree
(Completo) Si definisca in maniera precisa la struttura dati B-tree e se ne illustri sinteticamente un’applicazione.
Si determini il numero massimo e minimo di nodi che può essere contenuto in un B-Tree di altezza h e grado minimo
- numero minimo nodi:
- numero Massimo nodi:
- numero minimo chiavi con grado minimo t:
- numero Massimo chiavi con grado minimo:
Fornire CON DIMOSTRAZIONE il limite superiore per l’altezza di un B-Tree di grado minimo con chiavi
Sia un B-tree con chiavi, il cui grado minimo è il medesimo di quello in figura. Qual è la massima altezza possibile per ?
Si determinino una minorazione e una maggiorazione del numero di nodi a profondità in un B-Tree di grado minimo e altezza (fai tabella)
Si effettui l’inserimento delle chiavi (nell’ordine dato) in un B-tree di grado minimo 2, inizialmente vuoto, e quindi si cancellino le chiavi .

Definire e fornire una maggiorazione al grado massimo di un nodo in uno heap binomiale contenente nodi Heap Binomiali
Fornire un esempio di Heap Binomiale che contiene 8 chiavi e effettuare l’operazione di Extract-Min
e descrivi DecreaseKey, ExtractMin, Delete, e Insert (Ed esegui esercizio)
Determinare un limite superiore e un limite inferiore per il numero di alberi binomiali in un heap binomiale con chiavi.
Nel caso degli heap binomiali, è richiesto che gli alberi binomiali nella lista delle radici siano ordinati per grado. Perché?

Indicare operazioni supportate, e la loro complessità.
Sia un nodo di grado in un heap di Fibonacci e siano i figli di nell’ordine in cui sono stati innestati in . Quale limitazione inferiore è possibile dare per il grado degree. Perché? Lemma 3
Fornire (e dimostrare) una minorazione dei gradi dei figli di ciascun nodo (LEMMA)
Stabilire se esistono heap di Fibonacci dati nel compito

Si definiscano gli alberi binomiali e si enuncino le loro principali proprietà, dimostrandole;
Si definiscano gli heap binomiale e si fornisca una maggiorazione al grado max di un nodo in un heap binomiale contenente n nodi

Si descriva la struttura dati union-find nella sua versione più efficiente, presentando le due euristiche su cui si basa e illustrando mediante pseudo-codice le operazioni supportate.
Qual è la complessità di una sequenza di operazioni di cui sono Make Set?