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