概念
紅黑樹是二叉搜尋樹的增強版，我們知道優化二叉搜尋樹的核心是優化二叉搜尋樹的高度，也就是使樹盡可能地平衡，紅黑樹就是解決這個問題的，它能夠盡可能地平衡二叉搜尋樹的高度，保證動态集合操作在最差的情況下時間複雜度保持在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節點的左孩子
右旋轉代碼實作如下：
/** * 右旋轉 * * @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：叔節點是黑色且新插入節點是左孩子
其它情況的分析思路留給讀者自己根據代碼配合注釋和前面的講解去分析，無非就是旋轉和變色，這裡就不再過多地做規則翻譯。