Learning Objectives
- 說明 2-3-4 樹的三種節點，以及為什麼它的所有葉節點永遠在同一層
- 追蹤 2-3-4 樹由上往下分裂 4-節點的插入，說明樹只會在根分裂時長高
- 列出紅黑樹的五條性質，把一棵紅黑樹換算成對應的 2-3-4 樹
- 說明紅黑樹插入時新節點塗紅的理由，以及「叔叔紅色就變色、叔叔黑色就旋轉」各對應 2-3-4 樹的什麼動作
- 比較 AVL 樹與紅黑樹，說明 C++ std::map 與 Java TreeMap 的底層結構
換個想法：讓一個節點放好幾個鍵
上一課的 AVL 樹用「左右高度最多差 1」維持平衡，代價是插入、刪除時常常要旋轉。這一課換一個角度：
如果一個節點可以放 1～3 個鍵，樹就能做到所有的葉節點永遠在同一層，完美平衡。
這種樹叫 2-3-4 樹。它很好理解，但直接寫成程式很麻煩，所以實務上把它「翻譯」成二元樹，每條連結塗上紅色或黑色，就是紅黑樹（red-black tree）。
歷史上，Bayer 在 1972 年提出「對稱二元 B 樹」（symmetric binary B-tree），就是用二元樹表示這種多鍵節點；1978 年 Guibas 與 Sedgewick 用紅、黑兩種顏色描述它，紅黑樹這個名稱由此而來。
這一課先看 2-3-4 樹怎麼插入，再看紅黑樹的規則、兩者怎麼一一對應，最後看紅黑樹的插入。
2-3-4 樹：三種節點
2-3-4 樹的節點依鍵的個數分成三種，名稱是「子節點的個數」：
| 節點 | 鍵 | 子節點 | 範例 |
|---|---|---|---|
| 2-節點 | 1 個 | 2 個 | [20]：左邊 < 20 < 右邊 |
| 3-節點 | 2 個 | 3 個 | [20 | 40]：左 < 20 < 中 < 40 < 右 |
| 4-節點 | 3 個 | 4 個 | [20 | 40 | 60] |
搜尋和二元搜尋樹一樣：在節點裡找到目標落在哪兩個鍵之間，往對應的子節點走。
插入一律放在葉節點。葉節點如果已經是 4-節點（3 個鍵），就沒有位置了，要先分裂：
[ ... ] [ ... 40 ... ]
| 分裂 / \
[20 | 40 | 60] ───> [20] [60]
中間的鍵 40 往上送到父節點，剩下的兩個鍵各自變成 2-節點。父節點如果也滿了怎麼辦？常見的做法是由上往下：從根往下走的時候，路上遇到 4-節點就先分裂，這樣父節點一定有空位接住送上來的鍵。
樹只有在根是 4-節點、被分裂時才長高一層：中間的鍵成為新的根。所有的葉節點同時往下一層，所以它們永遠在同一層。
2-3-4 樹的插入：路上遇到 4-節點先分裂
從只有 10 的樹開始，依序插入 30、20、40、50、60。插完 20，根是 [10 | 20 | 30]；插入 40 時根是 4-節點，先分裂：20 成為新的根，樹長高一層，再把 40 放進右邊的葉節點。插入 60 時，往下走的下一站 [30 | 40 | 50] 是 4-節點，先分裂，40 送上根，60 才放進去。
紅黑樹：用顏色畫出 2-3-4 樹
2-3-4 樹的節點有三種大小，直接寫程式要處理各種情況，也浪費空間。紅黑樹的做法是：每個 2-3-4 節點畫成一小群二元樹節點， 其中一個是黑色的「中心」，同一個節點裡的其他鍵是掛在它下面的紅色節點：
| 2-3-4 節點 | 紅黑樹 |
|---|---|
[20] |
黑色 20 |
[20 | 40] |
黑色 20、右子節點紅色 40（或黑色 40、左子節點紅色 20） |
[20 | 40 | 60] |
黑色 40，左右子節點是紅色 20、紅色 60 |
所以紅色節點代表「我和父節點其實在同一個 2-3-4 節點裡」。這個對應寫成規則，就是紅黑樹的五條性質：
- 每個節點不是紅色就是黑色
- 根是黑色
- 每個空的子節點（叫 NIL，視為葉）是黑色
- 紅色節點的子節點一定是黑色，也就是不能有兩個紅色節點相連
- 從任何一個節點往下走到每一個 NIL，經過的黑色節點數量都相同，這個數叫黑高度（black height）
第 4 條對應「一個 2-3-4 節點最多 3 個鍵」（一個黑色加最多兩個紅色）；第 5 條對應「2-3-4 樹的葉節點都在同一層」，因為每個 2-3-4 節點剛好貢獻一個黑色節點。
樹高的保證：最短的路徑全是黑色節點，最長的路徑紅黑交錯，最多是最短的 2 倍。n 個節點的紅黑樹，高度不超過 2 log₂(n + 1)，搜尋 O(log n)。
檢查一棵樹是不是紅黑樹
black_height 用後序檢查第 4、5 條：紅色節點不能有紅色子節點；左右兩邊算出來的黑高度要相同。原本的樹（根 20，左 10，右 40 帶著紅色的 30、50）黑高度是 2。把 40 改成紅色，40 和 30 連續紅色，回傳 -1；改回來後把 10 改成紅色，根的左邊黑高度變成 0、右邊是 1，也回傳 -1。
把紅黑樹換算成 2-3-4 樹
fill 從每個黑色節點出發，把它的紅色子節點併進同一個 2-3-4 節點，再對下面的黑色節點遞迴。根 40 帶著紅色的 20、60，合成 [20 | 40 | 60]；10 帶著紅色的 5 合成 [5 | 10]；80 帶著兩個紅色子節點合成 [70 | 80 | 90]。紅黑樹有 4 層，換算出來的 2-3-4 樹只有 2 層，剛好等於黑高度。
想一想：2-3-4 樹與紅黑樹的對應
2-3-4 樹裡一個有 3 個鍵的節點，有幾個子節點（不是葉節點的情況）？
一棵紅黑樹：根是黑色 30，左子節點是紅色 10（10 的兩個子節點是黑色 5、黑色 20），右子節點是黑色 40。對應的 2-3-4 樹長什麼樣子？
用「檢查一棵樹是不是紅黑樹」範例的 black_height 檢查下面這棵樹：根是黑色 20，兩個子節點是紅色 10 和紅色 30。會印出什麼？
紅黑樹的插入：塗紅、看叔叔
插入時先照二元搜尋樹的規則把新節點放到葉的位置，而且一律塗成紅色：紅色節點不會改變任何路徑上的黑色節點數，第 5 條不會被破壞。 唯一可能出問題的是第 4 條：父節點剛好也是紅色，出現兩個紅色相連。這時看叔叔（父節點的兄弟）的顏色：
| 情況 | 紅黑樹的動作 | 在 2-3-4 樹裡的意思 |
|---|---|---|
| 父節點是黑色 | 什麼都不用做 | 新鍵放進一個還有空位的節點 |
| 父節點紅、叔叔也紅 | 變色：父、叔改黑，祖父改紅，再從祖父往上檢查 | 祖父所在的節點已經是 4-節點，放不下了：分裂，中間的鍵（祖父）往上送 |
| 父節點紅、叔叔黑（空的也算黑），新節點在外側 | 在祖父旋轉一次，父節點改黑、祖父改紅 | 3-節點多了一個鍵變成 4-節點，把中間的鍵擺成黑色 |
| 父節點紅、叔叔黑，新節點在內側 | 先在父節點旋轉，轉成外側，再照上一列處理（雙旋轉） | 同上 |
| 最後根是紅色 | 根改成黑色 | 根分裂後中間的鍵成為新根，樹長高一層 |
外側、內側和 AVL 一樣：父節點是祖父的左子節點、新節點也在左邊，就是外側（LL）；方向相反就是內側（LR）。
變色可能讓祖父和曾祖父又連續紅色，所以要繼續往上檢查；旋轉之後那一段的頂端是黑色，就結束了。所以一次插入最多旋轉 2 次，變色最多往上 O(log n) 層。
範例用遞迴寫：insert 回程時對每一層呼叫 fix(h)，把 h 當成祖父，檢查它底下兩層有沒有紅色相連。
紅黑樹插入：變色與旋轉
依序插入 10、30、20、40、50，和上面 2-3-4 樹的範例前幾個鍵相同。插入 20 時，20 在 30 的左邊、30 在 10 的右邊，屬於內側（RL）：先在 30 右旋，再在 10 左旋並交換顏色，20 成為黑色的根。插入 40 時叔叔 10 是紅色，只要變色，根 20 被改紅後再塗回黑色，黑高度加 1，對應 2-3-4 樹的根分裂。插入 50 時叔叔是空的（黑色），在 30 左旋一次。root 要等最外層的 insert 回傳才會換人。
刪除、和 AVL 的比較、內建容器
刪除的調整比插入複雜，這裡只說明想法，不實作：
- 照二元搜尋樹的方法刪除（兩個子節點時用後繼者或前驅頂替），最後真正被拿掉的節點最多只有一個子節點
- 拿掉的是紅色節點：黑高度不變，結束
- 拿掉的是黑色節點：那條路徑少了一個黑色，第 5 條被破壞。修正時看兄弟節點的顏色與它的子節點，分成四種情況，用變色與旋轉補回來
在 2-3-4 樹裡，這相當於節點被拿空了：兄弟有多的鍵就借一個過來（對應旋轉），兄弟也只有一個鍵就和它合併（對應變色，可能讓父節點也少一個鍵，問題往上傳）。 整個刪除最多旋轉 3 次。
AVL 樹和紅黑樹怎麼選？
| AVL 樹 | 紅黑樹 | |
|---|---|---|
| 平衡條件 | 左右高度最多差 1 | 五條顏色規則 |
| 樹高上限 | 約 1.44 log₂n | 約 2 log₂n |
| 插入的旋轉 | 最多 2 次 | 最多 2 次 |
| 刪除的旋轉 | 最多 O(log n) 次 | 最多 3 次 |
| 每個節點多存 | 高度（整數） | 顏色（1 個位元就夠） |
AVL 樹比較矮，搜尋略快；紅黑樹的插入、刪除調整比較少。兩者的操作都是 O(log n)。
內建的有序容器：Java 的 TreeMap 官方文件第一句就寫明是「以紅黑樹實作」（TreeSet 內部用 TreeMap），並保證 get、put、remove 是 log(n)。
C++ 標準只規定 std::map、std::set 的操作是 O(log n)，沒有指定用哪種樹；GCC 的 libstdc++ 和 LLVM 的 libc++ 都是用紅黑樹實作。
Python 標準函式庫沒有平衡樹，需要時常用排好序的串列配 bisect。
想一想：插入的調整
紅黑樹插入一個新節點後，它的父節點是紅色、叔叔也是紅色。下一步要做什麼？
用「紅黑樹插入」範例的程式，把 1～10 依序插入一棵空的紅黑樹。印出的樹高與黑高度是什麼？
下列關於內建有序容器的敘述，哪一個正確？
實作：變色
下面的紅黑樹插入已經寫好旋轉的情況，只缺「父節點和叔叔都是紅色」的變色。請在 fix 裡補上三行：把 h 改成紅色、h 的兩個子節點改成黑色。測試依序插入 10、20、30、15、25、5、1、27，每次印出前序走訪與顏色；沒有變色時，從插入 15 開始就會和預期輸出不同。
重點整理
- 2-3-4 樹：節點有 1～3 個鍵；插入一律放進葉節點，路上遇到 4-節點先分裂、中間鍵往上送；只有根分裂時樹才長高，所以葉節點永遠在同一層
- 紅黑樹是 2-3-4 樹的二元樹寫法：黑色節點＋它的紅色子節點＝一個 2-3-4 節點
- 五條性質：非紅即黑、根是黑、NIL 是黑、紅色不能相連、每條路徑黑色節點數相同；樹高不超過 2 log₂(n + 1)
- 插入：新節點塗紅；父節點紅時看叔叔，叔叔紅就變色（＝分裂），叔叔黑就旋轉（外側一次、內側兩次）；最後根塗黑（＝長高一層）
- 插入最多旋轉 2 次，刪除最多 3 次；AVL 比較矮，紅黑樹調整比較少
- Java
TreeMap／TreeSet以紅黑樹實作；C++std::map／std::set常見的實作也是紅黑樹
下一課：B 樹與 B+ 樹。2-3-4 樹其實就是最小的 B 樹；把一個節點能放的鍵增加到幾百個，樹就矮到只要讀幾次磁碟，資料庫的索引就是這樣做的。