给定高度的最大高度 AVL 树有多少？
How many maximum height AVL trees given height?
我在寻找用于查找高度为 h 的最大高度 AVL 树数的递归公式时遇到了一些问题。高度 0 有 1，高度 1 有 2，高度 2 有 4，高度 3 有 8，等等，对吗？
高度h的AVL树最大节点数n为n = 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1（除根节点外的每个节点都有两个子节点，即每一层的节点数是上一个）。根据节点数 n 给出高度 h 的公式为：h = log(n + 1).
换个角度来看这个问题
代替给定节点数的最大高度，让我们找到给定高度的最小节点数。对于这个问题，我们有这个递归函数：n(h) = n(h-1) + n(h-2) + 1 因为你至少需要 n(h-1) 个右子树节点和 n(h-2) 个左子树节点以及一个根节点。
（图片和更完整的解释 here）。
考虑到这一点，您必须找到一个 h 使得 n(h) < n < n(h+1) 其中 n 是给定的节点数。
顺便说一句，简短的回答是 h < 2log(n) + 2
我在寻找用于查找高度为 h 的最大高度 AVL 树数的递归公式时遇到了一些问题。高度 0 有 1，高度 1 有 2，高度 2 有 4，高度 3 有 8，等等，对吗？
高度h的AVL树最大节点数n为n = 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1（除根节点外的每个节点都有两个子节点，即每一层的节点数是上一个）。根据节点数 n 给出高度 h 的公式为：h = log(n + 1).
换个角度来看这个问题
代替给定节点数的最大高度，让我们找到给定高度的最小节点数。对于这个问题，我们有这个递归函数：n(h) = n(h-1) + n(h-2) + 1 因为你至少需要 n(h-1) 个右子树节点和 n(h-2) 个左子树节点以及一个根节点。
考虑到这一点，您必须找到一个 h 使得 n(h) < n < n(h+1) 其中 n 是给定的节点数。
顺便说一句，简短的回答是 h < 2log(n) + 2