作者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/cn.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