在给定多个节点的情况下，在AVL树中找到最小和最大高度？

Question

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

例如：
教科书中的问题：
一棵包含3个节点、5个节点和7个节点的AVL树的最大/最小高度是多少<教科书式答案：
3个节点的AVL树的最大/最小高度为2/2，5个节点为3/3，7个节点为4/3

我不知道他们是否通过一些神奇的公式计算出来，或者他们是否画出了每个给定高度的AVL树并以这种方式确定。

Answer 1

假设节点数为n

尝试找出AVL树的最小高度与尝试使树完整相同，即填充每个级别上所有可能的节点，然后移动到下一个级别。

因此，在每个级别上，合格节点的数量增加2^（h-1），其中h是树的高度。

因此，在h=1时，节点（1）=2^（1-1）=1个节点

对于h=2，节点（2）=节点（1) 2^(2-1) = 3节点

对于h=3，节点（3）=节点（2）2^（3-1）=7个节点

所以只要找到最小的h，其中节点（h）大于给定的节点数n。

现在，关于AVL树的最大高度问题：-

假设AVL树的高度为h，F（h）是AVL树中的节点数，

为了使其高度最大，让我们假设其左子树FL和右子树FR的高度差为1（因为它满足AVL属性）。

现在假设FL是高度为h-1的树，FR是高度为h-2的树。

现在节点数

F（h）=F（h-1）F（h-2）1（Eq 1）

在两侧添加1：

F（h）1=（F（h-1）1）（F（h-2）1）（等式2）

所以我们将最大高度问题简化为斐波那契序列。这些树F（h）被称为斐波那契树。

所以，F（1）=1，F（2）=2

所以为了得到最大高度，只需找到斐波那契数列中小于或等于n的数的索引。

So应用（等式1）

F（3）=F（2）F（1）1=4，所以如果n在2和4之间，树的高度将为3。

F（4）=F（3）F（2）1=7，类似地，如果n介于4和7之间，则树的高度为4。

等等。

Answer 2

注意AVL树的以下定义特征很重要。

AVL树属性

• AVL树的节点遵守BST属性
• 任何节点的左、右子树的高度相差不超过1

定理：AVL属性足以维持最坏情况树高O（log N）。

示例）T4包含12个节点。[上限]O（对数12）=4。

看到这里发展的模式了吗？？

Answer 3

下面的解决方案适用于手工解决问题并获得直觉，请参阅此答案底部的大树（54个节点）的确切公式。¹

最小高度很容易，只需在树的每一层填充节点，直到用完为止。这个高度是最小的。

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

如果您需要了解AVL树的属性，或者只是对AVL树的一般解释，Wikipedia是一个很好的起点。

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

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

如果你有一棵拥有大量节点的树，上面显示的技术就不适用了。在这种情况下，可以使用以下公式计算精确的最小/最大高度^2。

给定n个节点

最小值：ceil（log₂（n 1））

最大值：地板（1.44*对数2）（n 2）～0.328）

如果你好奇的话，第一次最大最小

感谢Jamie S让我注意到了更大节点数的故障

从技术上讲，树的高度是根和任何叶节点之间的最长路径长度（以边为单位）。然而，OP的教科书使用了一个常见的替代定义，即树的层数。为了与OP和维基百科保持一致，我们在这篇文章中也使用了这个定义

这些公式来自Wikipedia AVL页面，插入了常量。原始来源是Donald E.Knuth的排序和搜索（第二版）