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

Дерево Фибоначчи — АВЛ-дерево с наименьшим числом вершин при заданной высоте (глубине).

1. Если для какой-либо из вершин высота поддерева, для которого эта вершина является корнем, равна $h$, то правое и левое поддерево этой вершины имеют высоты равные соответственно $h-1$ и $h-2$, или $h-2$ и $h-1$. Каждое поддерево дерева Фибоначчи также является деревом Фибоначчи.
2. Пустое дерево — дерево Фибоначчи высоты 0.
3. Дерево с одной вершиной — дерево Фибоначчи высоты 1.

Число вершин

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

См. также

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