Re: [理工] 紅黑樹

作者: FRAXIS (喔喔)   2017-09-29 20:18:59
※ 引述《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
最多只會轉兩次。
作者: can18 (18號)   2017-09-29 21:27:00
請問大大 我自己看一些紅黑樹 都是用 parent 及 uncle 的情形討論但大大似乎沒提到 uncle 是版本不同嗎
作者: FRAXIS (喔喔)   2017-09-30 08:06:00
旋轉的時候一定會需要考慮 parent 和 uncle但是這部份在 CLRS 上面有詳細說明了 就不重述我只是提供一個可以直接找到會旋轉的節點的方法

Links booklink

Contact Us: admin [ a t ] ucptt.com