※ 引述《jouen (呵呵)》之銘言：
: https://i.imgur.com/TMCf9D4.jpg
: 第一個圖插入10之後，2、8有一定要變黑嗎？ 如果2、8維持紅色，應該也是符合紅黑樹
: 的規則吧？而且對應的2-3-4樹高度反而比較低不是嗎？
: 可是為什麼圖中要將2、8變為黑色？ 還是我有理解錯的地方呢
認真的回一下這篇文章來討論各類紅黑樹。
我先給個摘要的結果：
方法 時間 空間 #Pass 旋轉 變色
Top-down O(lg n) O(1) 1 O(lg n) O(lg n)
Bottom-up O(lg n) O(1) 2 O(1) O(lg n) Amortized O(1)
Top-down-Tarjan O(lg n) O(1) 1 O(lg n) O(lg n) Amortized O(1)
Amortized O(1)
其中 Bottom-up 的空間複雜度是指沒有 parent pointer 的情況。
有 parent pointer 很簡單是 O(1) ，但是沒有 parent pointer 還
是可以 O(1) 的
這三種方法的簡介如下：
1. Top-down: 紅黑樹原始論文上的方法，想知道細節的可以參考
Mark Allen Weiss 的資料結構。這方法不需要 back track，
所以可以容易的用迴圈實作但是最多會有 O(lg n) 個旋轉。
2. Bottom-up: Tarjan 參考 half-balanced tree 設計出來的方
法，想知道細節的可以參考 CLRS 。因為需要 backtrack ，
所以用遞迴或是用迴圈 + parent 指標實作。這方法插入最
多只需要兩次旋轉，刪除最多三次旋轉。而且這方法可以被證
明，當插入或是刪除的節點確定後，之後的rebalance （變色 + 旋轉）
複雜度是 amortized O(1)！這個性質對 C++ 函式庫很重要，
因為標準規定在 set 的 insert 和 erase 可以提供 hint ，
如果 hint 是正確的話，時間複雜度必須是 amortized O(1)。
換言之，如果把已排序元素循序插入到 set 中，只要有提供
對的 hint ，插入 n 個元素只需要 O(n) 時間。也因為這個
要求，AVL 是不能拿來實作 C++ 的 set 的。
3. Tarjan's Top-down: 這是另一種 top-down 的方法，但是旋
轉和變色的數量是 amortized O(1) 的 [1]。
以下我稍微介紹一下我是怎麼理解 bottom-up 的插入法的。
在 Horowitz 和 Sahni 的資料結構書上，介紹 AVL 的插入時，
有用到一個性質是，如果需要旋轉，那麼旋轉只會發生在一個節
點上（可能是單旋或是雙旋），而且從此點（Tarjan 稱之為
safe node）往下到插入的地方，就只是單純調整 balance factor 而已。
可以用同樣的方法來處理紅黑樹，先找到要旋轉的點，此點以下
就只是單純的變色，然後最後旋轉即可。
在插入的時候，會先需要從 root 往下開始 traverse 去找需要插入的
位置，為了討論方便，我們把 root 到插入位置的搜尋路徑叫做 p ，
而新插入節點設定為紅色。safe node 就是在 p 上，距離插入節點最近，
至少有一個黑子節點的黑點，如果沒有這種點的話，那就把 root 當
safe node。
因為插入的點是紅色，只有插入點的父節點是紅色時才會違反紅黑樹條件，所以接
下來就只討論插入點的父節點是紅色的情況。
雖然條件有點複雜，但是如果把 p 畫成一條直線，不在 p 上的分叉點畫成垂直線，
那麼 p 必定會長成這樣
情況 1： safe node 在 p 上的下一個點是黑點。
safe node 插入點
root - .. - 黑 - 黑 - 紅 - 黑 - 紅 - .. 紅 - (紅) - 黑 (sentinel)
| | | | | | |
黑/紅 紅 黑 紅 黑 黑 黑 (sentinel)
也就是，在 p 上，safe node 以下，必定是紅點接著有兩個紅子節點的黑點相繼出現。
另一種情況是
情況 2： safe node 在 p 上的下一個點是紅點。
safe node 插入點
root - .. - 黑 - 紅 - 黑 - 紅 - .. 紅 - (紅) - 黑 (sentinel)
| | | | | |
黑 黑 紅 黑 黑 黑 (sentinel)
而調整的方式就是從 safe node 以下，先變色。
情況 1 ，變完色就成為
safe node 插入點
root - .. - 黑 - 紅 - 黑 - 紅 - 黑 - .. 黑 - (紅) - 黑 (sentinel)
| | | | | | |
黑/紅 黑 紅 黑 紅 紅 黑 (sentinel)
這樣就變成合法的紅黑樹了。而情況二則是變完色之後要再旋轉，旋轉的判斷
有兩個 case ，詳情請參考 CLRS 。
所以 bottom-up 的插入，第一個 pass 先找到 safe node ，
然後從 safe node 以下進行第二個 pass 來變色，最後再旋轉，
就可以使用迴圈來實作，所以就算沒有 parent pointer 也可以
只使用 O(1) 空間。
刪除其實也類似，先找到 safe node ，以下變色，然後旋轉，
只是 safe node 的條件稍微複雜一些，有人想知道的話我再寫
一篇吧。
這技巧也被用在 WAVL tree 上，有興趣的可以研究。
https://en.wikipedia.org/wiki/WAVL_tree
除了這三種紅黑樹之外，還有一些相關的資料結構。
AA tree
https://en.wikipedia.org/wiki/AA_tree
用二元樹模擬 2-3 tree，可以參考 Mark Allen Weiss 的資料結構。
Left-leaning red–black tree
https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree
用二元樹模擬 2-3 tree 或是 2-3-4 tree。
可以參考 Sedgewick and Wayne 的 Algorithms。
（Sedgewick 是紅黑樹的發明人之一）
[1] Robert Endre Tarjan
Efficient Top-Down Updating of Red-Black Trees