3.2.3 黑兄紅侄
黑兄紅侄有以下四種情形，下面分別進行圖示：
情形1：
情形2：
情形3：
情形4：
由以上圖例所示，看完以上四張圖的兄弟有可能會有一個疑問，如果情形1和情形2中的兩個侄子結點都為紅色時，是該進行LL旋轉還是進行LR旋轉呢？答案是進行LL旋轉。情形3和情形4則是優先進行RR旋轉的判定。
紅黑樹的代碼實現
本以為紅黑樹的代碼非常容易，因為System.Collections.Generic.SortedDictionary類就是使用紅黑樹實現的，把代碼的算法部分摳出來就搞定了。但看了SortedDictionary源碼後有些失望，C#中真正實現紅黑樹的是TreeSet類，SortedDictionary只是在TreeSet的基礎上進一步抽象，加上了Key/Value泛型對。TreeSet使用了一種新的紅黑樹算法，它在搜索插入點和刪除點時預先進行旋轉和染色操作，從而避免插入和刪除後的回溯。這種算法看上去很美，但仔細想想，如果插入的是一個已經存在的結點，刪除的結點並不存在，那這些預平衡處理不是白做了嗎？更可怕的是如果在一條路徑上間隔進行一次插入和一次刪除，而這些操作沒有命中目標，那麼大家就會看到結點的顏色變來變去，這些都是無用功。來看看在尋找插入和刪除點的路徑上TreeSet每前進一步都要做些什麼：給四個變量賦值；判斷每個結點的兩個孩子結點的顏色。這種算法在《Java數據結構和算法》這本書中有詳細講述，不過只講解了插入算法。另外國內也專門有一篇論文描述這個算法，他的測試結果是這種算法優於其他算法，估計測試時沒有不命中目標的情況發生。總之我並不相信這是一個好的算法。
為了證實我的想法，我不得不自己實現紅黑樹，實現思路跟AVL樹很類似，也是使用一個數組保存訪問路徑以進行回溯，當然，考慮到紅黑樹不嚴格的平衡，數組的長度設為64，這並不會給性能帶來什麼影響。過程很艱辛，需要做大量測試。很不幸，寫完後繼續做紅黑樹的Silverlight動畫時不小心把原來的代碼給覆蓋掉了，結點刪除部分的代碼丟失。當時幾乎崩潰，不過重寫並沒有我想象的那麼困難，很快完成，感覺思路清晰了很多，實現比原來也有了改進，感謝上帝！
