AVL樹的最大和最小節點

Question

請問如何在AVL樹中的最大和最小數量的節點給出的8

高度我似乎無法能夠從追查出來的情況下正確公式f（8）= F（7）+ F（6）1

2*f(6)+f(5)+2 
2*[f(5)+f(4)+1]+f(5)+2 
3*f(5)+2*f4+4 
3*[f(4)+f(3)+1]+2*f(4)+4 
5*f(4)+3*f(3)+7 
5*[f(3)+f(2)+1]+3*f(3)+7 
8*f(3)+5*f(2)+12 
8*[f(2)+f(1)+1]+5*f(2)+12 
13*f(2)+8*f(1)+20 
13*[f(1)+f(0)+1]+8*f(1)+20 
21*f(1)+13*f(0)+33=54 whereas answer is 88 is the minimum 

Answer 1

對於AVL樹的每個節點，我們知道左側的深度和右子樹通過至多1不同（這是由定義給出）。由此，下一步是非常明顯的：我們採用深度爲N和N - 1的最小樹，並將它們作爲新的根的子樹。很明顯，AVL規則依然成立，並且樹包含儘可能少的節點（從歸納基礎案例中可以看出）。我們已經得到了遞歸公式：minnodes（depth）= 1 + minnodes（depth-1）+ minnodes（depth - 2）。這是一個簡單的遞歸方程，Wolfram Alpha可以爲你解決（link）。

第二種情況是微不足道的 - 深度爲h的完美二叉樹包含儘可能多的節點，給定的深度和平凡滿足AVL條件。

Answer 2

你的地方失算了一步，貌似接近尾聲：

f(0) = 1 
f(1) = 2 
f(2) = f(1) + f(0) + 1 = 4 
f(3) = f(2) + f(1) + 1 = 4 + 2 + 1 = 7 
f(4) = f(3) + f(2) + 1 = 7 + 4 + 1 = 12 
f(5) = f(4) + f(3) + 1 = 12 + 7 + 1 = 20 
f(6) = f(5) + f(4) + 1 = 20 + 12 + 1 = 34 
f(7) = f(6) + f(5) + 1 = 34 + 20 + 1 = 55 
f(8) = f(7) + f(6) + 1 = 55 + 34 + 1 = 88 

如果你不相信的話，你總是可以編造一個快速片段檢查：

@Test 
public void testGetMax() { 
    assertEquals(88, getMax(8)); 
} 

int getMax(int x) { 
    switch (x) { 
     case 0: 
      return 1; 
     case 1: 
      return 2; 
     default: 
      return getMax(x - 1) + getMax(x - 2) + 1; 
    } 
}