[找到一个在AVL树中从上到下（渐近）根r的等级的函数，即找到一个函数$ f（n）$，因此对于每个具有$ n $节点的AVL树都有一个常数$ c> 0 $$ 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 $。
现在我需要根据节点数量$ n $而不是高度$ h $来找到f。我的方向正确吗？希望任何帮助如何继续，谢谢。
f（n）= 0起作用...但是您可能想要更严格的限制。
在特定高度的最不平衡情况下，当根尽可能左移时，其右分支将是大小为Θ（2 h）=Θ（n）的完整树。很容易。
在左侧，您将有一个最小尺寸的树，这会更难一些。令M（h）为高度h的最小尺寸AVL树。我们有：
M（1）= 1;
M（2）= 2;否则
M（h）= M（h-1）+ M（h-2）+1
嗯，看来这个问题有一个有趣的答案。这种形式的递归关系具有我们可以解决的指数解。让我们开始
M（h）= e a + bh + c
那么我们有
e a + bh = e a + bh-b + e a + bh-2b + c +1
[区分双方w.r.t. h，我们得到
e a + bh = e a + bh-b + e a + bh-2b
e a + bh = e a + bh / e b + e a + bh / e 2b
（e b）2 = e b +1
嗯，给我们e b =φ，其中φ是黄金比例：https://en.wikipedia.org/wiki/Golden_ratio
所以M（h）=Θ（φh）
然后在最不平衡状态下的紧渐近边界变成：
Θ（f（n））=Θ（φlog n / n）=Θ（n φ-1]
所以f（n）= n φ-1是对您问题的最佳答案。