[理工] 紅黑樹

[jouen (呵呵)]

https://i.imgur.com/TMCf9D4.jpg

第一個圖插入10之後，2、8有一定要變黑嗎？ 如果2、8維持紅色，應該也是符合紅黑樹
的規則吧？而且對應的2-3-4樹高度反而比較低不是嗎？

可是為什麼圖中要將2、8變為黑色？ 還是我有理解錯的地方呢

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.169.125
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1506513491.A.9D1.html
推 sarsman: Searching 10時，路徑上的點有兩個紅子node要變色沒錯
→ sarsman: 變色後5變紅，Insert完10並做完Rotation後才再把5變回黑
推 s1020824: 插入完11後不用
→ s1020824: 是等下一次插入時先走一次路徑
→ s1020824: 如果路徑上有一父點兩紅子點的話就要color change
→ s1020824: 確定路上都沒有違規以後再插入
抱歉我說錯了，是插入10之後，第二張圖是insert10
※ 編輯: jouen (27.52.169.125), 09/27/2017 20:21:48
噓 s1020824: 2.8是在10插入前就變黑了
→ s1020824: 這時5會從黑變紅
→ s1020824: 先變完確認路徑上沒問題再插入10
→ s1020824: 再rotation
→ s1020824: 最後才把5變回黑色
→ s1020824: 抱歉按到噓了qq
還是不太了解，圖1原本2.8是紅色，加入10之後，不是處理RL就好了嗎？為什麼2.8也會
變黑色？
這個結果會有什麼問題嗎？
https://i.imgur.com/mDO3IFo.jpg
※ 編輯: jouen (27.52.169.125), 09/27/2017 21:57:05
推 blackhair25: https://i.imgur.com/O9t9Pod.jpg 大概是這樣，有錯
→ blackhair25: 誤麻煩指證
請問searching遇到一父二紅子要改顏色是必要程序嗎？ 聖經版定義？ 他是為了避免向
上產生連鎖rotation的情況嗎？
※ 編輯: jouen (27.52.169.125), 09/27/2017 23:04:54
推 gary70812: 我怎麼記得可以不用改@@ 紅黑樹蠻多版本的QQ
推 gary70812: 剛剛用網頁跑出來似乎也是不用改？
推 gary70812:  https://i.imgur.com/ZqzwUA8.jpg
推 sarsman: http://i.imgur.com/wW8CgHx.jpg 楓葉本顏色修正的code
→ sarsman: http://i.imgur.com/i0QHxHn.jpg  我實際操作起來怪怪的
→ sarsman: ，感覺是right-rotate的問題，但不知道怎麼改
→ sarsman: 我一樓提的做法是洪逸版http://i.imgur.com/KwgbZAG.jpg
推 gary70812: 大大您有先進case2嗎？我剛剛自己操作一次結果是進case
→ gary70812: 2 然後case3就結束了
推 gary70812: 到case3我的z是11不是10
推 FRAXIS: 變成黑色的作法是 top-down 法 不變的是 bottom-up 法
推 outofyou: sarsman提供的top-down法,能保證2步跟4步不會同時出現？
→ outofyou: 參考csee.umbc.edu的top-down投影片,也不需要2,8的變色
→ outofyou: 其實也解釋了就算是bottom-up，也頂多動到祖父的祖父。
→ outofyou: 所以2,8不用變色是沒錯的。
推 FRAXIS: 不管是 top-down 或是 bottom-up 都有可能有O(lg n)變色
推 sarsman: 原來，我忘記在一開始else後把else if的right改成left，
→ sarsman: 謝謝g大XD
→ FRAXIS: ItoA 上面的方法是 bottom-up 的
推 FRAXIS: sarsman提供的 top-down 很奇怪 因為 top-down 的目的
→ FRAXIS: 就是保證 search path 的尾端是黑色，所以可直接插入紅點
→ FRAXIS: 所以 step 4 不可能會發生 如果 step 做的對的話
→ FRAXIS: 而且 step 2 可能會有 O(lg n) 個 rotation..
推 outofyou: F大可以提供O(lg n)變色的例子嗎？
推 gary70812: 可不可以只記一種qq
推 sarsman: Note的2跟4頂多只會做一個應該是指做過2就不會做4，可是2
→ sarsman: 的確可能需要多次的Rotation
→ sarsman: 洪逸沒提到Search path最後要黑點才能插入新的紅點，我想
→ sarsman: step4就是為了補足這點
推 FRAXIS: ftp://ftp.cs.princeton.edu/techreports/1985/006.pdf
→ FRAXIS: Figure 4，就類似這樣 因為插入就是在找 black uncle
→ FRAXIS: 沒有 black uncle 就只好一直變色上去.. (bottom-up法)
→ FRAXIS: 不要管這 paper 的內文 因為這是第三種 red-black
→ FRAXIS: 這 paper 是 top-down 且保證 amortized O(1) rotation
→ outofyou: 謝謝F大，我研究一下
推 sarsman: 謝謝F大分享，晚點回家研究
推 outofyou: 謝F大糾正，我對csee.umbc.edu的top-down投影片理解錯誤
→ outofyou: csee.umbc.edu寫的top-down會讓2,8變色,bottom-up不會。
→ outofyou: sarsman的洪逸版跟csee.umbc.edu對照後，在一次
→ outofyou: insertion中確實可能都發生2跟4。其中case3的旋轉2次
→ outofyou: 只會視為1次旋轉。他只保證新點的父或Uncle其中一個
→ outofyou: 必為黑。
推 FRAXIS: 那就看你怎麼解讀2和4的分界了
→ FRAXIS: 如果新點的父或Uncle其中一個為黑 而且知道要插入了
→ FRAXIS: 可以先插入然後直接旋轉 step 2 和 step 4 同時發生
→ FRAXIS: 我也可以先轉再插 就沒有 step 4 了..
推 lovepipi: 我想請問這個在第幾頁