Дерево Фибоначчи

Одно из весьма существенных свойств дерева Фибоначчи — количество вершин в нём может принимать только некоторый набор значений. Пусть ${\displaystyle N_{h}}$ — число вершин в дереве Фибоначчи с высотой ${\displaystyle h}$, тогда ${\displaystyle N_{0}=0}$, ${\displaystyle N_{1}=1}$, а для произвольного h число вершин можно описать рекуррентно: ${\displaystyle N_{h}=N_{h-1}+N_{h-2}+1}$. Дерево Фибоначчи названо так из-за схожести приведённой формулы с рекуррентным соотношением, определяющим последовательность чисел Фибоначчи. Для высоты ${\displaystyle h}$ число вершин ${\displaystyle N_{h}=\Phi _{h+2}-1}$, где ${\displaystyle \Phi _{n}}$ — ${\displaystyle n}$-ое число Фибоначчи.

• Дерево
  • Двоичное дерево
    • Двоичное дерево поиска
      • АВЛ-дерево
• Числа Фибоначчи
• Фибоначчи