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

Question

我找到一个递归公式来找到高度为h的最大高度AVL树的数量时遇到了一些麻烦。高度0有1，高度1有2，高度2有4，高度3有8等都是正确的吗？

Answer 1

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

而不是给定节点数的最大高度，让我们找到给定高度的最小节点数。对于这个问题，我们有这个递归函数：n(h) = n(h-1) + n(h-2) + 1，因为你需要至少子树中的n(h-1)节点和左子树中的n(h-2)节点以及root的一个节点。

（图片和更完整的解释here）。

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

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

Answer 2

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