讀者看到這個標題都會覺得不可思議吧，不過這確實是算法的妙處，編程的魅力。像TreeMap、TreeSet、JDK8 HashMap等都使用這種算法，這種算法就是紅黑樹。紅黑樹能在O（lgn）的時間內完成查找、插入和刪除操作。
紅黑樹是變種的AVL樹(有關AVL樹的原理請查看小編的文章《平衡二叉樹AVL》)，是一種弱平衡二叉樹。什麼是強平衡？AVL樹保證每個子樹的高度差的絕對值都不超過1，這種是強平衡，AVL每次插入數據和刪除數據時，為了保持這種特性，得進行不可預算的旋轉，極大可能地損耗性能。而紅黑樹在任何不平衡狀態下都會在3次旋轉之內解決。
好了，廢話不多說，下面小編將通過圖文以及代碼講解紅黑樹的知識點。
注：本文中實現的代碼參考了treeMap的源碼
紅黑樹概念
紅黑樹是每個節點都帶有顏色屬性並能自平衡的二叉查找樹，顏色是紅色或黑色。它必須滿足如下性質
- 每個節點要麼是黑色，要麼是紅色
- 根節點是黑色
- 每個葉子節點(NIL)是黑色(又被稱為黑哨兵)
- 每個紅色節點的兩個子節點都是黑色
- 任意一節點到每個葉子節點的路徑都包含數量相同的黑節點
有了這幾個性質做為限制，避免了二叉查找樹退化成單鏈表的情況。而且從這幾條性質也可以看出：當某條路徑最短時，這條路徑必然都是由黑色節點構成。當某條路徑最長時，這條路徑必然是由紅色和黑色節點相間構成（由於性質4的限定）。而性質5又規定任意一節點到每個葉子節點的路徑都包含數量相同的黑節點，所以在路徑最長的情況下，路徑上紅色節點數量=黑色節點數量，也就是說路徑長度為兩倍黑色節點數量，換句話就是最長路徑是最短路徑長度的2倍。
注：紅黑色樹是一種比較難的數據結構，要完全搞懂非常耗時耗力。而且涉及到的知識點有BT、BST和AVL。如果對這些數據結構不是很熟悉的同學，可以關注下小編的頭條號，小編其他文章中有對這些數據結構進行講解。
自平衡
紅黑樹能自平衡，靠的是：左旋、右旋和變色
- 左旋：逆時針旋轉紅黑樹的兩個節點，使父節點被自己的右孩子取代，而自己成為自己的左孩子
private void rotateLeft(RBTreeNode p) {
if (p != null) {
RBTreeNode r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
- 右旋：順時針旋轉紅黑樹的兩個節點，使父節點被自己的左孩子取代，而自己成為自己的右孩子
private void rotateRight(RBTreeNode p) {
if (p != null) {
RBTreeNode l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
- 變色：節點顏色由紅色變黑色或黑色變紅色
插入
紅黑樹的插入過程和二叉查找樹(BST)插入過程類似，不過紅黑樹插入新節點後，需進行自平衡調整，以滿足紅黑樹的的性質。當插入新節點時，我們設置這個新節點為紅色，因為插入紅色節點後滿足性質5，保持紅黑樹所有路徑上的黑色節點數量不變，僅可能破壞性質4，出現兩個連續的紅色節點的情況。少破會一條性質，插入自平衡操作比較簡單。
接下來，將分析插入紅色節點後紅黑樹的情況。這裡做下規定：插入的新節點為N，N的父節點為P，祖父節點為G，叔叔節點為U。
情況1
插入的新節點N是紅黑樹的根節點，比如插入節點12，這種情況下，我們把節點12的顏色由紅色變為黑色，性質2被滿足。也沒有破壞其他的性質。
情況2
N的父節點是黑色，比如在情況1下插入節點1，性質4和性質5都沒有受到影響，不需要調整。
以下情況N的父節點P都是紅色，主要區分叔叔節點U的情況，節點U有可能是黑色，有可能是紅色。
情況3
N的父節點P是紅色，叔叔節點U也是紅色。由於P和N均為紅色，性質4被打破，此時需要調整。如下圖所示，假設節點7是新插入的節點。先將節點0和節點2染成黑色，再把節點9染成紅色。此時經過9-1-0和9-1-2-7路徑上的黑色節點數量相等，性質5仍然滿足。但需要注意的是G（節點9）被染成紅色後，可能會和它的父節點形成連續的紅色節點，此時需要遞歸向上調整。圖中節點9是根節點，所以只需要把9染成黑色，就能完成平衡。
情況4
N的父節點P為紅色，叔叔節點U為黑色。N是P的左孩子。如下圖所示，假設節點4是新插入的節點，節點7是父節點，叔叔節點Nil默認為黑色。先將節點4右旋，然後再變色，把節點4染黑，祖父節點2染紅。此時2-4-7滿足紅黑樹的性質。但需要注意的是節點2被染成紅色後，與父節點1形成連續紅色節點，所以需要遞歸向上調整。
情況5
N的父節點P為紅色，叔叔節點U為黑色。N是P的右孩子。也就是情況4最右圖的變種。把N當做節點2-4-7這個路徑，叔叔節點0為黑色，節點N是節點1的右孩子。現在對這種情況進行分析：我們只要把N中的節點4左旋，這個時候就可以滿足紅黑樹的性質，達到平衡。
情況3，情況4和情況5是針對N節點的父節點是祖父節點G的右孩子這種情況來分析的，也就是說存在N節點的父節點是祖父節點G的左孩子這種情況，由於這種情況與上面分析的類似，這裡不再贅述。有興趣的同學可以開動腦筋思考下，動動手，這樣紅黑樹知識掌握得就透徹啦。
下面我將通過圖來演示數據12、1、9、2、0、11、7、19、4、15、18插入到紅黑樹中的情況，大家拿好板凳，認真跟著小編一步一步來哈。
插入12，建立根節點
插入節點1
插入節點9
插入節點2
插入節點0
插入節點11
插入節點7
插入節點19
插入節點4
插入節點15
插入節點18
數據12、1、9、2、0、11、7、19、4、15、18插入到紅黑樹中演示完畢了，最終的紅黑樹數據結構如下
好啦看到這裡是不是感覺有點疲勞了，那就休息下，伸伸懶腰，回憶回憶之前的內容，如果有受益，不妨給小編點點贊。
休息差不多了，現在我們開始講講紅黑樹的刪除操作啦
刪除
刪除操作首先要確定待刪除節點有幾個孩子，如果有兩個孩子，要先找到該節點的前驅(該節點左子樹中最大的節點)或者後繼(該節點右子樹中最小的節點)，將前驅或者後繼的值替換到待刪除節點的值。由於前驅和後繼至多隻有一個孩子節點，這樣我們就把問題轉化為只有一個孩子節點的情況了。問題被簡化了一些。
注：本文中使用後繼做為待刪除節點替換的值。想要了解前驅和後繼的話，請參考二叉查找樹BST文章中第4點和第5點的內容。
紅黑樹待刪除的節點，如果為紅色，性質5(任意一節點到每個葉子節點的路徑都包含數量相同的黑節點)不會被破壞，這時候直接用其孩子節點替換空位即可；如果為黑色，那麼就破壞了性質5，需要自平衡處理。如果待刪除節點的孩子節點為紅色，直接用孩子節點替換待刪除的節點，並將孩子節點染成黑色。這樣就達到了平衡。如果待刪除節點的孩子節點為黑色，處理就比較複雜。
下面我們將對待刪除節點的孩子節點為黑色進行分析，先做下規定：待刪除節點為X，X的孩子節點為N(至多隻有一個孩子節點)，X的父節點為P，X的兄弟節點為B，B的左孩子為BL，右孩子為BR。
情況1
兄弟節點B是黑色，節點B的兩個子孩子BL、BR也是黑色。比如下圖中：待刪除節點13是黑色，節點13的父節點16是黑色，兄弟節點17是黑色，兄弟節點的兩個子孩子為Nil，也都是黑色。處理操作是設置兄弟節點17為紅色，並向上遞進判斷父節點16的平衡情況，直到待操作的節點是紅色為止。最後斷掉節點13，達到平衡。圖中還需要遞進一次，才能達到平衡。這裡不列出來了，同學們自己動動手哈。
情況2
兄弟節點B是紅色，節點B的兩個子孩子BL、BR都是黑色。比如下圖中：待刪除節點16是黑色，由於待刪除節點16有兩個非空子孩子，後繼尋找替換的節點17，把節點17的值替換到節點16上，此後待刪除的節點轉化成節點17。由節點17可知，兄弟節點6是紅色，節點6的兩個孩子是黑色，改變兄弟節點6為黑色，父節點17位紅色，並右旋。這時候待刪除的節點17，轉換成情況1。
情況3
兄弟節點B是黑色，節點B的兩個子孩子BL、BL都是紅色。比如下圖：待刪除節點19是黑色，父節點18是紅色，兄弟節點16是黑色，兄弟節點的兩個孩子節點15和節點17是紅色，這個時候先進行變色，父節點18變黑，兄弟節點16變紅，兄弟節點的左孩子15變黑，再進行右旋，並切斷節點19就達到了平衡。
情況4
兄弟節點B是黑色，節點B的左孩子BL是紅色，右孩子BR是黑色。比如下圖：待刪除節點15是黑色，父節點16是紅色，兄弟節點18是黑色，節點17是紅色。先對節點17染黑，對節點18染紅，再對節點18右旋。這些步驟後，樹變成兄弟節點左孩子BL是黑色，右孩子BR是紅色這種情況，接著對節點17染紅，節點18染黑，父節點16染黑，再對父節點16左旋並斷鏈節點15，從而達到了平衡。
情況1和情況4針對的是待刪除節點是父節點左孩子的情況，情況2和情況3針對的是待刪除節點是父節點右孩子的情況，也就是說還存在：情況1和情況4待刪除節點是父節點右孩子的情況；情況2和情況3待刪除節點是父節點左孩子的情況。由於這些情況與上面介紹的情況類似，這裡就不在贅述了。有興趣的同學，自己動動手，鞏固下學到的知識點。
下面我將通過圖來演示將數據12、1、9、2、0、11、7、19、4、15依次從紅黑樹中刪除的情況，大家拿好板凳，認真跟著小JIA一步一步來哈。
紅黑樹初始數據結構
刪除節點12
刪除節點1
刪除節點9
刪除節點2
刪除節點0
刪除節點11
刪除節點7
刪除節點19
刪除節點4
刪除節點15
最後只剩下節點18，也就是隻剩下根節點。數據12、1、9、2、0、11、7、19、4、15依次從紅黑樹中刪除的情況演示完畢！
遍歷
紅黑樹的遍歷同二叉樹的遍歷，小編在《二叉樹》文章中已經介紹過啦，這裡不在贅述。
查找
紅黑樹的遍歷同AVL的遍歷，小編在《平衡二叉樹AVL》文章中已經介紹過啦，這裡不在贅述。
花了幾天時間，終於把紅黑樹整理完畢啦，由於紅黑樹涉及太多，一下子可能看不過來，小編建議：各位同學關注下小編的頭條號，有時間再慢慢看哈。
這篇文章實現的完整代碼，如果有需要的同學可以私聊找小編獲取。
閱讀更多 java技術閱讀 的文章
