高考申論題
109年
[資訊處理] 資料結構
第 一 題
📝 此題為申論題，共 2 小題
小題 (一)
在一棵高度為 h(h=0,1,2,…)的 AVL tree 中：⑴高度為6之 AVL tree 最多可能有幾個 nodes？最少可能有幾個 nodes？（假設 root 之 h=0）（6分） ⑵假設此樹共有45個 nodes。請問此 AVL tree 可能最高之高度及最矮之高度各為何？（6分）
思路引導 VIP
首先確認題目對「高度」的定義（root 的 h=0）。接著利用 AVL Tree 的極端特性：最滿的情況為完滿二元樹（利用公式 $2^{h+1}-1$ 計算最大節點數），最稀疏的情況為費波那契樹（利用遞迴公式 $N(h) = N(h-1) + N(h-2) + 1$ 計算最小節點數）。求給定節點數下的高度極值時，反向代入上述兩公式的邊界範圍即可。
小題 (二)
請將下列數字{17, 60, 24, 5, 7}逐步插入圖1的 AVL tree 中，並平衡之。（12分）
思路引導 VIP
解答此題需熟練 AVL Tree 的插入與平衡機制。核心思路為：每次插入新節點後，由下往上回溯計算各祖先節點的平衡因子（BF）。若發現某節點 |BF| > 1，則依據新節點的插入路徑判定為 LL、RR、LR 或 RL 型失衡，並精準執行相應的旋轉操作。作答時務必詳細列出每一步的插入位置、失衡節點、旋轉類型及旋轉後的樹狀結構。