[理工] 紅黑樹

看板Grad-ProbAsk作者 (呵呵)時間8年前 (2017/09/27 19:58), 8年前編輯推噓21(22推 1噓 38→)
留言61則, 7人參與, 最新討論串2/4 (看更多)
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
推
09/27 20:10, , 1F
Searching 10時，路徑上的點有兩個紅子node要變色沒錯
09/27 20:10, 1F
→
09/27 20:12, , 2F
變色後5變紅，Insert完10並做完Rotation後才再把5變回黑
09/27 20:12, 2F
推
09/27 20:20, , 3F
插入完11後不用
09/27 20:20, 3F
→
09/27 20:20, , 4F
是等下一次插入時先走一次路徑
09/27 20:20, 4F
→
09/27 20:20, , 5F
如果路徑上有一父點兩紅子點的話就要color change
09/27 20:20, 5F
→
09/27 20:20, , 6F
確定路上都沒有違規以後再插入
09/27 20:20, 6F
抱歉我說錯了，是插入10之後，第二張圖是insert10 ※ 編輯: jouen (27.52.169.125), 09/27/2017 20:21:48
噓
09/27 20:30, , 7F
2.8是在10插入前就變黑了
09/27 20:30, 7F
→
09/27 20:30, , 8F
這時5會從黑變紅
09/27 20:30, 8F
→
09/27 20:30, , 9F
先變完確認路徑上沒問題再插入10
09/27 20:30, 9F
→
09/27 20:30, , 10F
再rotation
09/27 20:30, 10F
→
09/27 20:30, , 11F
最後才把5變回黑色
09/27 20:30, 11F
→
09/27 20:31, , 12F
抱歉按到噓了qq
09/27 20:31, 12F
還是不太了解，圖1原本2.8是紅色，加入10之後，不是處理RL就好了嗎？為什麼2.8也會 變黑色？ 這個結果會有什麼問題嗎？ https://i.imgur.com/mDO3IFo.jpg
※ 編輯: jouen (27.52.169.125), 09/27/2017 21:57:05
推
09/27 22:30, , 13F
大概是這樣，有錯
09/27 22:30, 13F
→
09/27 22:30, , 14F
誤麻煩指證
09/27 22:30, 14F
請問searching遇到一父二紅子要改顏色是必要程序嗎？ 聖經版定義？ 他是為了避免向 上產生連鎖rotation的情況嗎？ ※ 編輯: jouen (27.52.169.125), 09/27/2017 23:04:54
推
09/28 00:01, , 15F
我怎麼記得可以不用改@@ 紅黑樹蠻多版本的QQ
09/28 00:01, 15F
推
09/28 00:58, , 16F
剛剛用網頁跑出來似乎也是不用改？
09/28 00:58, 16F
推
09/28 01:01, , 17F
09/28 01:01, 17F
推
09/28 01:34, , 18F
楓葉本顏色修正的code
09/28 01:34, 18F
→
09/28 01:37, , 19F
我實際操作起來怪怪的
09/28 01:37, 19F
→
09/28 01:37, , 20F
，感覺是right-rotate的問題，但不知道怎麼改
09/28 01:37, 20F
→
09/28 01:42, , 21F
我一樓提的做法是洪逸版http://i.imgur.com/KwgbZAG.jpg
09/28 01:42, 21F
推
09/28 09:44, , 22F
大大您有先進case2嗎？我剛剛自己操作一次結果是進case
09/28 09:44, 22F
→
09/28 09:44, , 23F
2 然後case3就結束了
09/28 09:44, 23F
推
09/28 09:45, , 24F
到case3我的z是11不是10
09/28 09:45, 24F
推
09/28 09:54, , 25F
變成黑色的作法是 top-down 法 不變的是 bottom-up 法
09/28 09:54, 25F
推
09/28 11:09, , 26F
sarsman提供的top-down法,能保證2步跟4步不會同時出現？
09/28 11:09, 26F
→
09/28 11:30, , 27F
參考csee.umbc.edu的top-down投影片,也不需要2,8的變色
09/28 11:30, 27F
→
09/28 11:41, , 28F
其實也解釋了就算是bottom-up，也頂多動到祖父的祖父。
09/28 11:41, 28F
→
09/28 11:45, , 29F
所以2,8不用變色是沒錯的。
09/28 11:45, 29F
推
09/28 11:50, , 30F
不管是 top-down 或是 bottom-up 都有可能有O(lg n)變色
09/28 11:50, 30F
推
09/28 11:52, , 31F
原來，我忘記在一開始else後把else if的right改成left，
09/28 11:52, 31F
→
09/28 11:52, , 32F
謝謝g大XD
09/28 11:52, 32F
→
09/28 11:55, , 33F
ItoA 上面的方法是 bottom-up 的
09/28 11:55, 33F
推
09/28 11:59, , 34F
sarsman提供的 top-down 很奇怪 因為 top-down 的目的
09/28 11:59, 34F
→
09/28 11:59, , 35F
就是保證 search path 的尾端是黑色，所以可直接插入紅點
09/28 11:59, 35F
→
09/28 12:00, , 36F
所以 step 4 不可能會發生 如果 step 做的對的話
09/28 12:00, 36F
→
09/28 12:00, , 37F
而且 step 2 可能會有 O(lg n) 個 rotation..
09/28 12:00, 37F
推
09/28 12:01, , 38F
F大可以提供O(lg n)變色的例子嗎？
09/28 12:01, 38F
推
09/28 12:06, , 39F
可不可以只記一種qq
09/28 12:06, 39F
推
09/28 12:14, , 40F
Note的2跟4頂多只會做一個應該是指做過2就不會做4，可是2
09/28 12:14, 40F
→
09/28 12:14, , 41F
的確可能需要多次的Rotation
09/28 12:14, 41F
→
09/28 12:16, , 42F
洪逸沒提到Search path最後要黑點才能插入新的紅點，我想
09/28 12:16, 42F
→
09/28 12:16, , 43F
step4就是為了補足這點
09/28 12:16, 43F
推
09/28 20:36, , 44F
ftp://ftp.cs.princeton.edu/techreports/1985/006.pdf
09/28 20:36, 44F
→
09/28 20:37, , 45F
Figure 4，就類似這樣 因為插入就是在找 black uncle
09/28 20:37, 45F
→
09/28 20:37, , 46F
沒有 black uncle 就只好一直變色上去.. (bottom-up法)
09/28 20:37, 46F
→
09/28 20:43, , 47F
不要管這 paper 的內文 因為這是第三種 red-black
09/28 20:43, 47F
→
09/28 20:44, , 48F
這 paper 是 top-down 且保證 amortized O(1) rotation
09/28 20:44, 48F
→
09/28 21:13, , 49F
謝謝F大，我研究一下
09/28 21:13, 49F
推
09/28 21:21, , 50F
謝謝F大分享，晚點回家研究
09/28 21:21, 50F
推
09/29 12:10, , 51F
謝F大糾正，我對csee.umbc.edu的top-down投影片理解錯誤
09/29 12:10, 51F
→
09/29 12:12, , 52F
csee.umbc.edu寫的top-down會讓2,8變色,bottom-up不會。
09/29 12:12, 52F
→
09/29 12:34, , 53F
sarsman的洪逸版跟csee.umbc.edu對照後，在一次
09/29 12:34, 53F
→
09/29 12:34, , 54F
insertion中確實可能都發生2跟4。其中case3的旋轉2次
09/29 12:34, 54F
→
09/29 12:35, , 55F
只會視為1次旋轉。他只保證新點的父或Uncle其中一個
09/29 12:35, 55F
→
09/29 12:35, , 56F
必為黑。
09/29 12:35, 56F
推
09/29 20:05, , 57F
那就看你怎麼解讀2和4的分界了
09/29 20:05, 57F
→
09/29 20:06, , 58F
如果新點的父或Uncle其中一個為黑 而且知道要插入了
09/29 20:06, 58F
→
09/29 20:08, , 59F
可以先插入然後直接旋轉 step 2 和 step 4 同時發生
09/29 20:08, 59F
→
09/29 20:08, , 60F
我也可以先轉再插 就沒有 step 4 了..
09/29 20:08, 60F
推
09/29 23:14, , 61F
我想請問這個在第幾頁
09/29 23:14, 61F
‣ 更多 jouen 的文章
文章代碼(AID): #1Pov9JdH (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 2 之 4 篇)：
排序： 最新先 | 最舊先 | 留言數
理工
21
61
[理工] 紅黑樹 紅黑樹
jouen
8年前, 09/27
理工
2
7
[理工] 紅黑樹 紅黑樹
PTTleader
9年前, 11/14
在新視窗開啟完整討論串 (共4篇)
‣ 更多 jouen 的文章
文章代碼(AID): #1Pov9JdH (Grad-ProbAsk)