Дерево Фибоначчи | это... Что такое Дерево Фибоначчи? (original) (raw)

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

Дерево Фибоначчи — АВЛ-дерево с наименьшим числом вершин при заданной высоте (глубине).

Если для какой-либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и , или и . Каждое поддерево дерева Фибоначчи также является деревом Фибоначчи.
Пустое дерево — дерево Фибоначчи высоты 0.
Дерево с одной вершиной — дерево Фибоначчи высоты 1.

Число вершин

Одно из весьма существенных свойств дерева Фибоначчи — количество вершин в нём может принимать только некоторый набор значений. Пусть N_h — число вершин в дереве Фибоначчи с высотой , тогда N_0=0 , N_1=1 , а для произвольного h высоту можно описать рекуррентно: $N_h=N_{h-1}+N_{h-2}+1$ . Дерево Фибоначчи названо так из-за схожести приведённой формулы с рекуррентным соотношением, определяющим последовательность чисел Фибоначчи. Для высоты число вершин $N_h=\Phi_{h+2}-1$ , где $\Phi_n$ — -ое число Фибоначчи.

См. также

Дерево (структура данных)
Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура
Двоичные деревья	Двоичное дерево · T-дерево
Самобалансирующиеся двоичные деревья	АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи
B-деревья	B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево
Префиксные деревья	Суффиксное дерево · Radix tree · Ternary search tree
Двоичное разбиение пространства	k-мерное дерево · VP-дерево
Недвоичные деревья	Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево
Разбиение пространства	R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков
Другие деревья	Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree
Алгоритмы	Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева

Категории:

Теория чисел
Деревья (структуры данных)

Wikimedia Foundation.2010.

Полезное

Смотреть что такое "Дерево Фибоначчи" в других словарях:

Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Содержание 1 Дерево отрезков в памяти … Википедия
Дерево Фенвика — (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году … Википедия
Фибоначчи числа — Числа Фибоначчи элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… … Википедия
Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершин… … Википедия
Дерево (структура данных) — У этого термина существуют и другие значения, см. Дерево (значения). Простой пример неупорядоченного дерева Дерево одна из наиболее широко распространённых структу … Википедия
Дерево квадрантов — Разбитая с помощью дерева квадрантов плоскость Дерево квадрантов (также квадродерево, 4 дерево, англ. quadtree) дере … Википедия
Фибоначчи — (Fibonacci) Фибоначчи первый крупный математик средневековой Европы Десятичная система счисления, арабские цифры, числа, последовательность, уровни, ряд, линии и спираль Фибоначчи Содержание >>>>>>>>> … Энциклопедия инвестора
Числа Фибоначчи — Числа Фибоначчи элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух… … Википедия
Последовательность Фибоначчи — Числа Фибоначчи элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… … Википедия
Ряд Фибоначчи — Числа Фибоначчи элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… … Википедия