Дерево Фибоначчи: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево Фибоначчи''' (''Fibonacci tree'') - бинарное дерево, определяемое следующим ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Дерево Фибоначчи''' (''Fibonacci tree'') - | '''Дерево Фибоначчи''' (''[[Fibonacci tree]]'') - [[бинарное дерево]], определяемое следующим образом: пустое [[дерево]] есть дерево Фибоначчи <math>F_{0}</math> [[вырожденное дерево]] есть дерево Фибоначчи <math>F_{1}</math> дерево Фибоначчи <math>F_{i}</math>есть [[корневое дерево]], | ||
бинарное дерево, определяемое следующим образом: пустое дерево есть | у которого левое [[поддерево]] [[корень|корня]] --- дерево <math>F_{i-2}</math>, а правое --- | ||
дерево Фибоначчи <math>F_{0}</math> вырожденное дерево есть дерево Фибоначчи | дерево <math>F_{i-1}</math>. '''Д.Ф.''' <math>F_{h}</math> высоты <math>h</math> является наиболее асимметричным сбалансированным по высоте деревом, у которого в качестве одного из поддеревьев служит наиболее асимметричное дерево высоты <math>h-1</math>, а в качесте другого --- наиболее асимметричное дерево высоты <math>h-2</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>. | |||
==Литература== | ==Литература== | ||
[Евстигнеев/85], | [Евстигнеев/85], | ||
Версия от 17:33, 14 октября 2009
Дерево Фибоначчи (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],
[Рейнгольд-Нивергельт-Део]