小明：老師，紅黑樹是什麼樹呀？
老師：紅黑樹是數據結構的一種，在JDK的TreeMap，TreeSet中都用應用，JDK8的HashMap中，當鏈表樹超過8的時候鏈表會轉換為紅黑樹可以提高查詢效率。
小明：好深奧哦，可以詳細講講嗎？
老師：好吧，要學習紅黑樹，咱們需要先來理解二叉查找樹（Binary Search Tree）。
二叉查找樹（BST）具備什麼特性呢？
1.左子樹上所有結點的值均小於或等於它的根結點的值。
2.右子樹上所有結點的值均大於或等於它的根結點的值。
3.左、右子樹也分別為二叉排序樹。
下圖中這棵樹，就是一顆典型的二叉查找樹：
這樣的數據結構有什麼好處呢？我們來試著查找一下值為10的節點。
1.查看根節點9：
2.由於10 > 9，因此查看右孩子13：
3.由於10 < 13，因此查看左孩子11：
4.由於10 < 11，因此查看左孩子10，發現10正是要查找的節點：
這種方式正式二分查找的思想，查找所需的最大次數等同於二叉樹的高度。在插入節點的時候也是利用類似的方法，通過一層一層比較大小，找到新節點適合插入的位置。
小明：好方便，二叉查找樹真是個強大的數據結構！
老師：很遺憾，二叉查找樹仍然存在它的缺陷。
小明：哦，到底存在什麼缺陷呢？
老師：缺陷體現在插入新節點的時候。讓我們來看看下面這種情形：
假設初始的二叉查找樹只有三個節點，根節點值為9，左孩子值為8，右孩子值為12：
接下來我們依次插入如下五個節點：7,6,5,4,3。依照二叉查找樹的特性，結果會變成什麼樣呢？
小明：媽呀，好好的二叉查找樹變成瘸子了
老師：正式如此。這樣的形態雖然也符合二叉查找樹的特性，但是查找的性能大打折扣，幾乎變成了線性。如何解決二叉查找樹多次插入新節點而導致的不平衡呢？我們的主角【紅黑樹】應運而生了。紅黑樹（Red Black Tree）是一種自平衡的二叉查找樹。除了符合二叉查找樹的基本特性外，它還具有下列的附加特性：
1.節點是紅色或黑色。
2.根節點是黑色。
3.每個葉子節點都是黑色的空節點（NIL節點）。
4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
下圖中這棵樹，就是一顆典型的紅黑樹：
小明：這麼多條條框框呀
老師：正是因為這些規則現實，才保證了紅黑樹的自平衡。紅黑樹從根到葉子的最長路徑不會超過最短路徑的2倍。當插入或刪除節點的時候，紅黑樹的規則有可能被打破。這時候就需要做出一些調整，來繼續維持我們的規則。
什麼情況下會破壞紅黑樹的規則，什麼情況下不會破壞規則呢？我們舉兩個簡單的例子：
1.向原紅黑樹插入值為14的新節點：
由於父節點15是黑色節點，因此這種情況並不會破壞紅黑樹的規則，無需做任何調整。
2.向原紅黑樹插入值為21的新節點：
由於父節點22是紅色節點，因此這種情況打破了紅黑樹的規則4（每個紅色節點的兩個子節點都是黑色），必須進行調整，使之重新符合紅黑樹的規則。
小明：那麼，我們需要做出怎樣的調整，才能保證一顆紅黑樹始終是紅黑樹呢？
老師：調整有兩種方法：【變色】和【旋轉】。而旋轉又分成兩種形式：【左旋轉】和【右旋轉】。
變色：
為了重新符合紅黑樹的規則，嘗試把紅色節點變為黑色，或者把黑色節點變為紅色。
下圖所表示的是紅黑樹的一部分，需要注意節點25並非根節點。因為節點21和節點22連續出現了紅色，不符合規則4，所以把節點22從紅色變成黑色：
但這樣並不算完，因為憑空多出的黑色節點打破了規則5，所以發生連鎖反應，需要繼續把節點25從黑色變成紅色：
此時仍然沒有結束，因為節點25和節點27又形成了兩個連續的紅色節點，需要繼續把節點27從紅色變成黑色：
左旋轉：
逆時針旋轉紅黑樹的兩個節點，使得父節點被自己的右孩子取代，而自己成為自己的左孩子。說起來很怪異，大家看下圖：
圖中，身為右孩子的Y取代了X的位置，而X變成了自己的左孩子。此為左旋轉。
右旋轉：
順時針旋轉紅黑樹的兩個節點，使得父節點被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：
圖中，身為左孩子的Y取代了X的位置，而X變成了自己的右孩子。此為右旋轉。
小明：好複雜，究竟什麼時候用到變色，什麼時候用到旋轉呢？
老師：確實有些複雜。紅黑樹的插入和刪除包含很多種情況，每一種情況都有不同的處理方式。在這裡我們舉一個典型例子。我們以剛才插入節點21的情況為例：
首先，我們需要做的是變色，把節點25及其下方的節點變色：
此時節點17和節點25是連續的兩個紅色節點，那麼把節點17變成黑色節點？恐怕不合適。這樣一來不但打破了規則4，而且根據規則2（根節點是黑色），也不可能把節點13變成紅色節點。
變色已無法解決問題，我們把節點13看做X，把節點17看做Y，像剛才的示意圖那樣進行左旋轉：
由於根節點必須是黑色節點，所以需要變色，變色結果如下：
這樣就結束了嗎？並沒有。因為其中兩條路徑(17 -> 8 -> 6 -> NIL)的黑色節點個數是4，其他路徑的黑色節點個數是3，不符合規則5。
這時候我們需要把節點13看做X，節點8看做Y，像剛才的示意圖那樣進行右旋轉：
最後根據規則來進行變色：
如此一來，我們的紅黑樹變得重新符合規則。這一個例子的調整過程比較複雜，經歷瞭如下步驟：
變色 -> 左旋轉 -> 變色 -> 右旋轉 -> 變色
小明：還真是繞呀，我慢慢消化吧。
老師：嗯,關於紅黑樹自平衡的調整，插入和刪除節點的時候都涉及到很多種Case，由於篇幅原因沒有一一列舉，有興趣的朋友可以參考維基百科，裡面講的非常清晰。
閱讀更多 HelloWorld應用 的文章
