Privat-portal.ru

Полезный блог privat-portal.ru

Метки: Дерево фибоначчи что это, заключение на тему дерево фибоначчи.

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

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

Число вершин

Одно из весьма существенных свойств дерева Фибоначчи — количество вершин в нём может принимать только некоторый набор значений. Пусть — число вершин в дереве Фибоначчи с высотой , тогда , , а для произвольного h высоту можно описать рекуррентно: . Дерево Фибоначчи названо так из-за схожести приведённой формулы с рекуррентным соотношением, определяющим последовательность чисел Фибоначчи. Для высоты число вершин , где — -ое число Фибоначчи.

См. также

Tags: Дерево фибоначчи что это, заключение на тему дерево фибоначчи.