给定多个节点，求 AVL 树的最小和最大高度？

给定一定数量的节点，是否有公式可以计算 AVL 树的最大和最小高度？

例如：
课本问题：
3 个节点、5 个节点和 7 个节点的 AVL 树的最大/最小高度是多少？
课本答案：
3 个节点的 AVL 树的最大/最小高度为 2/2，5 个节点的 AVL 树的最大/最小高度为 3/3，7 个节点的 AVL 树的最大/最小高度为 4/3

我不知道他们是否通过某种神奇的公式得出了这个结果，或者他们是否为每个给定的高度绘制了 AVL 树并以此方式确定了它。

The solution below is appropriate for working things out by hand and gaining an intuition, please see the exact formulas at the bottom of this answer for larger trees (54+ nodes).¹

Well the minimum height² is easy, just fill each level of the tree with nodes until you run out. That height is the minimum.

要找到最大值，请执行与最小值相同的操作，但然后返回一步（删除最后放置的节点）并查看将该节点添加到相反的子树（从它刚刚所在的位置）是否违反 AVL 树属性。如果是这样，您的最大身高就是您的最小身高。否则这个新高度（应该是最小高度+1）就是你的最大高度。

如果您需要概述 AVL 树的属性，或者只是 AVL 树的一般解释，维基百科是一个很好的起点。 http://en.wikipedia.org/wiki/AVL_tree

Example:

我们以 7 节点为例。您填充所有级别并找到高度为 3 的完全填充的树。（1 个位于第 1 级，2 个位于第 2 级，4 个位于第 3 级。1+2+4=7 个节点。）这意味着 3 是您的最小值。

现在找到最大值。删除最后一个节点并将其放置在左子树而不是右子树上。右子树的高度仍然为 3，但左子树的高度现在为 4。但是这些值相差不到 2，因此它仍然是 AVL 树。因此你的最大高度是 4。（即 min+1）

下面列出了所有三个示例（请注意，数字对应于放置顺序，不值):

公式：

The technique shown above doesn't hold if you have a tree with a very large number nodes. In this case, one can use the following formulas to calculate the exact min/max height².

Given n nodes³:

Minimum: ceil(log₂(n+1))

Maximum: floor(1.44*log₂(n+2)-.328)

如果您好奇的话，第一次 max-min>1 是在 n=54 时。

^{1Thanks to Jamie S https://stackoverflow.com/users/6553450/jamie-s for bringing this failure at larger node counts to my attention.}

^{2Technically, the height of a tree is the longest path length (in edges) between the root and any leaf node https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology. However the OP's textbook uses a common alternate definition of height as the number of levels in a tree. For consistency with the OP and Wikipedia, we use that definition in this post as well.}

^{3These formulas are from the Wikipedia AVL page https://en.wikipedia.org/wiki/AVL_tree#Properties, with constants plugged in. The original source is Sorting and searching by Donald E. Knuth (2nd Edition).}