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

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

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

Одно из существенных свойств дерева Фибоначчи — количество вершин в нём может принимать только определённый набор значений. Пусть ${\displaystyle N_{h}}$ — число вершин в дереве Фибоначчи с высотой ${\displaystyle h}$. Тогда ${\displaystyle N_{0}=0}$, ${\displaystyle N_{1}=1}$, а для произвольного ${\displaystyle 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}$-ое число Фибоначчи.

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

• Cormen, Thomas H. Introduction to Algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest … [и др.]. — 3rd. — MIT Press, 2009. — ISBN 978-0-262-03384-8.
• Knuth, Donald E. The Art of Computer Programming, Vol. 3: Sorting and Searching. — Addison-Wesley, 1998. — ISBN 978-0-201-89685-5.
• MIT OpenCourseWare — Introduction to Algorithms . MIT. Дата обращения: 21 сентября 2025.