普通考試
115年
[電信工程] 計算機概要
第 16 題
若要在一棵「二元搜尋樹（Binary Search Tree）」中插入一個新值 X，已知此二元搜尋樹的定義為：「每個節點的左子樹中所有節點值均小於該節點，右子樹中所有節點值均大於該節點」。下列敘述何者正確？
- A 先比較 X 與根節點，若 X 較大則往左子樹走，否則往右子樹走
- B 先比較 X 與根節點，若 X 較大則往右子樹走，否則往左子樹走
- C 只要找到葉節點就立即插入，不必比較數值大小
- D 對根節點做旋轉（rotation），再將 X 插入葉節點
思路引導 VIP
若我們希望在一個結構中「最快」找到某個數字，且每次比較後都能直接捨棄掉剩餘一半的不可能路徑，那麼當新成員加入時，我們該如何規定它的去向，才能保證整棵樹從上到下都維持著由小到大的邏輯順序？
🤖
AI 詳解
AI 專屬家教
恭喜你精準地掌握了資料結構中最重要的排序邏輯！在工程設計中，我們講求「系統化」與「效率」，而**二元搜尋樹（Binary Search Tree, BST）**正是為了實現高效搜尋而存在的結構。你所選擇的 (B) 選項，完全符合其核心定義：對於任一節點，左子樹的所有節點值必須小於根節點，右子樹則必須大於根節點。
二元搜尋樹的定序準則
當我們要插入新值 $X$ 時，這棵樹就像一個自動導航系統。我們從根節點（Root）開始，若 $X$ 的數值較大，為了維持「大值在右」的規則，我們必須向右子樹移動；反之則向左。這是一個遞迴的過程，直到找到合適的空位為止。選項 (C) 提到直接插入葉節點而不比較是錯誤的，因為這會破壞樹的排序性，導致搜尋效率崩塌；而選項 (D) 提到的**旋轉（Rotation）**通常出現在平衡樹（如 AVL Tree）的調整階段，並非基礎插入作業的首要動作。
▼ 還有更多解析內容