Albero di Fibonacci

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

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

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.

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

Per la natura stessa dell'albero di Fibonacci, risulta che ${\displaystyle {\mathit {n}}_{h}}$ ${\displaystyle =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 ${\displaystyle {\mathit {n}}_{h}={\mathcal {F}}_{h+3}-1}$ dove ${\displaystyle {\mathcal {F}}_{h}}$ rappresenta l'h-esimo elemento della successione di Fibonacci.

• Passo base:

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

• Passo induttivo:

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

${\displaystyle {\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 ${\displaystyle \lim _{h\rightarrow \infty }{\frac {{\mathcal {F}}_{h+1}}{{\mathcal {F}}_{h}}}}$ si avvicina sempre più al Rapporto Aureo ${\displaystyle \phi ={\frac {(1+{\sqrt {5}})}{2}}\approx 1,61803...}$ e si dimostra che ${\displaystyle {\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 ${\displaystyle h=\Theta (\log \ n_{h})}$, in dettaglio un albero di Fibonacci con ${\displaystyle n_{h}}$ nodi ha altezza ${\displaystyle <1,44\ \log(n_{h}+2)-0,328}$

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

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

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica