Árbol de fibonacci

El árbol de Fibonacci es un árbol AVL con el menor número de vértices para una altura (profundidad) determinada.

Si para cualquiera de los vértices la altura del subárbol para el cual este vértice es la raíz es , entonces los subárboles derecho e izquierdo de este vértice tienen alturas iguales a y , o y , respectivamente . Cada subárbol de un árbol de Fibonacci es también un árbol de Fibonacci. $h$ ${\ estilo de visualización h-1}$ ${\ estilo de visualización h-2}$ ${\ estilo de visualización h-2}$ ${\ estilo de visualización h-1}$
El árbol vacío es un árbol de Fibonacci de altura 0.
Un árbol con un vértice es un árbol de Fibonacci de altura 1.

Número de vértices

Una de las propiedades más esenciales del árbol de Fibonacci es que el número de vértices en él solo puede tomar un cierto conjunto de valores. Sea el número de vértices en el árbol de Fibonacci con altura , entonces , y para h arbitraria el número de vértices se puede describir recursivamente : . El árbol de Fibonacci se llama así por la similitud de la fórmula anterior con la relación de recurrencia que determina la secuencia de los números de Fibonacci . Para altura , el número de vértices es , donde es el -ésimo número de Fibonacci. ${\ Displaystyle N_ {h}}$ $h$ ${\ estilo de visualización N_ {0} = 0}$ ${\ estilo de visualización N_ {1} = 1}$ $N_{h}=N_{h-1}+N_{h-2}+1$ $h$ $N_{h}=\Phi _{h+2}-1$ ${\ estilo de visualización \ Phi _ {n}}$ $norte$

Véase también

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión