大家好，我是“Stephen·謝”，之前提出的索引優(yōu)化數(shù)據(jù)庫查詢的文章中提到了樹（Tree）的概念，由于樹結(jié)構(gòu)的強大性和重要性，有必要在接下來的幾篇文章中對幾種重要的樹結(jié)構(gòu)以通俗易懂的方式做一下演示圖解。
二叉查找樹：
首先，我們來了解一下二叉查找樹,二叉查找樹具備以下幾個特點：
1、左子樹上所有節(jié)點的值均小于或等于它的根節(jié)點的值；
2、右子樹上所有節(jié)點的值均大于或等于它的根節(jié)點的值；
3、左右子樹也分別為二叉排序樹。
下面我們以一棵典型的二叉查找樹來查找值為10的節(jié)點：
以上圖例正是典型的二分查找的思想，查找所需的最大次數(shù)等同于二叉查找樹的高度。在往樹中插入新節(jié)點的時候也要用類似的方法，通過一層一層地比較大小從而找到新節(jié)點適合插入的位置。但是即便如此，二叉查找樹依舊存在它的缺陷，并且此缺陷恰恰體現(xiàn)在插入新節(jié)點的時候。請看下面圖例展示：
這樣的瘸腿形態(tài)雖然也符合二叉查找樹的特性，但是查找的性能卻大打折扣，幾乎變成了線性數(shù)據(jù)結(jié)構(gòu)。為了解決二叉查找樹多次插入新節(jié)點而導(dǎo)致的不平衡問題，紅黑樹便應(yīng)運而生了。
紅黑樹：
紅黑樹是一種自平衡的二叉查找樹，除了符合二叉查找樹的特性外，還具有下列性質(zhì)：
1、根節(jié)點是黑色，節(jié)點是紅色或黑色；
2、每個葉子節(jié)點都是黑的空節(jié)點；（nil節(jié)點）
3、每個紅色節(jié)點的兩個子節(jié)點都是黑色；（也就是說從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）
4、從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
這些規(guī)則的限制，保證了紅黑樹的平衡，紅黑樹從根到葉子的最長路徑不會超過最短路徑的兩倍。當(dāng)紅黑樹插入或者刪除節(jié)點的時候，紅黑樹的規(guī)則可能被打破，這時候就需要做出調(diào)整來維持它的平衡了。請看下面的例子（注意：新插入的節(jié)點必須是紅色，否則就沒有意義了）：
由于父節(jié)點22是也是紅色節(jié)點，因此打破了紅黑樹的規(guī)則（每個紅黑樹的兩個子節(jié)點都是黑色），所以必須進行調(diào)整，使之重新符合規(guī)則。那么我們需要作出怎樣的調(diào)整才能保證一棵紅黑樹始終是符合規(guī)則的標(biāo)準(zhǔn)紅黑樹呢？調(diào)整有兩種方法：“變色”和“旋轉(zhuǎn)”，其中，旋轉(zhuǎn)又分為兩種形式：“左旋轉(zhuǎn)”和“右旋轉(zhuǎn)”。
變色，左旋轉(zhuǎn)和右旋轉(zhuǎn)：
我們先看變色：
為了重新符合紅黑樹的規(guī)則，嘗試把紅色節(jié)點變成黑色，或者把黑色節(jié)點變成紅色。
下圖是摘自上面紅黑樹的一部分，節(jié)點25并非根節(jié)點。正如上面所說因為新節(jié)點21和節(jié)點22連續(xù)出現(xiàn)了紅色，不符合規(guī)則，所以把節(jié)點22從紅色變成黑色。
但這樣并不算完，節(jié)點22變成黑色后，憑空多出的黑色節(jié)點又打破了規(guī)則，發(fā)生連鎖反應(yīng)，需要繼續(xù)把節(jié)點25從黑色變?yōu)榧t色。
此時仍未結(jié)束，節(jié)點25變?yōu)榧t色后，又和節(jié)點27形成了兩個連續(xù)的紅色，規(guī)則又被打破，需要繼續(xù)把節(jié)點27從紅色變?yōu)楹谏?/b>
如此一路走下來，完成變色調(diào)整。
再看一下左旋轉(zhuǎn)：
逆時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點，使得父節(jié)點被自己的右孩子取代，而自己成為左孩子。
再看一下右旋轉(zhuǎn)：
順時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點，使得父節(jié)點被自己的左孩子取代，而自己成為右孩子。
綜合變色和旋轉(zhuǎn)方法的案例演示：
這幾種方法究竟怎么使用呢？紅黑樹的插入和刪除包含很多種情況，每種情況都有不同的處理方式，下面舉一個典型的例子，可以體會一下這個過程。
還以剛才插入節(jié)點21為例：
首先我們變色處理，把節(jié)點25及其下方的節(jié)點變色：
此時節(jié)點17和節(jié)點25是連續(xù)的兩個紅色節(jié)點，那么此時再把節(jié)點17變成黑色節(jié)點可以嗎？顯然是不可以的，這樣依然不符合規(guī)則，更不可以把根節(jié)點13變成紅色。
既然變色已經(jīng)無法解決問題，我們此時就要使用旋轉(zhuǎn)了，我們把節(jié)點13看作X，把節(jié)點17看作Y，進行左旋轉(zhuǎn)：
旋轉(zhuǎn)完成后，由于根節(jié)點必須是黑色，所以還需要進行變色：
至此并沒有結(jié)束，因為其中兩條路徑（17->8->6->NIL）的黑色節(jié)點數(shù)是4，其他路徑的黑色節(jié)點數(shù)是3，依舊不符合規(guī)則。這時我們需要把節(jié)點13看成X，節(jié)點8看成Y，做右旋轉(zhuǎn)：
然后再進行變色：
經(jīng)過上面一系列的調(diào)整，我們的紅黑樹終于變得重新符合規(guī)則，整個過程有點復(fù)雜，經(jīng)歷了：變色-->左旋轉(zhuǎn)-->變色-->右旋轉(zhuǎn)-->變色這樣的一系列步驟。
總結(jié)：
? ?????經(jīng)過上面細(xì)致的步驟演示，想必大家對二叉查找樹和紅黑樹有所了解了吧，對紅黑樹結(jié)構(gòu)插入新節(jié)點所觸發(fā)的一系列的變化流程也有了大概印象。實際中紅黑樹的應(yīng)用是很多的，比如JDK（Java開發(fā)工具包）的集合類TreeMap和TreeSet底層就是紅黑樹實現(xiàn)的，在Java8中，HashMap也用到了紅黑樹。其實關(guān)于紅黑樹自平衡的調(diào)整，插入和刪除節(jié)點時涉及到的情形一一展開講解還是很多很多的，但是萬變不離其中，紅黑樹自平衡調(diào)整的主體思想都是上面所敘述的，大家有興趣可以再進行深入的探究。
