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

Материал из WEGA
Версия от 13:51, 13 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево Фибоначчи''' (''Fibonacci tree'') - бинарное дерево, определяемое следующим ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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