Найдите функцию, которая ограничивает сверху и снизу (асимптотически c) ранг root r в дереве AVL,
т.е. найдите функцию $ f (n) $, так что существует постоянная $ c> 0 $, что для каждого дерева AVL с $ n $ вершинами, поэтому $ c * f (n) \ le rank (r) \ le n- c* f (n) $.
$ rank (r) $ получает свое максимальное значение, когда его нижнее левое дерево содержит максимальное количество узлов и поскольку это дерево AVL, для дерева с высотой $ h $ левое нижнее дерево будет с высотой $ h-1 $ и количество узлов будет максимальным, когда поддерево является полным деревом с узлами $ 2 ^ {h-2} -1 $, поэтому мы получаем:
$ rank (r) \ leq 2 ^ { h-2} -1 + 1 = 2 ^ {h-2} $
С другой стороны, $ rank (r) $ получает минимальное значение, когда его под левое дерево содержит минимальное количество узлов и это происходит, когда под левое дерево является деревом Фибоначчи с высотой $ h-2 $, поэтому
$ rank (r) \ geq \ phi ^ {h-2} +1 $.
Сейчас Мне нужно найти f как функцию количества узлов $ n $, а не высоты $ h $. Я нахожусь в правильном направлении?
Хотел бы уточнить любую помощь, как продолжить, Спасибо.