Árbol de Fibonacci

De Wikipedia, la enciclopedia libre
Árboles de Fibonacci de orden 1, 2, 3 y 4.

Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci.
El árbol de Fibonacci se define de la siguiente manera:

El árbol nulo (no contiene ningún nodo) es de orden 0.
El árbol que consta de un único nodo es de orden 1.
Para n > 1, el árbol de Fibonacci de orden n consta de un nodo raíz con el árbol de Fibonacci de orden n-1 como uno de sus hijos y el árbol de Fibonacci de orden n-2 como el hijo restante.

Dado que este tipo de árbol es un caso particular de un árbol AVL, ya que el factor de equilibrio de todo nodo es -1, un árbol de Fibonacci es balanceado con altura O(log n).

Implementación en pseudo-código del árbol de Fibonacci[editar]

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;
}

Enlaces externos[editar]

Referencias[editar]

Obtenido de «https://es.wikipedia.org/w/index.php?title=Árbol_de_Fibonacci&oldid=150860245»