Дерево Фибоначчи: различия между версиями

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

у которого левое [[поддерево]] [[корень|корня]] — дерево <math>F_{i-2}</math>, а правое —

дерево <math>F_{i-1}</math>. '''Дерево Фибоначчи''' <math>F_{h}</math> высоты <math>h</math> является наиболее асимметричным сбалансированным по высоте деревом, у которого в качестве одного из поддеревьев служит наиболее асимметричное дерево высоты <math>h-1</math>, а в качесте другого — наиболее асимметричное  дерево высоты <math>h-2</math>.

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

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