最近研究JDK源碼的時候，發現TreeMap和TreeSet底層數據結構是紅黑樹，當然，TreeSet其實本質上就是Value為壹個固定值的TreeMap。在JDK1.8以後，HashMap也用到了紅黑樹。
那紅黑樹到底是怎樣的壹種數據結構呢？相信大家都不是非常了解，我也去翻了好多的相關文章，發現壹篇很有趣的漫畫，可以幫助大家很快了解紅黑樹大概是怎樣的壹種數據結構，有哪些特點。 只是大概的介紹壹下紅黑樹，詳細的實現大家還是請參考相關的算法書籍。
以下內容轉自： 漫畫算法：什麽是紅黑樹？
1.左子樹上所有結點的值均小於或等於它的根結點的值。
2.右子樹上所有結點的值均大於或等於它的根結點的值。
3.左、右子樹也分別為二叉排序樹。
下圖中這棵樹，就是壹顆典型的二叉查找樹：
1.查看根節點9：
3.由於10 < 13，因此查看左孩子11：
假設初始的二叉查找樹只有三個節點，根節點值為9，左孩子值為8，右孩子值為12：
2.根節點是黑色。
3.每個葉子節點都是黑色的空節點（NIL節點）。
4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
5.從任壹節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
下圖中這棵樹，就是壹顆典型的紅黑樹：
什麽情況下會破壞紅黑樹的規則，什麽情況下不會破壞規則呢？我們舉兩個簡單的栗子：
1.向原紅黑樹插入值為14的新節點：
為了重新符合紅黑樹的規則，嘗試把紅色節點變為黑色，或者把黑色節點變為紅色。
下圖所表示的是紅黑樹的壹部分，需要註意節點25並非根節點。因為節點21和節點22連續出現了紅色，不符合規則4，所以把節點22從紅色變成黑色：
但這樣並不算完，因為憑空多出的黑色節點打破了規則5，所以發生連鎖反應，需要繼續把節點25從黑色變成紅色：
逆時針旋轉紅黑樹的兩個節點，使得父節點被自己的右孩子取代，而自己成為自己的左孩子。說起來很怪異，大家看下圖：
圖中，身為右孩子的Y取代了X的位置，而X變成了自己的左孩子。此為左旋轉。
順時針旋轉紅黑樹的兩個節點，使得父節點被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：
圖中，身為左孩子的Y取代了X的位置，而X變成了自己的右孩子。此為右旋轉。
首先，我們需要做的是變色，把節點25及其下方的節點變色：
這時候我們需要把節點13看做X，節點8看做Y，像剛才的示意圖那樣進行右旋轉：
如果想要詳細了解紅黑樹算法，可以參考這篇文章： Java數據結構和算法（十壹）——紅黑樹