miniatura|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 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
http://www.cse.ohio-state.edu/~weide/sce/now/321/homeworks/hw02.html http://www.fdi.ucm.es/profesor/milanjm/edi0203/FI611_03_Jun_2_parcial_.pdf http://www.conclase.net/c/edd/index.php?cap=006b http://articulos.conclase.net/arboles-b/index.html
Referències http://www.nist.gov/dads/HTML/fibonacciTree.html
Categoria:Estructura de dades