Alberi Binomiali Non Ordinati

Implementano gli Heap di Fibonacci.

Definizione

, definito in base alla seguente ricorsione:

• è l’albero formato da un solo nodo;
• Dato definiamo combinando due copie di nella seguente maniera:

Lemma (Proprietà degli alberi binomiali NON Ordinati)

Per ogni valgono le segu\enti proprietà: 

1. ha nodi;
2. L’altezza di è ;
3. ha a profondità
4. La radice di ha grado ed ogni altro nodo in ha grado . Inoltre, i figli della radice di sono radici di in un qualsiasi ordine . 

• Si osservi che da questo lemma segue immediatamente che , almeno quando l’heap è formato soltanto da alberi binomiali non ordinati.
• La strategia di mantenimento degli Heap di Fibonacci prevede di ritardare il più possibile il lavoro di ristrutturazione dell’heap.

DImostrazione per induzione 

Caso Base:  

1. ha nodi.
2. L’altezza di è
3. ha nodi a profondità
4. La radice di ha grado

Passo Induttivo: Supponiamo che il Lemma sia vero per , con

1. ha nodi.

2. L’altezza di è

3. Sia , il numero di nodi di a profondità è uguale a:  

   Inoltre, ha nodi a profondità 0, quindi avrà nodi a profondità .

4. La radice di ha grado $degree{U_{k-1}}+1 = k

   • Inoltre ciascun altro nodo appartiene ad un e pertanto per ipotesi induttiva ha grado , cioè .
   • Il primo figlio della radice di è radice di . Inoltre, per ipotesi induttiva, I successivi figli della radice di sono radici di