问给定高度的AVL树的最大高度是多少？

EN

让我们从另一个角度来看这个问题。

让我们找出给定高度的最小节点数，而不是给定节点数的最大高度。对于这个问题，我们有一个递归函数：n(h) = n(h-1) + n(h-2) + 1，因为您需要在右子树中至少有n(h-1)节点，在左子树中至少需要n(h-2)节点，并且需要一个节点作为根。

​

(图片和更完整的解释here)。

考虑到这一点，您必须找到一个满足n(h) < n < n(h+1)的h，其中n是您给定的节点数。

顺便说一句，简短的答案是h < 2log(n) + 2

在高度为h的AVL树中，最大节点数n是n = 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1 (除了根之外，每个节点都有两个子节点，这意味着每一层的节点比前一层多两倍)。这就给出了根据节点数n计算高度h的公式：h = log(n + 1)。