Java AVL树中的最小节点数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21347187/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Minimum number of node in AVL tree?
提问by user2913922
I know the formula of finding minimum number of node in a AVL tree is
我知道在 AVL 树中找到最小节点数的公式是
S(h) = S(h-1) + S(h-2) + 1
S(h) = S(h-1) + S(h-2) + 1
However, I don't really get how to use this function, say if we have a AVL height of 6. The answer tells me that Minimum = 7 + 4 + 1 =12. But how do you get this number? I mean when you plug in 6 isn't it (6-1) + (6-2) + 1?
但是，我真的不知道如何使用这个函数，假设我们的 AVL 高度为 6。答案告诉我，Minimum = 7 + 4 + 1 =12。但是你怎么得到这个数字呢？我的意思是当你插入 6 时，不是 (6-1) + (6-2) + 1 吗？
Can anyone explain to me how to solve this? My teacher haven't talk about this yet but I really want to figure this out myself in order to be prepared for the test next week.
谁能向我解释如何解决这个问题？我的老师还没有谈论这个，但我真的很想自己弄清楚，以便为下周的考试做好准备。
采纳答案by Christian
In S(h) = S(h-1) + S(h-2) + 1,
在S(h) = S(h-1) + S(h-2) + 1，
S(h)is a recursivefunction/formula. A recursive function calls itself (in a smaller or simpler way) inside its body.
S(h)是一个递归函数/公式。递归函数在其内部调用自身（以更小或更简单的方式）。
Note that a recursive function must have some base cases, in this case:
请注意，递归函数必须有一些基本情况，在这种情况下：
S(1) = 0
S(2) = 1
So let's say h = 6, then S(h = 6)will be (just replacing):
所以让我们说h = 6，然后S(h = 6)将是（只是替换）：
S(6) = S(6-1) + S(6-2) + 1
S(6) = S(5) + S(4) + 1
S(6) = 2*S(4) + S(3) + 1 + 1
S(6) = 2*(S(3) + S(2) + 1) + S(3) + 2
S(6) = 3*S(3) + 2*S(2) + 4
S(6) = 3*(S(2) + S(1) + 1) + 2*S(2) + 4
S(6) = 5*S(2) + 3*S(1) + 7
S(6) = 5*1 + 3*0 + 7
S(6) = 12
回答by paxdiablo
You're confusing S(h-1)with S(h)-1, the first is the (minimum) size of a tree with height h-1, the second the size of a tree of height h, thensubtract one from that.
你混淆S(h-1)与S(h)-1，首先是随着高度一棵树的（最小）的大小h-1，高度的树的第二大小h，然后减去一个从。
回答by kobiyashi
using the Fibonacci sequence in two ways: the first way is less complex but not as efficient as the second one. In order to understand the second way you need to know some math, which I wont explain here unless you really wish for it or check out wiki for some answers first way:
以两种方式使用斐波那契数列：第一种方式不那么复杂，但不如第二种方式有效。为了理解第二种方式，您需要了解一些数学知识，除非您真的希望它或首先查看 wiki 以获得一些答案，否则我不会在这里解释：
public int findMinNodes(int h){
if(h<0)
return 0;
int a=1;
int b=2;
int c;
for(int i=1;i<h;i++){
c=a+b+1;
a=b;
b=c;
}
return b;
}
second way:
第二种方式：
public static int findMinNodes(int h){
return (int)(Math.round(((Math.sqrt(5)+2)/
Math.sqrt(5))*Math.pow((1+
Math.sqrt(5))/2,h)-1));
}
Note:if you try the second method with really large inputs (say h=6000) your answer will display "infinity" that is due to the Math methods.
注意：如果您尝试使用非常大的输入（比如 h=6000）的第二种方法，您的答案将显示“无穷大”，这是由于数学方法。
回答by user3449719
Min nodes in avl tree with height h are when it has a balancing factor of either 1 or-1. In that kind of avl tree One sub tree has height h-1 and other sub tree's height is h-2. Therefore we calculate no. Of nodes of tree of height h-1 and h-2 recursively and add 1 to it. 1 is added to count root node of previous tree.
avl 树中高度为 h 的最小节点是当它的平衡因子为 1 或 -1 时。在那种avl树中，一棵子树的高度为h-1，另一棵子树的高度为h-2。因此我们计算没有。对高度为 h-1 和 h-2 的树的节点递归地加 1。添加 1 以计算前一棵树的根节点。
回答by Duncan Iglesias
Just a quick note to the question above, the minimum number of nodes in an AVL tree for a tree with a height of 6 is not 12, it should be 20. The following equation should demonstrate the recursive call of the S(h) function.
只是对上述问题的快速说明，高度为 6 的树的 AVL 树中的最小节点数不是 12，应该是 20。 下面的等式应该演示 S(h) 函数的递归调用.
Since we know that S(1) = 1, S(2) = 2, & S(3) = 4, we can reduce the following equation to these knowns for h = 6.
由于我们知道 S(1) = 1, S(2) = 2, & S(3) = 4，我们可以将以下等式简化为 h = 6 的这些已知值。
S(h) = S(h-1) + S(h-2) + 1
S(6) = S(5) + S(4) + 1 // recursive S(5) & S(4)
S(6) = (S(4) + S(3) + 1) + (S(3) + S(2) + 1) + 1 // don't forget '+1'
S(6) = [(S(3) + S(2) + 1) + S(3) + 1] + (S(3) + S(2) + 1) + 1
// now sub in the values
S(6) = [(4 + 2 + 1) + 4 + 1] + (4 + 2 + 1) + 1
S(6) = 4 + 2 + 1 + 4 + 1 + 4 + 2 + 1 + 1
S(6) = 20
I hope this helps. Please let me know if I overlooked something!
我希望这有帮助。如果我忽略了什么，请告诉我！
回答by Rana Priyanka
the minimum number of nodes in an AVL tree for a tree with a height of 6 is not 20, it should be 33. The following equation should demonstrate the recursive call of the N(h) function.
对于高度为 6 的树，AVL 树中的最小节点数不是 20，应该是 33。以下等式应该演示 N(h) 函数的递归调用。
Since we know that N(0)=1 ,N(1) = 2, N(2) = 4, we can reduce the following equation to these knowns for h = 6.
由于我们知道 N(0)=1 ,N(1) = 2, N(2) = 4，我们可以将以下等式简化为 h = 6 的这些已知值。
formula N(h)=1+N(h-1)+N(h-2)
公式 N(h)=1+N(h-1)+N(h-2)
N(3)=1+N(3-1)+N(3-2)=1+N(2)+N(1)=7
N(3)=1+N(3-1)+N(3-2)=1+N(2)+N(1)=7
N(4)=1+N(4-1)+N(4-2)=1+N(3)+N(2)=12
N(4)=1+N(4-1)+N(4-2)=1+N(3)+N(2)=12
N(5)=1+N(5-1)+N(5-2)=1+N(4)+N(3)=20
N(5)=1+N(5-1)+N(5-2)=1+N(4)+N(3)=20
N(6)=1+N(6-1)+N(6-2)=1+N(5)+N(4)=33
N(6)=1+N(6-1)+N(6-2)=1+N(5)+N(4)=33
I hope this may help you
我希望这可以帮助你
回答by Michael B
For the function N(h) = 1 + N(h - 1) + N(h - 2)
对于函数 N(h) = 1 + N(h - 1) + N(h - 2)
MIT Recitation 04 states the base cases for this recursive function are: N(1) = 1; N(2) = 2
MIT Recitation 04 指出这个递归函数的基本情况是：N(1) = 1；N(2) = 2
therefore
所以
N(3) = 1 + N(2) + N(1) = 1 + 2 + 1 = 4
N(3) = 1 + N(2) + N(1) = 1 + 2 + 1 = 4
N(4) = 1 + N(3) + N(2) = 1 + 4 + 2 = 7
N(4) = 1 + N(3) + N(2) = 1 + 4 + 2 = 7
N(5) = 1 + N(4) + N(3) = 1 + 7 + 4 = 12
N(5) = 1 + N(4) + N(3) = 1 + 7 + 4 = 12
N(6) = 1 + N(5) + N(4) = 1 + 12 + 7 = 20
N(6) = 1 + N(5) + N(4) = 1 + 12 + 7 = 20
N(7) = 1 + N(6) + N(5) = 1 + 20 + 12 = 33
N(7) = 1 + N(6) + N(5) = 1 + 20 + 12 = 33
N(8) = 1 + N(7) + N(6) = 1 + 33 + 20 = 54
N(8) = 1 + N(7) + N(6) = 1 + 33 + 20 = 54
and so on, just keep plugging the numbers in from previous answers...
等等，只需继续插入先前答案中的数字......
