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

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

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

Числовершин


 Одно из весьма существенных свойств дерева Фибоначчи — количествовершин в нём может принимать только некоторый набор значений. ПустьNh — число вершин в дереве Фибоначчи с высотой h, тогда N0=0,N1=1, а для произвольного h число вершин можно описать рекуррентно:Nh=Nh1+Nh2+1. Дерево Фибоначчи названо так из-за схожестиприведённой формулы с рекуррентным соотношением, определяющимпоследовательность чисел Фибоначчи. Для высоты h число вершинNh=Φh+21, где Φnn-ое число Фибоначчи.