Дерево Фибоначчи — разновидность АВЛ-дерева с наименьшим числом вершин при заданной высоте (глубине). Такие деревья используются в теории алгоритмов и анализа сбалансированных структур данных как крайний случай для оценки нижних границ числа вершин AVL-деревьев.
Если для какой-либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и , или и . Каждое поддерево дерева Фибоначчи также является деревом Фибоначчи. Пустое дерево — дерево Фибоначчи высоты 0. Дерево с одной вершиной — дерево Фибоначчи высоты 1.
Число вершин Одно из существенных свойств дерева Фибоначчи — количество вершин в нём может принимать только определённый набор значений. Пусть — число вершин в дереве Фибоначчи с высотой . Тогда , , а для произвольного число вершин можно описать рекуррентно: .
Дерево Фибоначчи получило название благодаря сходству этой формулы с рекуррентным соотношением для чисел Фибоначчи. Для высоты число вершин вычисляется как , где — -ое число Фибоначчи.
См. также Дерево Двоичное дерево Двоичное дерево поиска АВЛ-дерево Числа Фибоначчи Фибоначчи
Примечания
Категория:Теория чисел Категория:Деревья (структуры данных)