有一個二元搜尋樹（Binary Search Tree），每個節點的鍵值都不同，下列敘述何者正確？

題目

有一個二元搜尋樹（Binary Search Tree），每個節點的鍵值都不同，下列敘述何者正確？ A. 最大的鍵值有可能在根節點 B. 樹根節點的鍵值必定大於左右子樹節點的鍵值 C. 是一種平衡樹（Balanced Tree） D. 假設有n 個節點，則空間（Space complexity）複雜度平均為O(log n)

官方答案

• 答案：A. 最大的鍵值有可能在根節點

解析

二元搜尋樹的性質是：任一節點的左子樹鍵值均小於該節點，右子樹鍵值均大於該節點。若最大值放在根節點，其餘所有節點都落在左子樹且皆小於根，仍完全符合定義，故 A 正確。B 錯在根對右子樹應為小於而非大於。BST 不具平衡保證，依插入順序可能退化為鏈狀，尋找最差為 O(n)；所需空間與節點數成正比為 O(n)，並非 O(log n)。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。