紅黑樹的定義
紅黑樹不是嚴格的平衡二叉樹。（即不會嚴格遵守左右子樹高度差的絕對值不超過1的條件，與之相對的，用AVL算法實現(xiàn)的則是嚴格的平衡二叉樹，但紅黑樹性能更優(yōu)。）
紅黑樹在原有的排序二叉樹上增加了以下幾個要求：
1)每個節(jié)點要么是紅色，要么是黑色
2)根節(jié)點永遠是黑色的
3)每個紅色節(jié)點的子節(jié)點都是黑色 （反之不一定）
4)從任一節(jié)點到其子樹中每個葉節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點（計算時含葉節(jié)點）
注意：所有的葉節(jié)點都是空節(jié)點(null)，并且是黑色的，被稱為黑哨兵（跟其它場合的葉節(jié)點不是一回事）
相關定義參考：二叉樹的基本性質
紅黑樹示例：
定義中關于葉節(jié)點的說法，有效的保證了平衡性，下面看一個反例：
上述例子不是紅黑樹。
紅黑樹操作：查詢
和普通二叉搜索樹一樣，略。
紅黑樹操作：插入節(jié)點
先看下三個基本操作：
變色
改變顏色，沒什么好說的
左旋
直接看圖：
右旋
直接看圖：
java 中處理插入操作時有如下規(guī)律：
在紅黑樹中插入的節(jié)點都是紅色的，因為插入一個紅色節(jié)點比插入一個黑色節(jié)點違背紅黑規(guī)則的可能性更小。原因是：插入黑色節(jié)點總會改變黑色高度，但是插入紅色節(jié)點只有一半的機會會違背規(guī)則3。另外違背規(guī)則3比違背規(guī)則4要更容易修正。當插入一個新的節(jié)點時，可能會破壞這種平衡性，那么紅黑樹是如何修正的呢？
1. 如果是第一次插入，由于原樹為空，所以只會違反紅黑樹的規(guī)則2，所以只要把根節(jié)點涂黑即可；
2.如果插入節(jié)點的父節(jié)點是黑色的，那不會違背紅黑樹的規(guī)則，什么也不需要做；
3.插入節(jié)點的父節(jié)點和其叔叔節(jié)點均為紅色的；
4. 插入節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色；
值得一提的是，后面兩種情況，都可以認為當前節(jié)點的祖父節(jié)點必然存在，且為黑色（根據(jù)紅黑樹的性質可以推導，這樣就簡化了判斷邏輯）
先看一個例子，在原有紅黑樹的基礎上插入節(jié)點(4)，首先對應情況3：
注意：這里只是為了說明情況，假設祖父節(jié)點的父節(jié)點仍然是紅色的，所以需要進行下一步。實際情況，也有可能是黑色的，那么操作也就到此為止了，不必進行下一步。也就是說，情況3操作結束后，要不要進行下一步，要看目前具體屬于哪種情況。
對于情況4：插入節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色。以例子中的情況來看，我們要做的操作有：第一步：以節(jié)點(7)作為新的節(jié)點，以父親節(jié)點(2)為支點做左旋操作，左旋結束后，當前節(jié)點變?yōu)樵赣H節(jié)點(2)。第二步：節(jié)點(2)作為新的節(jié)點，將父節(jié)點(7)涂黑，將祖父節(jié)點(11)涂紅，以祖父節(jié)點(11)為支點做右旋操作。最終結果如上圖。
注意：在一次完整的插入操作中，可能通過不止一次旋轉才完成目標。但是插入操作最多也只會有兩次旋轉。
那么情況4到底是按照什么邏輯來進行變色或旋轉的呢？其實有多種理解方法：
第一種理解方法
考慮當前節(jié)點n和父節(jié)點p的位置又分為四種情況：A、n是p左子節(jié)點，p是g的左子節(jié)點。
B、n是p右子節(jié)點，p是g的右子節(jié)點。
C、n是p左子節(jié)點，p是g的右子節(jié)點。
D、n是p右子節(jié)點，p是g的左子節(jié)點。
情況A：n是p左子節(jié)點，p是g的左子節(jié)點。針對該情況可以通過一次右旋轉操作，并將p設為黑色，g設為紅色。
情況B則需要使用左旋操作來解決平衡問題，方法和情況A類似。
情況C：n是p左子節(jié)點，p是g的右子節(jié)點。針對該情況通過一次左旋，一次右旋操作，并將n設為黑色，g設為紅色完成重新平衡。
情況D則需要使用一次右旋，一次左旋操作來解決平衡問題，方法和情況C類似。
備注：情況3和情況4的旋轉支點標錯了，不要被誤導。
第二種理解方法
考慮當前節(jié)點是父親節(jié)點的左節(jié)點還是右節(jié)點。
A、當前節(jié)點是左節(jié)點。
B、當前節(jié)點是右節(jié)點。
但是要考慮當前節(jié)點跟父親節(jié)點是不是同一側（實際上TreeMap程序也是這么寫的）口訣就是：左節(jié)點右旋，右節(jié)點左旋，同側變色旋，不同側普通旋，如此遞歸至當前節(jié)點（當前節(jié)點會可能隨著旋轉操作改變）的父親節(jié)點是黑色為止。
其中普通旋之后一定會再來一次變色旋，變色旋之后一定不需要再旋轉了。（其實也就是把上一種理解方式歸納一下）
普通旋：以當前節(jié)點的父親節(jié)點為支點，進行旋轉操作（包括左旋右旋），然后把父親節(jié)點作為當前節(jié)點，繼續(xù)判斷（當然，TreeMap中這種狀態(tài)并沒有判斷，直接下一步，因為這時候肯定不符合紅黑規(guī)則）；
變色旋：以當前節(jié)點的祖父節(jié)點為支點，進行旋轉操作（包括左旋右旋），并把父節(jié)點變黑，祖父節(jié)點變紅，這個情況下當前節(jié)點不需要再改變了。
當前節(jié)點跟父親節(jié)點是不是同一側還有一個專業(yè)的說法：同側為外側插入，不同側為內側插入。
可以這樣理解（非官方）：對于內測插入，先要通過普通旋變成外側插入的情況。
TreeMap代碼如下（jdk6）：
PRivate void fixAfterInsertion(Entry<K,V> x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; }紅黑樹操作：刪除節(jié)點java 中處理刪除操作時有如下規(guī)律：111
參考地址：http://blog.csdn.net/eson_15/article/details/51144079
參考地址：http://blog.csdn.net/very_2/article/details/5722682
參考地址：http://www.cnblogs.com/yydcdut/p/4009201.html
新聞熱點
疑難解答
