作者小灰
最近，小灰把這個知識點重新做了總結，分成上下兩篇，希望大家把紅黑樹這個重要的資料結構徹底吃透。
————— 第二天 —————
————————————
二叉查找樹（BST）具備什麼特性呢？
1.左子樹上所有結點的值均小于或等于它的根結點的值。
2.右子樹上所有結點的值均大于或等于它的根結點的值。
3.左、右子樹也分别為二叉排序樹。
下圖中這棵樹，就是一顆典型的二叉查找樹：
1.檢視根結點9：
2.根據二叉查找樹左子樹小、右子樹大的特性，10 > 9，是以值為10的結點隻可能在根結點的右子樹當中，我們檢視右孩子結點13：
3.由于10 < 13，是以檢視左孩子11：
4.由于10 < 11，是以檢視左孩子10，發現10正是要查找的結點：
假設初始的二叉查找樹隻有三個結點，根結點值為9，左孩子值為8，右孩子值為12：
接下來我們依次插入如下五個結點：7,6,5,4,3。依照二叉查找樹的特性，結果會變成什麼樣呢？
1.結點是紅色或黑色。
2.根結點是黑色。
3.每個葉子結點都是黑色的空結點（NIL結點）。
4 每個紅色結點的兩個子結點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色結點)
5.從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。
下圖中這棵樹，就是一顆典型的紅黑樹：
什麼情況下會破壞紅黑樹的規則，什麼情況下不會破壞規則呢？我們舉兩個簡單的例子：
1.向原紅黑樹插入值為14的新結點：
由于父結點15是黑色結點，是以這種情況并不會破壞紅黑樹的規則，無需做任何調整。
2.向原紅黑樹插入值為21的新結點：
由于父結點22是紅色結點，是以這種情況打破了紅黑樹的規則4（每個紅色結點的兩個子結點都是黑色），必須進行調整，使之重新符合紅黑樹的規則。
變色：
為了重新符合紅黑樹的規則，嘗試把紅色結點變為黑色，或者把黑色結點變為紅色。
下圖所表示的是紅黑樹的一部分（子樹），新插入的結點Y是紅色結點，它的父親結點X也是紅色的，不符合規則4，是以我們可以把結點X從紅色變成黑色：
但是，僅僅把一個結點變色，會導緻相關路徑憑空多出一個黑色結點，這樣就打破了規則5。是以，我們需要對其他結點做進一步的調整，後文會詳細說明。
左旋轉：
逆時針旋轉紅黑樹的兩個結點，使得父結點被自己的右孩子取代，而自己成為自己的左孩子。說起來很怪異，大家看下圖：
圖中，身為右孩子的Y取代了X的位置，而X變成了自己的左孩子。此為左旋轉。
右旋轉：
順時針旋轉紅黑樹的兩個結點，使得父結點被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：
圖中，身為左孩子的Y取代了X的位置，而X變成了自己的右孩子。此為右旋轉。
局面1：新結點（A）位于樹根，沒有父結點。
(空心三角形代表結點下面的子樹)
這種局面，直接讓新結點變色為黑色，規則2得到滿足。同時，黑色的根結點使得每條路徑上的黑色結點數目都增加了1，是以并沒有打破規則5。
局面2：新結點（B）的父結點是黑色。
這種局面，新插入的紅色結點B并沒有打破紅黑樹的規則，是以不需要做任何調整。
局面3：新結點（D）的父結點和叔叔結點都是紅色。
這種局面，兩個紅色結點B和D連續，違反了規則4。是以我們先讓結點B變為黑色：
這樣一來，結點B所在路徑憑空多了一個黑色結點，打破了規則5。是以我們讓結點A變為紅色：
這時候，結點A和C又成為了連續的紅色結點，我們再讓結點C變為黑色：
經過上面的調整，這一局部重新符合了紅黑樹的規則。
局面4：新結點（D）的父結點是紅色，叔叔結點是黑色或者沒有叔叔，且新結點是父結點的右孩子，父結點（B）是祖父結點的左孩子。
我們以結點B為軸，做一次左旋轉，使得新結點D成為父結點，原來的父結點B成為D的左孩子：
這樣一來，進入了局面5。
局面5：新結點（D）的父結點是紅色，叔叔結點是黑色或者沒有叔叔，且新結點是父結點的左孩子，父結點（B）是祖父結點的左孩子。
我們以結點A為軸，做一次右旋轉，使得結點B成為祖父結點，結點A成為結點B的右孩子：
接下來，我們讓結點B變為黑色，結點A變為紅色：
經過上面的調整，這一局部重新符合了紅黑樹的規則。
以上就是紅黑樹插入操作所涉及的5種局面。
或許有人會問，如果局面4和局面5當中的父結點B是祖父結點A的右孩子該怎麼辦呢？
很簡單，如果局面4中的父結點B是右孩子，則成為了局面5的鏡像，原本的右旋操作改為左旋；如果局面5中的父結點B是右孩子，則成為了局面4的鏡像，原本的左旋操作改為右旋。
給定下面這顆紅黑樹，新插入的結點是21：
顯然，新結點21和它的父結點22是連續的紅色結點，違背了規則4，我們應該如何調整呢？
讓我們回顧一下剛才講的5種局面，目前的情況符合局面3：
“新結點的父結點和叔叔結點都是紅色。”
于是我們經過三次變色，22變為黑色，25變為紅色，27變為黑色：
經過上面的調整，以結點25為根的子樹符合了紅黑樹規則，但結點25和結點17成為了連續的紅色結點，違背規則4。
于是，我們把結點25看做一個新結點，正好符合局面5的鏡像：
“新結點的父結點是紅色，叔叔結點是黑色或者沒有叔叔，且新結點是父結點的右孩子，父結點是祖父結點的右孩子”
于是我們以根結點13為軸進行左旋轉，使得結點17成為了新的根結點：
接下來，讓結點17變為黑色，結點13變為紅色：
如此一來，我們的紅黑樹變得重新符合規則。