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 了..

我想請問這個在第幾頁