Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

ДЕРЕВО ФИБОНАЧЧИ

Дерево Фибоначчи — это сбалансированное АВЛ-дерево с минимально возможным количеством узлов при заданной высоте: каждый узел дерева имеет левое поддерево высотой на единицу больше, чем его правое поддерево.

Определение дерева Фибоначчи:

  • 1) пустое дерево есть дерево Фибоначчи с высотой 0;
  • 2) дерево из одного узла есть дерево с высотой 1;
  • 3) если Тк_х и Ти 2 — деревья Фибоначчи с высотами к -1 и И- 2 , ТО ТИ={ТИ-1’Х> Тк_2) есть дерево Фибоначчи с высотой И и корнем х;
  • 4) никакие другие деревья не являются деревьями Фибоначчи.

Согласно этому определению дерево Фибоначчи высотой к > 1

строится следующим образом: в корень помещается узел, в его левое поддерево помещается дерево Фибоначчи высотой к-1, а в правое поддерево — дерево Фибоначчи высотой к-2 .

На рис. 3.15 приведены деревья Фибоначчи высотой к {к = 1,2,..., 5) и числом узлов пи:

/7=1 /7=2 /7=3 /7=4 /7=5

771 = 1 772 =2 «3=4 ПА=1 77-=12

Деревья Фибоначчи высотой И и числом узлов п

Рис. 3.15. Деревья Фибоначчи высотой И и числом узлов пи

Фактически число узлов в дереве Фибоначчи высотой к определяется формулой

где Рк+2 число Фибоначчи порядка к + 2.

Числа Фибоначчи вычисляются по следующему правилу:

Г0 =0; Р, = 1; Рк = Ри_2 + Ри_{, при к = 2,3,...

Значения чисел Фибоначчи для /7 = 0, 1,..., 10 и число узлов в соответствующих деревьях Фибоначчи приведены на рис. 3.16.

держит 2л-1 узлов).

Напомним, что максимальное количество узлов при заданной высоте содержит совершенное бинарное дерево, все листья которого расположены на одном уровне (совершенное дерево высотой к со

Высота дерева

И

Число Фибоначчи Рн

Число узлов в дереве Фибоначчи

"/,

0

0

0

1

1

1

2

1

2

3

2

4

4

3

7

5

5 г ^12

6

8 20

7

13 ^

33

8

21

54

9

34

88

10

55

143

Рис. 3.16. Число узлов в деревьях Фибоначчи

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы