Next: L'utilizzo degli Heap di
Up: Gli Heap di Fibonacci
Previous: Operazioni - Cancellazione di
  Indice
Affinchè il costo ammortizzato della fuzione DECREASE-KEY e DELETE sia
realmente , dobbiamo dimostrare che il limite superiore al grado di
un qualsiasi nodo di uno Heap di Fibonacci è .
Chiameremo xsize il numero di nodi dell'albero
radicato in x (compreso x stesso). La dimostrazione mostra
anche come xsize è esponenziale a
xgrado.
Lemma 1
Sia
un nodo di un qualsiasi Heap di Fibonacci tale che abbia
(xgrado)=k. Siano
i suoi figli
ordinati in base al loro ordine di arrivo. Allora vale che
(
grado e (
grado per i =
2,3,
k.
Dimostrazione:
per dire che (grado non serve dimostrazione; dato
si nota che quando è diventato figlio di , aveva
i figli
e quindi (grado;
poichè può essere stato aggiunto solo se aveva grado uguale a
, in quel momento si aveva (grado.
Da quell'istante a perso al più un figlio perchè altrimenti
sarebbe stato tagliato (vedi sottosezione 2.8 ed in particolare la
funzione taglio-a-cascata). Ne consegue che (grado
Con quello che stiamo per vedere si capisce finalmente perchè questo tipo
di struttura si chiami ``Heap di Fibonacci''. Come tutti sanno l'
-esimo numero di Fibonacci è:
Il seguente lemma dimostra che può essere espresso in un'altro modo:
Lemma 2
per tutti gli
si possono esprimere i numeri di
Fibonacci come segue:
Dimostrazione:
Per induzione su :
Per
Data l'ipotesi induttiva
,
si ha:
Indichiamo con il cosiddetto rapporto aureo definito come
Il Lemma 4 che termina la dimostrazione utilizza il seguente
Lemma 3.
Dimostrazione(per induzione su ):
Caso Base:
Semplice verifica per e
Passo Induttivo:
per ipotesi
basta quindi dimostrare che
cioè che
ed infatti sostituendo il valore di si verifica che
Lemma 4
sia
un nodo di uno Heap di Fibonacci e
. Allora vale che
dove
.
Dimostrazione:
Definiamo il minimo valore possibile di tra i nodi
t.c.
. Chiaramente si ha che e
.
Dato un nodo , siano
i suoi figli
ordinati in base al loro ordine di arrivo. Troviamo ora un limite
inferiore su : sommiamo per stesso, per il
primo figlio e poi
applichiamo via via il Lemma 1 per gli altri figli. Si ha quindi:
Resta ora da dimostrare per induzione su che
.
I casi di base (per e ) sono di verifica immediata.
Con si prenda come ipotesi induttiva che
per
.
Abbiamo quindi:
Abbiamo quindi dimostrato che:
dove l'ultima disuguaglianza è data dal Lemma 3.
Con il Corollario 5 termina la parte relativa alla limitazione
del grado massimo.
Corollario 5
Il grado massimo
di un nodo di uno
Heap di Fibonacci
composto da
nodi é
.
Dimostrazione:
Sia un nodo di heap di Fibonacci composto da nodi e sia
. Possiamo dire che
dato il
Lemma 3. Utilizzando si ottiene
, cioè
.
Il grado massimo (quello che noi avevamo chiamato ) di un qualunque
nodo di uno heap di Fibonacci è dunque
Next: L'utilizzo degli Heap di
Up: Gli Heap di Fibonacci
Previous: Operazioni - Cancellazione di
  Indice
Paolo Larcheri
2002-01-26