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

Дерево Фибоначчи (Fibonacci tree) — бинарное дерево, определяемое следующим образом: пустое дерево есть дерево Фибоначчи [math]\displaystyle{ F_{0} }[/math], вырожденное дерево есть дерево Фибоначчи [math]\displaystyle{ F_{1} }[/math], дерево Фибоначчи [math]\displaystyle{ F_{i} }[/math] есть корневое дерево, у которого левое поддерево корня — дерево [math]\displaystyle{ F_{i-2} }[/math], а правое — дерево [math]\displaystyle{ F_{i-1} }[/math]. Дерево Фибоначчи [math]\displaystyle{ F_{h} }[/math] высоты [math]\displaystyle{ h }[/math] является наиболее асимметричным сбалансированным по высоте деревом, у которого в качестве одного из поддеревьев служит наиболее асимметричное дерево высоты [math]\displaystyle{ h-1 }[/math], а в качесте другого — наиболее асимметричное дерево высоты [math]\displaystyle{ h-2 }[/math].

Литература

• Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980.