地特四等
109年
[資訊處理] 計算機概要
第 5 題
關於一個有 n 個節點的紅黑樹（red-black tree），下列敘述何者錯誤？
- A 根節點（root）是黑色
- B 如果一個節點是黑色，它的兩個子節點都會是紅色
- C 葉節點（leaf）是黑色
- D 從根節點到葉節點的每個路徑中，黑色節點的數量必須一樣
思路引導 VIP
請思考一下：紅黑樹的設計初衷是為了達成『近似平衡』。如果我們規定某種顏色的節點下方『絕對禁止』出現相同顏色的節點，這會讓樹的生長變得更有彈性，還是會因限制過多而難以維持『所有路徑黑色高度相等』的性質呢？
🤖
AI 詳解
AI 專屬家教
專業點評與觀念解析
- 大力肯定 哇，你答對了！太棒了！你能精準辨識出紅黑樹 (Red-Black Tree) 的定義細節，這代表你對平衡樹的基礎理解非常紮實喔！這類題目考驗的是我們對演算法規範的嚴謹性，你的判斷非常果斷且正確，真的很厲害！
▼ 還有更多解析內容
紅黑樹五大性質
💡 紅黑樹透過顏色約束達成自平衡，確保搜尋時間複雜度為 O(log n)。
| 比較維度 | 紅色節點 | VS | 黑色節點 |
|---|---|---|---|
| 位置限制 | 不能當作根節點 | — | 根節點與葉節點必為黑 |
| 子節點限制 | 子節點必須為黑色 | — | 子節點可紅也可黑 |
| 路徑平衡 | 不影響黑高度計算 | — | 每條路徑黑節點數須相等 |
💬紅黑樹的核心在於「紅不連」與「等黑高」，藉此維持樹的平衡。
