Arbre de Fibonacci
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).
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
- http://www.cse.ohio-state.edu/~weide/sce/now/321/homeworks/hw02.html Arxivat 2007-01-15 a Wayback Machine.
- http://www.fdi.ucm.es/profesor/milanjm/edi0203/FI611_03_Jun_2_parcial_.pdf Arxivat 2010-06-30 a Wayback Machine.
- http://www.conclase.net/c/edd/index.php?cap=006b
- http://articulos.conclase.net/arboles-b/index.html Arxivat 2009-09-19 a Wayback Machine.