作者FRAXIS (喔喔)
看板Grad-ProbAsk
標題Re: [理工] 紅黑樹
時間Fri Sep 29 20:18:59 2017
※ 引述《FRAXIS (喔喔)》之銘言：
: 刪除其實也類似，先找到 safe node ，以下變色，然後旋轉，
: 只是 safe node 的條件稍微複雜一些，有人想知道的話我再寫
: 一篇吧。
在刪除的時候，會先需要從 root 往下開始 traverse 去找要刪除的節點，如果
要刪除的節點有兩個子節點，那就把刪除節點的 successor 的資料複製到要刪除
的節點上，接著再把 successor 刪除，所以在不失一般性的情況下，可以假設
要被刪除的節點只有一個子節點。
（在實務上不能把 successor 的資料複製到要刪除的點上，然後把 successor
刪除，原因是可能有指標(iterator)指向 successor ，這樣作會導致這些指標
莫名其妙的就 invalid 了，所以需要多一些步驟，這也是為什麼 CLRS 上的刪除
比較複雜的原因）
為了討論方便，我們把 root 到要刪除節點的搜尋路徑叫做 p ，而 safe node
就是在 p 上，距離刪除節點最近的紅色點，或是子代和孫代有紅色點的黑點。
如果 p 上沒有這種點的話，root 就是 safe node 。
當節點被刪除時，如果刪除節點有非 sentinel 的子節點，就把非 sentinel 子節
點上移，不然就把 sentinel 子節點上移，此時有幾種情況：
刪除節點顏色 子節點顏色
紅 紅 不存在
紅 黑 子節點直接上移，不違反紅黑樹性質
黑 紅 子節點上移之後變為黑色，不違反紅黑樹性質
黑 黑 子節點上移，但是因為黑色點減少，違反紅黑樹性質
因為只有最後一個情形才違反紅黑樹性質，所以我就只討論這情況。在這個時候
因為刪除節點的另一個子節點是 sentinel ，而上移的節點又是黑色，根據紅黑
樹的限制，上移的節點必為 sentinel 。換句話說，只有刪除黑色的葉節點才可
能違反紅黑樹性質。
接下來可以把 p 畫出來，有幾種可能：
情況 1： safe node 是紅點且有黑子黑孫
safe node 刪除點
root - .. - 紅 - 黑 - 黑 - 黑 - 黑 - .. 黑 - (黑) - 黑 (sentinel)
| | | | | | |
黑 黑 黑 黑 黑 黑 黑 (sentinel)
子 子 子 子 子
黑 黑 黑 黑 黑
孫 孫 孫 孫 孫
情況 2： safe node 是紅點且有紅孫
情況 3： safe node 是黑點且有紅子或紅孫
就不畫了。
而調整的方式就是從 safe node 以下，先變色。
情況 1 ，變完色就成為
safe node
root - .. - 黑 - 黑 - 黑 - 黑 - 黑 - .. 黑 - 黑 (sentinel)
| | | | | |
紅 紅 紅 紅 紅 紅
這樣就變成合法的紅黑樹了。而情況二和三則是變完色之後要再旋轉，旋轉的判斷
有三個 case ，詳情請參考 CLRS 。
: 這技巧也被用在 WAVL tree 上，有興趣的可以研究。
: https://en.wikipedia.org/wiki/WAVL_tree
WAVL 在 Goodrich and Tamassia 的 Algorithm Design and Applications
有詳細介紹。
WAVL 的複雜度與紅黑樹一模一樣，只需要 O(1) 旋轉，
rebalance 是 amortized O(1)。
稍有不同的地方是在旋轉次數，插入時 WAVL 和紅黑樹
都頂多轉兩次，但是刪除時紅黑樹最多轉三次，WAVL
最多只會轉兩次。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 76.21.71.91
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1506687541.A.2EB.html
推 can18: 請問大大 我自己看一些紅黑樹 都是用 parent 及 uncle 的 09/29 21:27
→ can18: 情形討論 09/29 21:27
→ can18: 但大大似乎沒提到 uncle 是版本不同嗎 09/29 21:27
→ FRAXIS: 旋轉的時候一定會需要考慮 parent 和 uncle 09/30 08:06
→ FRAXIS: 但是這部份在 CLRS 上面有詳細說明了 就不重述 09/30 08:12
→ FRAXIS: 我只是提供一個可以直接找到會旋轉的節點的方法 09/30 08:12