C#與數據結構--樹論--紅黑樹（Red Black Tree）(上)(3)

2.2 黑叔

當叔父結點為黑色時，需要進行旋轉，以下圖示了所有的旋轉可能

情形1：

情形2：

情形3：

情形4：

可以觀察到，當旋轉完成後，新的旋轉根全部為黑色，此時不需要再向上回溯進行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結點有可能為黑哨兵結點。

其實紅黑樹的插入操作不是很難，甚至比AVL樹的插入操作還更簡單些。但刪除操作就遠遠比AVL樹復雜得多，下面就介紹紅黑樹的刪除操作。