https://i.imgur.com/TMCf9D4.jpg
第一个图插入10之后，2、8有一定要变黑吗？ 如果2、8维持红色，应该也是符合红黑树
的规则吧？而且对应的2-3-4树高度反而比较低不是吗？
可是为什么图中要将2、8变为黑色？ 还是我有理解错的地方呢

Searching 10时，路径上的点有两个红子node要变色没错变色后5变红，Insert完10并做完Rotation后才再把5变回黑

插入完11后不用是等下一次插入时先走一次路径如果路径上有一父点两红子点的话就要color change确定路上都没有违规以后再插入2.8是在10插入前就变黑了这时5会从黑变红先变完确认路径上没问题再插入10再rotation最后才把5变回黑色抱歉按到嘘了qq

https://i.imgur.com/O9t9Pod.jpg 大概是这样，有错误麻烦指证

我怎么记得可以不用改@@ 红黑树蛮多版本的QQ刚刚用网页跑出来似乎也是不用改？https://i.imgur.com/ZqzwUA8.jpg

http://i.imgur.com/wW8CgHx.jpg 枫叶本颜色修正的codehttp://i.imgur.com/i0QHxHn.jpg 我实际操作起来怪怪的，感觉是right-rotate的问题，但不知道怎么改我一楼提的做法是洪逸版http://i.imgur.com/KwgbZAG.jpg

大大您有先进case2吗？我刚刚自己操作一次结果是进case2 然后case3就结束了到case3我的z是11不是10

变成黑色的作法是 top-down 法 不变的是 bottom-up 法

sarsman提供的top-down法,能保证2步跟4步不会同时出现？参考csee.umbc.edu的top-down投影片,也不需要2,8的变色其实也解释了就算是bottom-up，也顶多动到祖父的祖父。所以2,8不用变色是没错的。

不管是 top-down 或是 bottom-up 都有可能有O(lg n)变色

原来，我忘记在一开始else后把else if的right改成left，谢谢g大XD

ItoA 上面的方法是 bottom-up 的sarsman提供的 top-down 很奇怪 因为 top-down 的目的就是保证 search path 的尾端是黑色，所以可直接插入红点所以 step 4 不可能会发生 如果 step 做的对的话而且 step 2 可能会有 O(lg n) 个 rotation..

F大可以提供O(lg n)变色的例子吗？

可不可以只记一种qq

Note的2跟4顶多只会做一个应该是指做过2就不会做4，可是2的确可能需要多次的Rotation洪逸没提到Search path最后要黑点才能插入新的红点，我想step4就是为了补足这点

ftp://ftp.cs.princeton.edu/techreports/1985/006.pdfFigure 4，就类似这样 因为插入就是在找 black uncle没有 black uncle 就只好一直变色上去.. (bottom-up法)不要管这 paper 的内文 因为这是第三种 red-black这 paper 是 top-down 且保证 amortized O(1) rotation

谢谢F大，我研究一下

谢谢F大分享，晚点回家研究

谢F大纠正，我对csee.umbc.edu的top-down投影片理解错误csee.umbc.edu写的top-down会让2,8变色,bottom-up不会。sarsman的洪逸版跟csee.umbc.edu对照后，在一次insertion中确实可能都发生2跟4。其中case3的旋转2次只会视为1次旋转。他只保证新点的父或Uncle其中一个必为黑。

那就看你怎么解读2和4的分界了如果新点的父或Uncle其中一个为黑 而且知道要插入了可以先插入然后直接旋转 step 2 和 step 4 同时发生我也可以先转再插 就没有 step 4 了..

我想请问这个在第几页