高考申論題
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 紅子（可左傾或右傾）；2-node 直接轉黑。接著將拆解後的節點依照原樹的指標關係連接，最後確認根節點為黑色且所有路徑的黑高度一致即可。
小題 (二)
首先，插入（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 樹繪製成紅黑樹。繪圖時務必標示清楚節點間的父子關係與紅黑顏色。
2-3-4 樹轉紅黑樹
💡 2-3-4 樹節點與紅黑樹具等價映射，轉換關鍵在於黑平衡的拆解。
| 比較維度 | 2-3-4 樹節點類型 | VS | 紅黑樹對應結構 |
|---|---|---|---|
| 2-node | 1 個鍵值，2 個子節點 | — | 單一黑色節點 |
| 3-node | 2 個鍵值，3 個子節點 | — | 1 黑 1 紅 (紅可位於黑之左或右側) |
| 4-node | 3 個鍵值，4 個子節點 | — | 1 黑位於中間，2 紅位於兩側 (左右對稱) |
💬2-3-4 樹的一個節點對應紅黑樹的一組黑色核心與其擴展的紅色節點。
