交大107 紅黑

[YaControl (維)]

https://i.imgur.com/4cedX1i.jpg
https://i.imgur.com/Bm4EtDT.jpg
想請教一下各位大神
依照洪逸筆記的插入做法
在search 插入點9的時候
遇到黑紅紅的要color change
那此題在一開始search後
要color change
但是做完之後需要rotation
最後做完之後要再重新search一次嗎
如果要重新search的話結果的2,11兩個node應為黑色？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.250.52.154
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549866833.A.D90.html
推 skyHuan: 不用 可以想成一次插入只會做一次cc
→ skyHuan: https://i.imgur.com/7LERZkp.jpg
→ skyHuan: 根據演算法做完3繼續往下，不會再回頭做2
→ YaControl: 謝謝sky大的解釋 另外想問會不會有這種狀況https://i.i
→ YaControl: mgur.com/4N5HgT1.jpg
→ YaControl: https://i.imgur.com/ok45vZo.jpg
推 skyHuan: 如果之前的點都有照著演算法插入應該是不會
→ skyHuan: 你可以把這題的例子多插幾個點試試看(eg. 插7.5, 13, 10,
→ skyHuan:  16)
→ YaControl: 謝謝sky大，祝您上台大
推 Aa841018: 借問，https://i.imgur.com/qNssjFr.jpg
→ Aa841018: 像是這題很明顯搜尋中遇上兩個需要cc的狀況，那順序是：
→ Aa841018: cc-rotation（可能不用）-cc-rotation（可能不用）??
推 Aa841018: 因為做完第一個cc還沒找到適當位子，但按照步驟應該要
→ Aa841018: 插入，那是該直接繼續第二次cc嗎？
推 gama79530: https://www.youtube.com/watch?v=vDHFF4wjWYU
→ gama79530: 這個影片關於RB tree-insert的各種case都有
→ gama79530: 多看幾次把各種case洗腦到想忘都忘不掉就成功了
→ a28238341a: 我認為看洪義的筆記會稍微有誤解 因為他的例子不夠多
→ a28238341a: 用bottom-up的方式做C.C.兩次 Rotation 1次就夠了
→ a28238341a: 這是回應上面的Aa大的