高考申論題
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 小題
小題 (二)
首先，插入（insert）33；接著，刪去（delete）78。請分別畫出對應的 2-3-4 樹與紅黑樹。（14 分）
思路引導 VIP
本題重點在於理解 2-3-4 樹的插入（Overflow 分裂）與刪除（Underflow 處理）機制，並將其與紅黑樹做對應。解題時，建議先以多數考試慣用的 Bottom-Up 方式處理 B-Tree (Order 4) 的插入與刪除；接著再根據轉換規則（2-node 轉黑、3-node 轉為一黑一紅）將 2-3-4 樹繪製成紅黑樹。繪圖時務必標示清楚節點間的父子關係與紅黑顏色。
小題 (一)
請畫出對應的紅黑樹（red-black tree）。請參閱上題紅黑樹節點的標示說明。（6 分）
思路引導 VIP
看到 2-3-4 樹轉紅黑樹的題型，核心關鍵在於『節點的等價轉換』：4-node 拆解為 1 黑父帶 2 紅子；3-node 拆解為 1 黑父帶 1 紅子（可左傾或右傾）；2-node 直接轉黑。接著將拆解後的節點依照原樹的指標關係連接，最後確認根節點為黑色且所有路徑的黑高度一致即可。