交大107 紅黑

看板Grad-ProbAsk作者 (維)時間6年前 (2019/02/11 14:33), 編輯推噓5(5推 0噓 16→)
留言21則, 5人參與, 6年前最新討論串1/1
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
推
02/11 14:38, 6年前 , 1F
不用 可以想成一次插入只會做一次cc
02/11 14:38, 1F
→
02/11 14:39, 6年前 , 2F
02/11 14:39, 2F
→
02/11 14:39, 6年前 , 3F
根據演算法做完3繼續往下，不會再回頭做2
02/11 14:39, 3F
→
02/11 14:52, 6年前 , 4F
謝謝sky大的解釋 另外想問會不會有這種狀況https://i.i
02/11 14:52, 4F
→
02/11 14:52, 6年前 , 5F
mgur.com/4N5HgT1.jpg
02/11 14:52, 5F
→
02/11 14:52, 6年前 , 6F
02/11 14:52, 6F
推
02/11 15:00, 6年前 , 7F
如果之前的點都有照著演算法插入應該是不會
02/11 15:00, 7F
→
02/11 15:00, 6年前 , 8F
你可以把這題的例子多插幾個點試試看(eg. 插7.5, 13, 10,
02/11 15:00, 8F
→
02/11 15:00, 6年前 , 9F
16)
02/11 15:00, 9F
→
02/11 15:12, 6年前 , 10F
謝謝sky大，祝您上台大
02/11 15:12, 10F
推
02/11 15:28, 6年前 , 11F
02/11 15:28, 11F
→
02/11 15:28, 6年前 , 12F
像是這題很明顯搜尋中遇上兩個需要cc的狀況，那順序是：
02/11 15:28, 12F
→
02/11 15:28, 6年前 , 13F
cc-rotation（可能不用）-cc-rotation（可能不用）??
02/11 15:28, 13F
推
02/11 15:31, 6年前 , 14F
因為做完第一個cc還沒找到適當位子，但按照步驟應該要
02/11 15:31, 14F
→
02/11 15:31, 6年前 , 15F
插入，那是該直接繼續第二次cc嗎？
02/11 15:31, 15F
推
02/11 16:24, 6年前 , 16F
02/11 16:24, 16F
→
02/11 16:26, 6年前 , 17F
這個影片關於RB tree-insert的各種case都有
02/11 16:26, 17F
→
02/11 16:27, 6年前 , 18F
多看幾次把各種case洗腦到想忘都忘不掉就成功了
02/11 16:27, 18F
→
02/11 17:18, 6年前 , 19F
我認為看洪義的筆記會稍微有誤解 因為他的例子不夠多
02/11 17:18, 19F
→
02/11 17:19, 6年前 , 20F
用bottom-up的方式做C.C.兩次 Rotation 1次就夠了
02/11 17:19, 20F
→
02/11 17:23, 6年前 , 21F
這是回應上面的Aa大的
02/11 17:23, 21F
‣ 更多 YaControl 的文章
文章代碼(AID): #1SOHTHsG (Grad-ProbAsk)