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

Дерево Фибоначчи (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].

Литература

[Евстигнеев/85],

[Евстигнеев-Касьянов/94],

[Рейнгольд-Нивергельт-Део]