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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Дерево Фибоначчи''' (''Fibonacci tree'') - бинарное дерево, определяемое следующим ...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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],  
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


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

Текущая версия от 12:48, 4 февраля 2011

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