地特三等申論題
108年
[資訊處理] 資料結構
第 一 題
📖 題組：
下圖為一棵 2-3-4 樹。 （圖中結構：根節點 [40, 62, 83]，其子節點由左至右分別為 [10, 20, 31], [45, 55], [70, 78], [90, 92]）
下圖為一棵 2-3-4 樹。 （圖中結構：根節點 [40, 62, 83]，其子節點由左至右分別為 [10, 20, 31], [45, 55], [70, 78], [90, 92]）
📝 此題為申論題，共 2 小題
小題 (一)
請畫出對應的紅黑樹（red-black tree）。請參閱上題紅黑樹節點的標示說明。（6 分）
思路引導 VIP
將 2-3-4 樹轉換為紅黑樹的核心在於節點的拆解：4-node 必定拆成 1黑2紅（中間值提升為黑），3-node 拆成 1黑1紅（可左傾或右傾）。接著將拆解後的各子樹，依據二元搜尋樹的大小關係，掛載到父節點對應的指標上即可完成轉換。
小題 (二)
首先，插入（insert）33；接著，刪去（delete）78。請分別畫出對應的 2-3-4 樹與紅黑樹。（14 分）
思路引導 VIP
遇到 2-3-4 樹的題型，先回憶其與紅黑樹的等價關係。插入時採用 Top-Down 遇 4-node 提早分裂的原則；刪除時確認目標節點刪去資料後是否發生 Underflow（低於 1 個 key），若無則直接移除即可。最後利用「2-node 轉黑、3-node 轉一黑一紅」的規則將最終樹形轉換為紅黑樹。