53. AVL 樹是一種平衡二元搜尋樹。今天給一棵高度為 5的 AVL 樹，請問該樹的節點最少為？(這邊的高度指的是根節點到葉節點所經過的「邊」數)
(A) 16
(B) 20
(C) 31
(D) 32

要找出高度為 5 的 AVL 樹最少有多少節點，我們需要理解 AVL 樹的平衡條件。

AVL 樹的平衡條件： 對於 AVL 樹中的任何節點，其左右子樹的高度差的絕對值不能超過 1。

我們用 Nh​ 來表示高度為 h 的 AVL 樹所包含的最少節點數。

• 高度為 0 的 AVL 樹 (h=0)：

  • 只有一個根節點。
  • N0​=1

• 高度為 1 的 AVL 樹 (h=1)：

  • 根節點有兩個子節點（可以是左子樹高度 0，右子樹高度 0）。

  • N1​=1(root)+N0​+N0​=1+1+1=3 (或 1個根節點 + 1個高0的子樹)

  • 最少節點數的樹，其中一個子樹的高度為 h−1，另一個子樹的高度為 h−2（為了保持平衡且節點最少）。

  • N1​=1(root)+N0​(height h−1)+N−1​(impossible)=1+N0​=1+1=2 (只有一個子樹，高0)

  • 實際上，高度為 1 的 AVL 樹最少需要 2 個節點（根節點和一個子節點）。例如：

    R (height 1) / N (height 0)

  • 另一個推導方式是 Nh​=Nh−1​+Nh−2​+1，這個遞迴式通常用於計算最少節點數。

  • N0​=1

  • N1​=N0​+N−1​+1 (這裡 N−1​ 定義為 0 或 1 節點。如果定義為 0，則 N1​=1+0+1=2)

  • 讓我們採用經典的費波那契數列關係來定義最少節點數：

  • N0​=1 (root only)

  • N1​=2 (root + 1 child)

  • Nh​=Nh−1​+Nh−2​+1 (當高度為 h 時，根節點 + 左子樹的高度為 h−1 + 右子樹的高度為 h−2 (或反之))

現在我們開始計算：

• N0​=1
• N1​=2
• N2​=N1​+N0​+1=2+1+1=4
• N3​=N2​+N1​+1=4+2+1=7
• N4​=N3​+N2​+1=7+4+1=12
• N5​=N4​+N3​+1=12+7+1=20

所以，高度為 5 的 AVL 樹最少有 20 個節點。

The final answer is B​