WikiSort.ru - Программирование

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 21 февраля 2017 года.

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

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}$ , а для произвольного 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}$ -ое число Фибоначчи.

См. также

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