Re: [理工] 紅黑樹

[FRAXIS (喔喔)]

※ 引述《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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 76.21.71.91
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1506650404.A.588.html
推 gary70812: 推
推 outofyou: 推
推 can18: 推 果然版上一堆神人
推 nat99up: 跪了...光是能理解紅黑樹的刪除我就覺得超猛了
推 tritonight: 推
推 blackhair25: 感謝整理，推
推 w181496: 推個
推 ken52011219: F大必推 駐版演算法神人
推 sarsman: 推
推 weilun911: 推