Albero di Fibonacci

L'Albero di Fibonacci è un albero AVL che, data una determinata altezza, ha il minor numero possibile di nodi mantenendo il bilanciamento.

Albero di fibonacci di altezza 5

Questo particolare tipo di albero prende il nome dall'omonimo matematico Leonardo Fibonacci. L'albero ha infatti le caratteristiche della famosa successione, è infatti intrinsecamente ricorsivo. Lo si evince dal fatto che qualsiasi albero di Fibonacci di altezza h può essere costruito a partire da una radice e da un sottoalbero di altezza h-2 come sottoalbero destro e h-1 come sottoalbero sinistro.

Si verifica intuitivamente e visivamente che il coefficiente di bilanciamento di ogni singolo nodo dell'albero è +1. Quindi questa categoria di alberi è quella che più si avvicina alla condizione di sbilanciamento, pur essendo ovviamente ancora bilanciato.

Lemma dell'altezza

Enunciato

Sia ${\mathcal {T}}_{h}$ un albero di Fibonacci di altezza $h$ e sia ${\mathit {n}}_{h}$ il numero dei suoi nodi. Risulta ${\mathit {h}}=\theta (\log n_{h})$

Dimostrazione

Per la natura stessa dell'albero di Fibonacci, risulta che ${\mathit {n}}_{h}$ $=1+{\mathit {n}}_{h-1}+{\mathit {n}}_{h-2}$

Tale enunciato ricorda molto la formula ricorsiva per il calcolo della successione di Fibonacci. Si riesce a dimostrare per induzione che ${\mathit {n}}_{h}={\mathcal {F}}_{h+3}-1$ dove ${\mathcal {F}}_{h}$ rappresenta l'h-esimo elemento della successione di Fibonacci.

• Passo base:

Il passo base è verificato banalmente, dato che ${\mathit {n}}_{0}=1$ e ${\mathcal {F}}_{3}-1=2-1=1$.

• Passo induttivo:

Supponiamo che per ogni ${\mathit {k}}<{\mathit {h}}$ si abbia che ${\mathit {n}}_{k}={\mathcal {F}}_{k+3}-1$ ed usando le ricorrenze relative ad $n_{h}$ e ad ${\mathcal {F}}_{i}$ si ottiene:

${\mathit {n}}_{h}=1+{\mathit {n}}_{h-1}+{\mathit {n}}_{h-2}=1+{\mathcal {F}}_{h+2}-1+{\mathcal {F}}_{h+1}-1={\mathcal {F}}_{h+3}-1$

Inoltre una proprietà della successione di Fibonacci è che il rapporto tra due numeri della successione $\lim _{h\rightarrow \infty }{\frac {{\mathcal {F}}_{h+1}}{{\mathcal {F}}_{h}}}$ si avvicina sempre più al Rapporto Aureo $\phi ={\frac {(1+{\sqrt {5}})}{2}}\approx 1,61803...$ e si dimostra che ${\mathcal {F}}_{h}={\frac {\phi ^{h}-(1-\phi )^{h}}{\sqrt {5}}}={\frac {\phi ^{h}-(-\phi )^{-h}}{\sqrt {5}}}=\theta (\phi ^{h})$ .

L'altezza dell'albero e il numero dei nodi sono quindi legati esponenzialmente, ragion per cui si ottiene $h=\Theta (\log \ n_{h})$, in dettaglio un albero di Fibonacci con $n_{h}$ nodi ha altezza $<1,44\ \log(n_{h}+2)-0,328$

Considerazioni

Il lemma precedente permette anche di dimostrare che l'altezza di qualsiasi albero AVL è funzione logaritmica del numero dei nodi.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'albero di Fibonacci