初考-統計資料處理大意107 年第 45 題單選題
假設六個鍵（key）插入（insert）一個不平衡的二元搜索樹（Unbalanced Binary Search Tree）的順序如下：4，6，2，5，3，8。下列那一項敘述是正確的？①在這個二元搜索樹搜尋一個鍵（key）需要檢查 2 或 3 個節點（node）②這個二元搜索樹具有同等數量的內部（internal）和葉（leaf）節點（node）③在這個二元搜索樹插入（insert）新鍵（key）7 不需增加另一層次（level）
D正確答案
畫出二元搜尋樹結構即可秒解！依序插入後，內部節點與葉節點皆為3個，搜尋根節點只需檢查1次，插入7會新增第4層。
為什麼答案是 D
僅②正確。建構出的樹中，內部節點(有子節點者)為4、2、6共3個；葉節點(無子節點者)為3、5、8共3個，兩者數量相等。
載入中…
完整詳解
Pro · 無限重點 畫出二元搜尋樹結構即可秒解！依序插入後，內部節點與葉節點皆為3個，搜尋根節點只需檢查1次，插入7會新增第4層。
依序畫樹：4為根，左2右6；2右接3，6左接5右接8。葉節點(3,5,8)共3個，內部節點(4,2,6)共3個，兩者相等，故僅②正確。
逐選項分析
A✕
包含錯誤的①與③。搜尋根節點(4)只需檢查1個節點，故①錯；插入7會放在8的左子節點，產生第4層，故③錯。
B✕ 陷阱
包含錯誤的①。考生容易忽略搜尋「根節點」時只需檢查1次，誤以為所有搜尋都至少要檢查2次。
C✕
包含錯誤的③。插入7時，因為7>4、7>6、7<8，會成為8的左子節點，導致樹的深度從3層增加到4層。
D✓ 正確
僅②正確。建構出的樹中，內部節點(有子節點者)為4、2、6共3個；葉節點(無子節點者)為3、5、8共3個，兩者數量相等。
本題二元搜尋樹結構分析
| 層次 (Level) | 節點數值 | 節點類型 | 搜尋所需檢查次數 |
|---|
| Level 1 | 4 | 內部節點 (Root) | 1次 |
| Level 2 | 2, 6 | 內部節點 | 2次 |
| Level 3 | 3, 5, 8 | 葉節點 (Leaf) | 3次 |
| Level 4 (若插入7) | 7 | 葉節點 (Leaf) | 4次 |
敘述①稱搜尋需要檢查「2或3個」節點，考生若只想到搜尋中下層節點，極易忽略搜尋「根節點(Root)」時只需要檢查1個節點，進而誤判①為正確。 
