紅黑樹是一個二叉搜尋樹，具有如下規則：
每個節點不是紅色就是黑色。
根節點必須為黑色。
如果節點為紅，其子節點必須為黑，父子節點不得同時為紅。
任一節點至NULL（NULL為黑色）的任何路徑，所含黑節點數必須相同。
根據規則4，新增節點必須為紅。
根據規則3，新增節點的父節點必須為黑。
因為新增節點必須是紅，那麼隻有在父節點不為黑的時候才需要調整，父節點為黑則無需調整。
着色法則的一個推論（證明過程未了解）是，紅黑樹的高度最多是2log(N+1)。是以，查找保證是一種對數的操作。
紅黑樹的平衡性比AVL樹要弱，但紅黑樹通常能夠導緻良好的平衡狀态。經驗告訴我們，紅黑樹的搜尋平均效率和AVL樹幾乎相等（STL源碼剖析P210）。
紅黑樹的調整大體分三種情況，單旋轉和雙旋轉非常類似于AVL樹的旋轉方法：
1、叔父節點為黑色，新節點在外側插入。調整方法是：父節點和祖父節點單旋轉并改變顔色，如下圖。
2、叔父節點為黑色，新節點在内側插入。調整方法是：先用新節點和父節點執行一次單旋轉，如下圖。
右圖和第一種情況一樣了，執行一次單旋轉再變色即可。
3、叔父節點為紅色，即祖父節點為黑，父節點和叔父節點為紅。調整方法是：改變祖父、父、叔父顔色。
如果節點G的父節點為紅，那麼使用前兩種方法進行調整即可。
從上面的插入操作可以看出，不管是内側插入還是外側插入，隻要叔父節點顔色為黑，那麼執行相應的單旋轉或雙旋轉即可。但如果叔父節點為紅，則需要改變三個節點的顔色。上圖中，G的父節點又有可能為紅，那麼就要根據G的叔父節點的顔色持續向上改變，這是自底向上的插入方法，STL中的紅黑樹就用了這種做法（源碼剖析P225）。另外一種做法是自頂向下，在沿着路徑搜尋插入點的同時，隻要發現某個黑節點的兩個兒子全為紅，則改變顔色，進而避免了持續向上的改變，《資料結構與算法分析》中的例程就用了這種方法（P356）。
下面是代碼：
參考：
《STL源碼剖析》 P208.
《資料結構與算法分析》 P351.