Arbre de Fibonacci

De la Viquipèdia, l'enciclopèdia lliure
Arbres de Fibonacci d'ordre 1, 2, 3 i 4

Es diu arbre de Fibonacci a una variant d'arbre binari amb la propietat que l'ordre d'un node es calcula com la successió de Fibonacci.
L'arbre de Fibonacci es defineix de la següent manera:

L'arbre nul (no conté cap node) és d'ordre 0.
L'arbre que consta d'un únic node és d'ordre 1.
Per n> 1, l'arbre de Fibonacci d'ordre n consta d'un node arrel amb l'arbre de Fibonacci d'ordre n-1 com a fill esquerre i l'arbre de Fibonacci d'ordre n-2 com a fill dret.

Atès que aquest tipus d'arbre és un cas particular d'un arbre AVL, ja que el factor d'equilibri de tot node és -1, un arbre de Fibonacci és balancejat amb alçada O (log n).

Implementació en C++ de l'arbre de Fibonacci[modifica]

TArbinDinamico <int> arbolFibonacci (int n) #
TArbinDinamico <int> res;
if (n == 0)
res = TArbinDinamico (0, n, 0);
else if (n == 1)
res = TArbinDinamico (1, n, 0);
else
res = TArbinDinamico (arbolFibonacci (n-1), n, arbolFibonacci (n-2));
return res;

}

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Arbre de Fibonacci

Referències[modifica]

Obtingut de «https://ca.wikipedia.org/w/index.php?title=Arbre_de_Fibonacci&oldid=30294192»