Árbol de Fibonacci

Árbol de Fibonacci
Á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 hijo izquierdo y el árbol de Fibonacci de orden n-2 como hijo derecho.

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 C++ del árbol 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;
}

Enlaces externos

Referencias


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Árbol binario — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Árbol AVL — es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson Velskii y Landis. Fue el primer árbol de búsqueda binario auto balanceable que se ideó. Contenido 1 Descripción 2 Definición formal 2.1 Definición de la …   Wikipedia Español

  • Árbol rojo-negro — Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en… …   Wikipedia Español

  • Montículo de Fibonacci — Para otros usos de este término, véase Montículo (desambiguación). En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentro de los… …   Wikipedia Español

  • Sucesión de Fibonacci — Gráfica de la sucesión de Fibonacci hasta f10 En matemática, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales: La sucesión inicia con …   Wikipedia Español

  • Cábala — Árbol de la Vida, de Athanasius Kircher. La Cábala o Qabbaláh (del hebreo קַבָּלָה‎ qabbalah recibir ) es una de las principales corrientes de la mística judía. La base estructural de este estudio consiste en el análisis del Árbol de la Vida.… …   Wikipedia Español

  • Programación dinámica (informática) — Saltar a navegación, búsqueda En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación …   Wikipedia Español

  • Sistema-L — Un sistema L o un sistema de Lindenmayer es una gramática formal (un conjunto de reglas y símbolos) principalmente utilizados para modelar el proceso de crecimiento de las plantas; puede modelar también la morfología de una variedad de organismos …   Wikipedia Español

  • Montículo (informática) — Para otros usos de este término, véase Montículo (desambiguación). Este artículo trata sobre la estructura de datos. Para el lugar de donde se asigna memoria dinámica, véase asignación dinámica de memoria. Este artículo o sección necesita… …   Wikipedia Español

  • Lorenzo Langstroth — Lorenzo Langstroth. Lorenzo Lorraine Langstroth (* 25 de diciembre de 1810 – 6 de octubre de 1895) fue un apicultor estadounidense; nacido en Filadelfia, Pensilvania. Graduado en Yale en 1880, trabajó allí hasta 1834 1835. Fue el pastor de varias …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”