紅黑樹的旋轉操作
紅黑樹的旋轉操作和AVL樹一樣，分為Ll 、RR、LR、RL四種旋轉類型，差別在於旋轉完成後改變的是結點的顏色，而不是平衡因子。旋轉動畫演示請參考AVL這篇文章中的Flash動畫：
http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.Html
紅黑樹上結點的插入
在討論紅黑樹的插入操作之前必須要明白，任何一個即將插入的新結點的初始顏色都為紅色。這一點很容易理解，因為插入黑點會增加某條路徑上黑結點的數目，從而導致整棵樹黑高度的不平衡。但如果新結點父結點為紅色時（如圖2所示），將會違返紅黑樹性質：一條路徑上不能出現相鄰的兩個紅色結點。這時就需要通過一系列操作來使紅黑樹保持平衡。
為了清楚地表示插入操作以下在結點中使用“新”字表示一個新插入的結點；使用“父”字表示新插入點的父結點；使用“叔”字表示“父”結點的兄弟結點；使用“祖”字表示“父”結點的父結點。插入操作分為以下幾種情況：
1、黑父
如圖3所示，如果新點的父結點為黑色結點，那麼插入一個紅點將不會影響紅黑樹的平衡，此時插入操作完成。紅黑樹比AVL樹優秀的地方之一在於黑父的情況比較常見，從而使紅黑樹需要旋轉的幾率相對AVL樹來說會少一些。
2．紅父
如果新點的父結點為紅色，這時就需要進行一系列操作以保證整棵樹紅黑性質。如圖3所示，由於父結點為紅色，此時可以判定，祖父結點必定為黑色。這時需要根據叔父結點的顏色來決定做什麼樣的操作。青色結點表示顏色未知。由於有可能需要根結點到新點的路徑上進行多次旋轉操作，而每次進行不平衡判斷的起始點（我們可將其視為新點）都不一樣。所以我們在此使用一個藍色箭頭指向這個起始點，並稱之為判定點。
2.1 紅叔
當叔父結點為紅色時，如圖4所示，無需進行旋轉操作，只要將父和叔結點變為黑色，將祖父結點變為紅色即可。但由於祖父結點的父結點有可能為紅色，從而違反紅黑樹性質。此時必須將祖父結點作為新的判定點繼續向上進行平衡操作。
需要注意，無論“父”在“叔”的左邊還是右邊，無論“新”是“父”的左孩子還是右孩子，它們的操作都完全一樣。
