3、雙黑
當舊點和新點都為黑色時（新點為空結點時，亦屬於這種情況），情況比較復雜，需要根據舊點兄弟結點的顏色來決定進行什麼樣的操作。我們使用“兄”來表示舊點的兄弟結點。這裡可分為紅兄和黑兄兩種情況：
3.1 紅兄
由於兄弟結點為紅色，所以父結點必定為黑色，而舊點被刪除後，新點取代了它的位置。下圖演示了兩種可能的情況：
紅兄的情況需要進行RR或LL型旋轉，然後將父結點染成紅色，兄結點染成黑色。然後重新以新點為判定點進行平衡操作。我們可以觀察到，旋轉操作完成後，判定點沒有向上回溯，而是降低了一層，此時變成了黑兄的情況。
3.2 黑兄
黑兄的情況最為復雜，需要根據黑兄孩子結點（這裡用“侄”表示）和父親結點的顏色來決定做什麼樣的操作。
3.2.1 黑兄二黑侄紅父
如圖14所示，這種情況比較簡單，只需將父結點變為黑色，兄結點變為黑色，新結點變為黑色即可，刪除操作到此結束。
3.2.2黑兄二黑侄黑父
如圖15所示，此時將父結點染成新結點的顏色，新結點染成黑色，兄結點染成黑色即可。當新結點為紅色時，父結點被染成紅色，此時需要以父結點為判定點繼續向上進行平衡操作。
