紅黑樹是二叉搜索樹的增強版，我們知道優化二叉搜索樹的核心是優化二叉搜索樹的高度，也就是使樹盡可能地平衡，紅黑樹就是解決這個問題的，它能夠盡可能地平衡二叉搜索樹的高度，保證動態集合操作在最差的情況下時間復雜度保持在O(lgn)。
紅黑樹通過在每個節點對象（Node）上增加顏色屬性（color）來保證從根到葉子的從A到B節點任意兩條路徑差距不超過2倍，因而是近似于平衡的。
注意：紅黑樹只是平衡二叉搜索樹的其中一種，平衡二叉樹還有其它算法。
關于二叉搜索樹可以閱讀筆者前面寫的二叉搜索樹文章，這里只給出二叉搜索樹的定義，其它不再過多詳細講解，二叉搜索樹是指具有下面定義的二叉樹：
1、任何父節點的值均大于等于（>=）左孩子節點值以及左孩子下的所有孩子節點值
2、任何父節點的值均小于（<）右孩子節點值以及右孩子下的所有孩子節點值
3、樹最根節點是唯一父節點值為null的節點
定義
紅黑樹是一顆二叉搜索樹，所以除了要滿足二叉搜索樹的定義外，紅黑樹還要滿足下面的定義（背下來）：
1、每個節點要么是紅色要么是黑色
2、根節點是黑色的
3、為null的葉節點是黑色的（代碼實現上可以用一個全局對象代表所有為null的節點）
4、如果一個節點是紅色的，那么它的兩個子節點都是黑色的
5、給定任意節點，從該節點到其所有后代葉節點的簡單路徑上均包含相同數目的黑色節點
紅黑樹-左、右旋轉（left/right-rotate）
我們知道，當對二叉搜索樹進行插入、刪除操作時會改變樹結構，改變后的樹結構可能會破壞紅黑樹的性質（前面列出的定義），為了保證每次改變結構后性質不被破壞，每次修改后需要調整，調整方式有兩種，分別是變色和旋轉，其中旋轉又包含左旋轉和右旋轉。
注意，只有旋轉才會改變（逐漸平衡）樹的高度，變色是不會改變樹高度的。
下面圖解左右旋轉分別是怎么調整節點位置的（學習旋轉時我們先不要關注它們的顏色，只關注旋轉怎么調整相關節點的位置）。
我們通過上圖可以很直觀發現，B樹左旋轉后得到A樹，A樹可以通過B樹右旋轉還原回來，它們是對稱的。下面是對左右旋轉規律的總結：
B樹a節點左旋轉后得到A樹位置調整如下：
1、將a節點的右孩子節點c替換到a節點位置的父節點下
2、a節點變為c節點的左孩子
3、c節點原來的左孩子變為a節點的右孩子
4、a節點原來的左孩子不變
5、c節點原來的右孩子節點不變
左旋轉代碼實現如下：
/** * 為null的節點統一對象 */private Node nil;/** * 根節點 */private Node rootNode;private static final int RED = 1;private static final int BLACK = 2;public RedBlackTree() { this.nil = new Node(); this.nil.color = BLACK; this.rootNode = this.nil;}/** * 節點對象 */private class Node { private Node left; private T eleVal; private Node right; private Node parent; /** * 顏色 RED：紅色 BLACK：黑色 */ private int color; private Node(T eleVal) { this.eleVal = eleVal; } private Node() { this.color = RED; this.left = null; this.right = null; this.parent = null; } @Override public String toString() { return "Node{" + "eleVal=" + eleVal + ", color=" + color + '}'; }}/** * 左旋轉 * * @param a 操作節點 */private void leftRotate(Node a) { Node c = a.right; //1、將a節點的右孩子節點c替換到a節點位置的父節點下 c.parent = a.parent; if (a.parent == this.nil) { this.rootNode = c; } else if (a == a.parent.left) { a.parent.left = c; } else { a.parent.right = c; } //2、a節點變為c節點的左孩子 c.left = a; a.parent = c; //3、c節點原來的左孩子變為a節點的右孩子 a.right = c.left; if (c.left != this.nil) { c.left.parent = a; }}
A樹c節點右旋轉后得到B樹位置調整如下：
1、將c節點的左孩子節點a替換到c節點位置的父節點下
2、c節點變為a節點的右孩子
3、a節點原來的右孩子變為c節點的左孩子
4、a節點原來的左孩子不變
5、c節點原來的右孩子節點不變
右旋轉代碼實現如下：
/** * 右旋轉 * * @param c 操作節點 */private void rightRotate(Node c) { //1、將c節點的左孩子節點a替換到c節點位置的父節點下 Node a = c.left; a.parent = c.parent; if (c.parent == this.nil) { this.rootNode = a; } else if (c.parent.left == c) { c.parent.left = a; } else { c.parent.right = a; } //2、c節點變為a節點的右孩子 a.right = c; c.parent = a; //3、a節點原來的右孩子變為c節點的左孩子 c.left = a.right; if (a.right != this.nil) { a.right.parent = c; }}
實際上，這種調整是嚴格按照二叉搜索樹定義來的，這里并不打算花時間詳細去證明這種調整是如何總是能夠保證滿足紅黑樹二叉搜索樹性質的，有興趣讀者可以自己去研究或參考網上資料進行深入學習。但是不管研究深度如何，最后的做法都是把調整的規律記下來。
最后有幾個疑問，就是在什么情況下應該進行左旋轉、在什么情況下又應該進行右旋轉呢？還有變色又是怎么回事？帶著這些問題我們繼續往下看。
紅黑樹-插入（insert）
插入實際上就是構建紅黑樹性質的二叉搜索樹，每次插入一個節點時，既要遵循二叉搜索樹的定義又要保證不破壞紅黑樹的性質，可想而知，插入的邏輯會比較復雜。還是那個習慣，我們只關心操作規律規則，暫且不要糾結如何證明，因為證明的過程太復雜，很多程序員包括一般算法類工程師也未必能夠用數學公式完全證明出來，大部分都是記住定義，就是學數學一樣，把公式記下來。
我們先思考假設插入一個節點newNode,大概步驟有哪些？一般來說有以下步驟：
1、首先要根據二叉搜索樹定義將newNode節點插入到正確位置，例如插入值為4的新節點圖解如下（雖然下圖顏色是滿足紅黑樹定義的，但先不要關心顏色，因為現在還不到檢查調整紅黑樹定義的步驟）：
二叉搜索樹性質插入代碼如下：
/** * 根據二叉搜索樹定義插入新節點 * * @param newNode 新節點 */@SuppressWarnings("unchecked")private void twoForkSearchTreeInsert(Node newNode) { Node insertParent = this.nil; Node currentParent = this.rootNode; //只要不是為null的葉子節點，就一直查找下去 while (currentParent != this.nil) { //當前父節點作為本次插入節點的父節點 insertParent = currentParent; //newNode.eleVal <= currentParent.eleVal //左孩子作為父節點繼續判斷 if (newNode.eleVal.compareTo(currentParent.eleVal) <= 0) { currentParent = currentParent.left; } else { //newNode.eleVal > currentParent.eleVal //右孩子作為父節點繼續判斷 currentParent = currentParent.right; } } newNode.parent = insertParent; //如果父節點為null，本次插入的直接作為最根節點 if (insertParent == this.nil) { this.rootNode = newNode; } else if (newNode.eleVal.compareTo(insertParent.eleVal) <= 0) { //左孩子 insertParent.left = newNode; } else { //右孩子 insertParent.right = newNode; }}
2、為新節點新增顏色（默認為紅色），以及設置為null的葉子節點為nil屬性，代碼如下：
/** * 給新插入節點進行紅黑樹著為紅色 * * @param newNode 新插入節點 */private void setRedBlackTreeProperty(Node newNode) { newNode.left = this.nil; newNode.right = this.nil; newNode.parent = this.nil; //紅色 newNode.color = RED;}
為什么將新插入的節點默認著為紅色，答案在紅黑樹第五條定義：
“給定任意節點，從該節點到其所有后代葉節點的簡單路徑上均包含相同數目的黑色節點”
從這條定義可以看出，如果插入黑色的話，一定是錯誤的。當然，紅色也可能錯誤，但是紅色導致的錯誤比黑色導致的錯誤容易處理些，所以選擇了紅色作為插入的默認顏色。
3、根據二叉搜索樹插入后，接下來就需要判斷是否滿足紅黑樹性質，如果不滿足則需要進行調整。我們知道新插入節點顏色默認著為紅色，根據紅黑樹的定義，下面我們分析哪些定義可能會被破壞：
定義1：每個節點要么是紅色要么是黑色（不會被破壞）
定義2：根節點是黑色的（可能會被破壞）
定義3：為null的葉節點是黑色的（不會被破壞）
定義4：如果一個節點是紅色的，那么它的兩個子節點都是黑色的（可能會被破壞）
定義5：給定任意節點，從該節點到其所有后代葉節點的簡單路徑上均包含相同數目的黑色節點（不會被破壞，因為插入節點是紅色的）
上面總結出當每次插入至多只有一條定義被破壞，要么是定義2（根節點必須是黑色但插入的是紅色），要么是定義4（如果它父節點是紅色但插入的子節點默認也是紅色），他們不可能同時被破壞，因為如果新插入節點是根，那么根本還沒有子節點，根本不會出現定義4的情況；如果不是根，那就證明存在根，根肯定已經是黑色的，雖然在進過多次調整后根節點也可能會被破壞，所以簡單粗暴的辦法就是每次插入最后那行代碼把根節點著為黑色即可。下面給出調整紅黑樹的代碼，緊接著分析定義4被破壞的3種情況相應的調整規則。
/** * 調整紅黑樹結構，保證不破壞紅黑樹定義 * * @param newNode 新插入節點 */private void updateRedBlackTree(Node newNode) { //如果新增節點的父節點顏色是紅色，這種情況一定破壞了紅黑樹定義 //定義4：如果一個節點是紅色的，那么它的兩個子節點都是黑色的 while (newNode.parent.color == RED) { //如果新增節點的父節點是祖父節點的左孩子 if (newNode.parent == newNode.parent.parent.left) { //新增節點的叔節點 Node uncleNode = newNode.parent.parent.right; //情況1：叔節點是紅色 if (uncleNode.color == RED) { this.setColor(newNode.parent, BLACK); this.setColor(uncleNode, BLACK); this.setColor(newNode.parent.parent, RED); newNode = newNode.parent.parent; //情況2：叔節點是黑色且新插入節是右孩子 } else if (uncleNode.color == BLACK && newNode == newNode.parent.right) { newNode = newNode.parent; this.leftRotate(newNode); } //情況3：叔節點是黑色且新插入節是左孩子 this.setColor(newNode.parent, BLACK); this.setColor(newNode.parent.parent, RED); this.rightRotate(newNode.parent.parent); //如果新增節點的父節點是祖父節點的右孩子，交換位置后繼續按左孩子邏輯調整 } else if (newNode.parent == newNode.parent.parent.right) { Node uncleNode = newNode.parent.parent.left; //情況1：叔節點是紅色 if (uncleNode.color == RED) { this.setColor(newNode.parent, BLACK); this.setColor(uncleNode, BLACK); this.setColor(newNode.parent.parent, RED); newNode = newNode.parent.parent; //情況2：叔節點是黑色且新插入節是右孩子 } else if (uncleNode.color == BLACK && newNode == newNode.parent.left) { newNode = newNode.parent; this.rightRotate(newNode); } //情況3：叔節點是黑色且新插入節是左孩子 this.setColor(newNode.parent, BLACK); this.setColor(newNode.parent.parent, RED); this.leftRotate(newNode.parent.parent); } } //簡單粗暴總是將根節點設置為黑色 this.rootNode.color = BLACK;}private void setColor(Node node, int color) { if (node != null) { node.color = color; }}
情況1：新插入節點（newNode）的叔節點（uncleNode）是紅色
此時情況如下圖（下圖省略了不關鍵的子樹）
這種情況由于newNode的父節點和叔節點都是紅色時發生，先將父節點變為黑色（修復被破壞的定義4），然后將祖父節點變為紅色（變色父節點后導致定義5被破壞），最后將叔節點變為黑色（變色祖父節點后導致定義4再次被破壞），還沒有結束，實際代碼實現上，還需要將祖父節點指針賦值給newNode,循環檢查直至根節點，因為我們改變了祖父節點的顏色，勢必會破壞上面的結構。
情況2：新插入節點（newNode）的叔節點是黑色的且newNode是一個右孩子
情況3：新插入節點（newNode）的叔節點是黑色的且newNode是一個左孩子
情況4：叔節點是黑色且新插入節點是左孩子
其它情況的分析思路留給讀者自己根據代碼配合注釋和前面的講解去分析，無非就是旋轉和變色，這里就不再過多地做規則翻譯。
