漫畫:什么是紅黑樹?
————————————
————————————
二叉查找樹（BST）具備什么特性呢？
1.左子樹上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值。
2.右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值。
3.左、右子樹也分別為二叉排序樹。
下圖中這棵樹，就是一顆典型的二叉查找樹：
1.查看根節(jié)點(diǎn)9：
2.由于10 > 9，因此查看右孩子13：
3.由于10 < 13，因此查看左孩子11：
4.由于10 < 11，因此查看左孩子10，發(fā)現(xiàn)10正是要查找的節(jié)點(diǎn)：
假設(shè)初始的二叉查找樹只有三個(gè)節(jié)點(diǎn)，根節(jié)點(diǎn)值為9，左孩子值為8，右孩子值為12：
接下來我們依次插入如下五個(gè)節(jié)點(diǎn)：7,6,5,4,3。依照二叉查找樹的特性，結(jié)果會(huì)變成什么樣呢？
1.節(jié)點(diǎn)是紅色或黑色。
2.根節(jié)點(diǎn)是黑色。
3.每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。
4 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
下圖中這棵樹，就是一顆典型的紅黑樹：
什么情況下會(huì)破壞紅黑樹的規(guī)則，什么情況下不會(huì)破壞規(guī)則呢？我們舉兩個(gè)簡(jiǎn)單的栗子：
1.向原紅黑樹插入值為14的新節(jié)點(diǎn)：
由于父節(jié)點(diǎn)15是黑色節(jié)點(diǎn)，因此這種情況并不會(huì)破壞紅黑樹的規(guī)則，無需做任何調(diào)整。
2.向原紅黑樹插入值為21的新節(jié)點(diǎn)：
由于父節(jié)點(diǎn)22是紅色節(jié)點(diǎn)，因此這種情況打破了紅黑樹的規(guī)則4（每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色），必須進(jìn)行調(diào)整，使之重新符合紅黑樹的規(guī)則。
變色：
為了重新符合紅黑樹的規(guī)則，嘗試把紅色節(jié)點(diǎn)變?yōu)楹谏蛘甙押谏?jié)點(diǎn)變?yōu)榧t色。
下圖所表示的是紅黑樹的一部分，需要注意節(jié)點(diǎn)25并非根節(jié)點(diǎn)。因?yàn)楣?jié)點(diǎn)21和節(jié)點(diǎn)22連續(xù)出現(xiàn)了紅色，不符合規(guī)則4，所以把節(jié)點(diǎn)22從紅色變成黑色：
但這樣并不算完，因?yàn)閼{空多出的黑色節(jié)點(diǎn)打破了規(guī)則5，所以發(fā)生連鎖反應(yīng)，需要繼續(xù)把節(jié)點(diǎn)25從黑色變成紅色：
此時(shí)仍然沒有結(jié)束，因?yàn)楣?jié)點(diǎn)25和節(jié)點(diǎn)27又形成了兩個(gè)連續(xù)的紅色節(jié)點(diǎn)，需要繼續(xù)把節(jié)點(diǎn)27從紅色變成黑色：
左旋轉(zhuǎn)：
逆時(shí)針旋轉(zhuǎn)紅黑樹的兩個(gè)節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的右孩子取代，而自己成為自己的左孩子。說起來很怪異，大家看下圖：
圖中，身為右孩子的Y取代了X的位置，而X變成了自己的左孩子。此為左旋轉(zhuǎn)。
右旋轉(zhuǎn)：
順時(shí)針旋轉(zhuǎn)紅黑樹的兩個(gè)節(jié)點(diǎn)，使得父節(jié)點(diǎn)被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：
圖中，身為左孩子的Y取代了X的位置，而X變成了自己的右孩子。此為右旋轉(zhuǎn)。
我們以剛才插入節(jié)點(diǎn)21的情況為例：
首先，我們需要做的是變色，把節(jié)點(diǎn)25及其下方的節(jié)點(diǎn)變色：
此時(shí)節(jié)點(diǎn)17和節(jié)點(diǎn)25是連續(xù)的兩個(gè)紅色節(jié)點(diǎn)，那么把節(jié)點(diǎn)17變成黑色節(jié)點(diǎn)？恐怕不合適。這樣一來不但打破了規(guī)則4，而且根據(jù)規(guī)則2（根節(jié)點(diǎn)是黑色），也不可能把節(jié)點(diǎn)13變成紅色節(jié)點(diǎn)。
變色已無法解決問題，我們把節(jié)點(diǎn)13看做X，把節(jié)點(diǎn)17看做Y，像剛才的示意圖那樣進(jìn)行左旋轉(zhuǎn)：
由于根節(jié)點(diǎn)必須是黑色節(jié)點(diǎn)，所以需要變色，變色結(jié)果如下：
這樣就結(jié)束了嗎？并沒有。因?yàn)槠渲袃蓷l路徑(17 -> 8 -> 6 -> NIL)的黑色節(jié)點(diǎn)個(gè)數(shù)是4，其他路徑的黑色節(jié)點(diǎn)個(gè)數(shù)是3，不符合規(guī)則5。
這時(shí)候我們需要把節(jié)點(diǎn)13看做X，節(jié)點(diǎn)8看做Y，像剛才的示意圖那樣進(jìn)行右旋轉(zhuǎn)：
最后根據(jù)規(guī)則來進(jìn)行變色：
如此一來，我們的紅黑樹變得重新符合規(guī)則。這一個(gè)例子的調(diào)整過程比較復(fù)雜，經(jīng)歷了如下步驟：
變色 -> 左旋轉(zhuǎn) -> 變色 -> 右旋轉(zhuǎn) -> 變色
幾點(diǎn)說明：
1. 關(guān)于紅黑樹自平衡的調(diào)整，插入和刪除節(jié)點(diǎn)的時(shí)候都涉及到很多種Case，由于篇幅原因無法展開來一一列舉，有興趣的朋友可以參考維基百科，里面講的非常清晰。
2.漫畫中紅黑樹調(diào)整過程的示例是一種比較復(fù)雜的情形，沒太看明白的小伙伴也不必鉆牛角尖，關(guān)鍵要懂得紅黑樹自平衡調(diào)整的主體思想。
—————END—————
推薦阿里云推廣服務(wù)器89/年，229/3年，買來送自己，送女朋友馬上過年再合適不過了，買了搭建個(gè)項(xiàng)目給面試官看也香，還可以熟悉技術(shù)棧，(老用戶用家人賬號(hào)買就好了，我用我女朋友的?）。掃碼購買
