给定多个节点，在 AVL 树中查找最小和最大高度？
Finding the minimum and maximum height in a AVL tree, given a number of nodes?
给定一定数量的节点，是否有公式可以计算 AVL 树的最大高度和最小高度？
例如：
课本题：
3节点、5节点、7节点的AVL树的maximum/minimum高度是多少？
课本答案：
3个节点的AVL树的maximum/minimum高度是2/2，5个节点是3/3，7个节点是4/3
我不知道他们是否通过某种神奇的公式计算出来，或者他们是否为每个给定的高度画出 AVL 树并以此方式确定。
下面的解决方案适用于手动解决问题并获得直觉，请参阅此答案底部的确切公式以获得更大的树（54+ 个节点）。1
嗯，最小高度2 很简单，只需用节点填充树的每一层，直到 运行 出来。那个高度是最小的。
要找到最大值，与最小值相同，但返回一步（删除最后放置的节点）并查看是否将该节点添加到相反的子树（从它刚刚所在的位置）违反了 AVL 树 属性。如果是这样，您的最大身高就是您的最小身高。否则这个新高度（应该是最小高度+1）就是你的最大高度。
如果您需要概述 AVL 树的属性，或者只是对 AVL 树的一般解释，Wikipedia is a great place to start.
示例：
让我们以 7 节点为例。您填写所有级别并找到高度为 3 的完全填充的树。（1 在级别 1，2 在级别 2，4 在级别 3。1+2+4=7 个节点。）这意味着 3 是您的最小值。
现在找到最大值。删除最后一个节点并将其放在左子树而不是右子树上。右子树的高度仍然是 3，但是左子树的高度现在是 4。但是这些值相差不到 2，所以它仍然是一棵 AVL 树。因此，您的最大高度为 4。（即最小值+1）
下面列出了所有三个示例（请注意，数字对应于放置顺序，不是值）：
公式：
如果您的树的节点数非常多，则上面显示的技术不适用。在这种情况下，可以使用以下公式计算出确切的 min/max 高度 2.
给定 n 个节点3:
最小值： ceil(log2(n+1))
最大值： floor(1.44*log2(n+2)-.328)
如果你好奇的话，第一次max-min>1是在n=54的时候。
1感谢 Jamie S 让我注意到这个在较大节点数时的故障。
2从技术上讲，树的高度是 longest path length (in edges) between the root and any leaf node。然而，OP 的教科书使用一个常见的替代高度定义作为树中的级别数。为了与 OP 和维基百科保持一致，我们在此 post 中也使用该定义。
3这些公式来自Wikipedia AVL page，插入了常量。原始来源是排序和搜索 作者：Donald E. Knuth（第 2 版）。
请务必注意 AVL 树的以下定义特征。
AVL树属性
- AVL树的节点遵守BST属性
- AND任意节点左右子树的高度相差不超过1
定理：AVL 属性 足以维持 O(log N) 的最坏情况树高。
注意下图。
- T1 由 T0 + 1 个节点组成，高度为 1。
- T2 由 T1 和 T0 + 1 节点组成，高度为 2。
- T3 由左子树的 T2 和右子树的 T1 组成
子树 + 1 个节点，高度为 3。
- T4 由左子树的 T3 和右子树的 T2 组成
子树 + 1 个节点，高度为 4。
如果你取 上限 O(log N)，其中 N 表示 AVL 树中的节点数，你将得到高度。
Example) T4 contains 12 nodes. [ceiling]O(log 12) = 4.
看到这里发展的模式了吗？
**最坏情况下的身高是
假设节点数为n
试图找出 AVL 树的最小高度与试图使树完整 相同，即填充每一层的所有可能节点，然后移动到下一级。
因此在每个级别，符合条件的节点数增加 2^(h-1)，其中 h 是树的高度。
So at h=1, nodes(1) = 2^(1-1) = 1 node
for h=2, nodes(2) = nodes(1)+2^(2-1) = 3 nodes
for h=3, nodes(3) = nodes(2)+2^(3-1) = 7 nodes
所以只要找到最小的h，其中nodes(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) (Eq 2)
所以我们已经将最大高度问题减少到 Fibonacci sequence。这些树 F(h) 被称为 Fibonacci Trees.
所以，F(1)=1 且 F(2)=2
因此，为了获得最大高度，只需找到斐波那契数列中小于或等于 n 的数字的索引即可。
所以应用 (Eq 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。
等等。
http://lcm.csa.iisc.ernet.in/dsa/node112.html
大致为 1.44 * log n，其中 n 是节点数。
有关如何推导的更详细说明。你可以参考这个link从第13页中间开始：http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter04.2.pdf
给定一定数量的节点，是否有公式可以计算 AVL 树的最大高度和最小高度？
例如：
课本题：
3节点、5节点、7节点的AVL树的maximum/minimum高度是多少？
课本答案：
3个节点的AVL树的maximum/minimum高度是2/2，5个节点是3/3，7个节点是4/3
我不知道他们是否通过某种神奇的公式计算出来，或者他们是否为每个给定的高度画出 AVL 树并以此方式确定。
下面的解决方案适用于手动解决问题并获得直觉，请参阅此答案底部的确切公式以获得更大的树（54+ 个节点）。1
嗯，最小高度2 很简单，只需用节点填充树的每一层，直到 运行 出来。那个高度是最小的。
要找到最大值，与最小值相同，但返回一步（删除最后放置的节点）并查看是否将该节点添加到相反的子树（从它刚刚所在的位置）违反了 AVL 树 属性。如果是这样，您的最大身高就是您的最小身高。否则这个新高度（应该是最小高度+1）就是你的最大高度。
如果您需要概述 AVL 树的属性，或者只是对 AVL 树的一般解释，Wikipedia is a great place to start.
示例：
让我们以 7 节点为例。您填写所有级别并找到高度为 3 的完全填充的树。（1 在级别 1，2 在级别 2，4 在级别 3。1+2+4=7 个节点。）这意味着 3 是您的最小值。
现在找到最大值。删除最后一个节点并将其放在左子树而不是右子树上。右子树的高度仍然是 3，但是左子树的高度现在是 4。但是这些值相差不到 2，所以它仍然是一棵 AVL 树。因此，您的最大高度为 4。（即最小值+1）
下面列出了所有三个示例（请注意，数字对应于放置顺序，不是值）：
公式：
如果您的树的节点数非常多，则上面显示的技术不适用。在这种情况下，可以使用以下公式计算出确切的 min/max 高度 2.
给定 n 个节点3:
最小值： ceil(log2(n+1))
最大值： floor(1.44*log2(n+2)-.328)
如果你好奇的话，第一次max-min>1是在n=54的时候。
1感谢 Jamie S 让我注意到这个在较大节点数时的故障。
2从技术上讲，树的高度是 longest path length (in edges) between the root and any leaf node。然而，OP 的教科书使用一个常见的替代高度定义作为树中的级别数。为了与 OP 和维基百科保持一致，我们在此 post 中也使用该定义。
3这些公式来自Wikipedia AVL page，插入了常量。原始来源是排序和搜索 作者：Donald E. Knuth（第 2 版）。
请务必注意 AVL 树的以下定义特征。
AVL树属性
- AVL树的节点遵守BST属性
- AND任意节点左右子树的高度相差不超过1
定理：AVL 属性 足以维持 O(log N) 的最坏情况树高。
注意下图。
- T1 由 T0 + 1 个节点组成，高度为 1。
- T2 由 T1 和 T0 + 1 节点组成，高度为 2。
- T3 由左子树的 T2 和右子树的 T1 组成
子树 + 1 个节点，高度为 3。
- T4 由左子树的 T3 和右子树的 T2 组成
子树 + 1 个节点，高度为 4。
如果你取 上限 O(log N)，其中 N 表示 AVL 树中的节点数，你将得到高度。
Example) T4 contains 12 nodes. [ceiling]O(log 12) = 4.
看到这里发展的模式了吗？
**最坏情况下的身高是
假设节点数为n
试图找出 AVL 树的最小高度与试图使树完整 相同，即填充每一层的所有可能节点，然后移动到下一级。
因此在每个级别，符合条件的节点数增加 2^(h-1)，其中 h 是树的高度。
So at h=1, nodes(1) = 2^(1-1) = 1 node
for h=2, nodes(2) = nodes(1)+2^(2-1) = 3 nodes
for h=3, nodes(3) = nodes(2)+2^(3-1) = 7 nodes
所以只要找到最小的h，其中nodes(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) (Eq 2)
所以我们已经将最大高度问题减少到 Fibonacci sequence。这些树 F(h) 被称为 Fibonacci Trees.
所以，F(1)=1 且 F(2)=2
因此，为了获得最大高度，只需找到斐波那契数列中小于或等于 n 的数字的索引即可。
所以应用 (Eq 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。
等等。
http://lcm.csa.iisc.ernet.in/dsa/node112.html
大致为 1.44 * log n，其中 n 是节点数。
有关如何推导的更详细说明。你可以参考这个link从第13页中间开始：http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter04.2.pdf