一文徹底理解紅黑樹
紅黑樹？好熟悉，一文理解，走起！
什么是紅黑樹
首先，紅黑樹也是一種平衡二叉搜索樹，也是一種平衡樹，就是不會出現(xiàn)嚴重“瘸腿”的現(xiàn)象，出現(xiàn)了就會自動觸發(fā)平衡操作來維持整棵樹的平衡！
為了解決二叉搜索樹的平衡問題出現(xiàn)了平衡樹，而平衡樹的兩大代表可以說就是AVL樹和紅黑樹，就目前這狀況，紅黑樹更加吃香！
既然有了AVL樹為什么還要有紅黑樹呢？
自然是AVL還不夠好，某些方面還能優(yōu)化改進，首先大家應(yīng)該知道，AVL樹的平衡是依據(jù)平衡因子，就是左右子樹高度差不能大于1，這個規(guī)則其實過于嚴格，帶來的結(jié)果就是幾乎每次的插入刪除新節(jié)點都會破壞平衡！
平衡一旦被破壞就會觸發(fā)自平衡操作，也就是通過左旋或者右旋來自平衡，所以在插入刪除比較多的操作中，AVL會進行頻繁的旋轉(zhuǎn)，這就造成了性能下降，可以說，紅黑樹就是為了解決這個問題！
我們知道這些數(shù)據(jù)結(jié)構(gòu)都是進行一步步的優(yōu)化，由原先的數(shù)據(jù)結(jié)構(gòu)加上新的規(guī)則然后產(chǎn)生新的數(shù)據(jù)機構(gòu)，紅黑樹可以說是AVL的進一步優(yōu)化吧，所以自然是多了一些規(guī)則的，紅黑樹具有如下特點：
也是一種二叉查找樹，所以具有二叉查找樹的特點，也就是比左邊的都大，比右邊的都小 根節(jié)點是黑色 默認將空節(jié)點作為葉子結(jié)點，且是黑色 紅色節(jié)點的左右孩子必須是黑色 每個節(jié)點到達其所有可達葉子節(jié)點路徑上的黑色節(jié)點數(shù)量必須一致 每個節(jié)點要么紅色要么黑色
滿足上述規(guī)則的就是一個紅黑樹了，畫個圖，直觀感受一下：
這就是一個基本的紅黑樹了！
解讀紅與黑
我們直觀的去看紅黑樹，與AVL最大的區(qū)別可能就是紅色與黑色了，在紅黑樹中，用紅色和黑色給每個節(jié)點著色，通過顏色來維持平衡！
也就是說，在紅黑樹中，每個節(jié)點都有一個顏色屬性，也就是每個節(jié)點要么是黑色，要么就是紅色，而且每個節(jié)點的紅色黑色也不是隨意的，而是有規(guī)則的！
比如根節(jié)點必須是黑色，然后紅色節(jié)點的兩個孩子必須是黑色等等，也就是紅黑樹的一些特性，主要就是對紅色和黑色的節(jié)點分布做控制，從而達到一種平衡！
那為什么是紅色和黑色而不是藍色和綠色呢？
不知道大家有沒有想過這個問題，其實吧，你叫藍綠樹也行！
什么意思呢？
紅黑樹這個名字自然是發(fā)明者給起的，紅黑樹是由R. Sedgewick和他的學(xué)弟L. J.Guibas兩個人合作研究出來的！
至于為啥叫紅黑樹，可能他們倆都比較喜歡紅黑這兩種顏色吧，又或者紅色和黑色對比更加明顯，不像黑色和灰黑色這種，對比不明顯！
那有人說了，為什么不黑白呢？豈不是對比更明顯，這樣說你就沒有考慮打印的場景，一般紙都是白色的，你打印出來，那不就看不見了～
所以這個顏色為啥是紅色和黑色，完全不用深究，我們需要關(guān)注是應(yīng)該是使用兩種顏色來達到維持平衡的目的！
紅黑樹的破壞
上面我們也說了，紅黑樹主要就是依據(jù)紅黑兩種顏色作為限制去維持一個平衡，那什么情況下，或觸發(fā)自平衡，也就是什么情況下平衡被打破了，我們來看一個例子：
此時還是一顆紅黑樹嗎？答案是的，因為現(xiàn)在依然符合紅黑樹的規(guī)則，這個時候就不用做任何調(diào)整，但是如果是下面這樣：
此時就不是紅黑樹了，為啥？因為它破壞了紅黑樹的這個規(guī)則：
任意節(jié)點到該節(jié)點可達葉子結(jié)點路徑上的所有黑色節(jié)點數(shù)量是一樣的
咋回事，看圖：
這個時候就得進行調(diào)整了，也就是會觸發(fā)自平衡，通過調(diào)整重新讓它符合紅黑樹的規(guī)則！
那該怎么調(diào)整呢？
紅黑樹的平衡
對于紅黑樹的平衡，有兩種方法：
通過旋轉(zhuǎn)，也就是和AVL的旋轉(zhuǎn)一樣，左旋和右旋 通過改變節(jié)點的顏色，也就是對節(jié)點重新著色
變色
我們先來看變色，現(xiàn)在是這樣：
也就是插入了一個黑色節(jié)點31導(dǎo)致紅黑樹失衡了，怎么搞？通過變色也就是對節(jié)點重新變色來重新達到紅黑樹平衡！
那怎么變呢？首先插入的31是黑色節(jié)點，導(dǎo)致這個路徑上的黑色節(jié)點多了一個，所以我們需要減少一個黑色節(jié)點，這個時候就需要把一個黑色節(jié)點給變成紅色節(jié)點！
這個時候我們看，根節(jié)點20沒法變，必須是黑色，然后29本身就是紅色節(jié)點，咋搞，只能是黑色節(jié)點變成紅色了，也就是這樣：
但是這個時候也有問題了，不滿足：
一個紅色節(jié)點的兩個孩子必須是黑色
咋搞，只能把節(jié)點29變黑了，也就是這樣：
這個時候就要注意看了，此時根節(jié)點20的右子樹路徑上的黑色節(jié)點都是一樣的，都是3個，此時會發(fā)現(xiàn)，左子樹上的少一個黑色節(jié)點，也就是只需要把節(jié)點10變成黑色，整個紅黑樹就平衡了
以上就是通過變色的方式去調(diào)整使得紅黑樹再次達到平衡！
旋轉(zhuǎn)
接下來我們再來看如何通過旋轉(zhuǎn)來調(diào)整紅黑樹，在說之前，有必要先來了解下旋轉(zhuǎn)的基礎(chǔ)操作左旋和右旋，看圖：
要記住，左旋是逆時針操作，而右旋是順時針操作，如圖：
這里有個左右旋的口訣：
左旋：左右左，也就是左旋是把該節(jié)點作為其右孩子的左孩子
右旋：右左右，也就是右旋就是把該節(jié)點作為其左孩子的右孩子
看個例子：
以上就是一個左旋的案例，也就是對節(jié)點5進行左旋，根據(jù)口訣“左右左”，就是對節(jié)點5左旋，然后將節(jié)點5作為自己右孩子節(jié)點7的左孩子，這里會遇到位置被占用的情況，那這個時候的做法就是將占用位置的節(jié)點6作為節(jié)點5的右孩子！
所以把口訣補充一下就是：
左旋：左 - 右 - 左 - 右（把趕走的節(jié)點作為該節(jié)點的右孩子）
右旋：右 - 左 - 右 - 左（把趕走的節(jié)點作為該節(jié)點的左孩子）
關(guān)于左右旋，主要的就是先搞懂旋轉(zhuǎn)的方向，然后對旋轉(zhuǎn)的節(jié)點依據(jù)口訣來操作，這塊自己可以多練習(xí)一下，就會慢慢體會到口訣的妙處了！
接著我們來看通過旋轉(zhuǎn)的操作使得紅黑樹達到重新平衡，看下面的一個案例：
我們看這樣的一顆紅黑樹，此時沒啥問題，不過如果我要加入一個新的紅色節(jié)點21會怎樣？是不是就成了這樣：
這樣紅黑樹就不平衡了，不滿足：
每個紅色節(jié)點的左右孩子必須是黑色節(jié)點
怎么弄？你可能會說變色啊，好，那我們試試變色，此時新插入的節(jié)點是紅色節(jié)點21，變色的話那就是把其父節(jié)點24由紅色變成黑色，也就是此時這樣：
但是現(xiàn)在也出現(xiàn)新問題了，就是每條路徑上的黑色節(jié)點數(shù)量不一致，怎么辦？黑色節(jié)點25由黑變紅？
這樣可以了嗎？答案是不可以，請一定注意看這條規(guī)則：
每個節(jié)點到達其所有可達葉子節(jié)點路徑上的黑色節(jié)點數(shù)量必須一致
有人可能會說，這不是一致的嗎，黑色節(jié)點不都是兩個，大家一定注意了，不是這樣的，不知道大家在看紅黑樹定義的時候有沒有疑惑這條規(guī)則：
默認將空節(jié)點作為葉子結(jié)點，且是黑色
據(jù)我了解，很多人會把這個規(guī)則忽視掉，而一旦把這個規(guī)則忽視，你就會對紅黑樹的一些平衡產(chǎn)生疑問，甚至深陷其中，根據(jù)這個規(guī)則，我們把上面的情況補充下就是這樣的：
我相信大家看到這個就會一眼看出問題所在吧，也就是紅色節(jié)點25，它的左右子樹路徑上的黑色節(jié)點可是不一樣的??！發(fā)現(xiàn)沒？
所以，我建議學(xué)習(xí)紅黑樹自己畫圖的時候最好是把黑色空節(jié)點給畫出來！這樣你才能真正的去理解紅黑樹的一些規(guī)則！避免不必要的一些誤解！
那此時我們再看這個該怎么處理：
此時節(jié)點25紅色，但是該節(jié)點的左右子樹路徑上的黑色節(jié)點不一致，在往上變色已經(jīng)沒意義了，所以此時要對紅色節(jié)點25進行旋轉(zhuǎn)操作，怎么選？可以發(fā)現(xiàn)它的左子樹過深，所以進行右旋：
最終也就是成了這個樣子：
這塊一定要理解，很多人對紅黑樹理解的不透徹，比較模糊，有一部原因就是因為這個，為了幫助大家理解，我再繼續(xù)講解這塊的要點！
重點理解
有一條紅黑樹的規(guī)則千萬不要忽視：
默認將空節(jié)點作為葉子結(jié)點，且是黑色
這個是幫助我們更好理解：
每個節(jié)點到達其所有可達葉子節(jié)點路徑上的黑色節(jié)點數(shù)量必須一致
我們繼續(xù)看一個例子，假如我們從頭開始構(gòu)建一顆紅黑樹，首先插入第一個節(jié)點，紅色節(jié)點24：
因為是第一個節(jié)點，所以根節(jié)點必須是黑色，因此我們需要把顏色變成黑色：
此時其實就是一顆紅黑樹，我們補充葉子空節(jié)點：
這樣看著是不是更加順眼，接著我們加入新的紅色節(jié)點21，如圖：
沒啥問題，此時依然是一顆紅黑樹，不用做任何調(diào)整，接下來我們再次加入新的紅色節(jié)點18:
此時就有問題了，不能有兩個連續(xù)的紅色節(jié)點，也就是每個紅色節(jié)點的左右孩子必須是黑色，這個時候怎么辦？
記住，紅黑樹失衡后，可以通過變色和旋轉(zhuǎn)來重新平衡，有的時候只需要單獨變色或者旋轉(zhuǎn)即可以平衡，而有的時候需要兩者結(jié)合才能達到平衡，如果是兩者結(jié)合的話，先變色還是先旋轉(zhuǎn)其實都可以，我習(xí)慣先變色
這個時候我們可以通過變色去處理，那變色有什么規(guī)律嗎？
我們一般插入的新節(jié)點默認都是紅色，為什么？
這是因為更好的適應(yīng)紅黑樹的這條規(guī)則：
每個節(jié)點到達其所有可達葉子節(jié)點路徑上的黑色節(jié)點數(shù)量必須一致
試想一下，如果默認插入是黑色，那一定會破壞平衡，每次插入都需要重新平衡，而默認紅色就不一定每次都破壞平衡，所以默認都是插入的紅色節(jié)點！
了解了這個我們繼續(xù)把注意力拉回到這張圖上：
此時我們新插入的紅色節(jié)點18導(dǎo)致了紅黑樹失衡，然后我們通過變色，怎么變？記住，向上變，也就是變其父節(jié)點的顏色，這里就是把紅色節(jié)點21變成黑色：
經(jīng)過變色，現(xiàn)在就成了這樣，要記住，此時依然是不平衡的，依然不滿足：
每個節(jié)點到達其所有可達葉子節(jié)點路徑上的黑色節(jié)點數(shù)量必須一致
不滿足的點就是根節(jié)點24，我們稱之為失衡點，那繼續(xù)變色啊，此時繼續(xù)向上變色，也即是把根節(jié)點24變成紅色：
可以看到此時，紅黑樹依然不平衡，咋整？沒節(jié)點可以繼續(xù)變色啦，已經(jīng)變到根節(jié)點了，那此時就要進行旋轉(zhuǎn)了，怎么旋轉(zhuǎn)，左側(cè)深，那就是右旋，就是對根節(jié)點24（因為24是一個失衡點，左右路徑上黑色節(jié)點不一致）進行右旋操作：
如此一來，紅黑樹重新達到平衡！
這里有幾個關(guān)鍵點要知道：
1、要清楚為什么每次插入的都是紅色節(jié)點
2、要注意存在空子樹的時候是否符合任意節(jié)點路徑上的黑色節(jié)點數(shù)量一致
3、可以通過變色和旋轉(zhuǎn)來重新平衡，需要兩者結(jié)合的時候，先變色或者先旋轉(zhuǎn)都行，只要最后達到平衡即可
紅黑樹的刪除
接下來聊聊紅黑樹的刪除操作，直接看例子：
這是一顆正兒八經(jīng)的紅黑樹，現(xiàn)在我們刪除一個節(jié)點，比如刪除節(jié)點31，成了這樣：
直接刪除即可，依然保持平衡，不用做任何操作（紅色葉子節(jié)點直接刪除），但是如果我們刪除的是這個節(jié)點呢？
隨之而來的問題就是節(jié)點13和節(jié)點20哪個與根節(jié)點25相連？
刪除的節(jié)點是非葉子節(jié)點，則用對應(yīng)的中序遍歷的前繼節(jié)點頂替要刪除節(jié)點的位置，刪除之后再做重新平衡的操作（如有需要）
然后我們來看該二叉樹的中序遍歷順序：
這里中序遍歷有個技巧，就是：
按照節(jié)點值大小從小到那排序即可
知道了中序遍歷的順序以后，我們就可以進行紅黑樹的刪除了，比如刪除節(jié)點16，那就需要找到節(jié)點16的前驅(qū)節(jié)點也就是節(jié)點13將其替代，也就是這樣：
此時原本黑色節(jié)點16就被它的前驅(qū)節(jié)點也即是紅色節(jié)點13覆蓋了，覆蓋完以后需要把原來的節(jié)點13刪掉，也就成了這樣：
此時發(fā)現(xiàn)紅黑樹不平衡了，就需要進行調(diào)整，怎么調(diào)整呢？自然是變色，需要把新上位的節(jié)點13從原來的紅色變成黑色：
最終這樣就達到了平衡，來動圖感受一下：
緊接著，我們再看一種情況，還是下面這棵紅黑樹：
假如現(xiàn)在我要刪除根節(jié)點25會怎樣？直接動圖感受一下：
根據(jù)動圖我們可以發(fā)現(xiàn)，先找到要刪除的節(jié)點25，然后就去找25的前驅(qū)節(jié)點20，將20復(fù)制一份覆蓋掉要刪除的節(jié)點25，然后刪除掉節(jié)點20，因為節(jié)點20是紅色，根節(jié)點必須黑色，所以覆蓋后還需要將節(jié)點20調(diào)整為黑色，至此紅黑樹平衡！
對于刪除，重要的就是找到要代替刪除節(jié)點的新節(jié)點，刪除后如果紅黑樹平衡遭到破壞就需要進行自平衡以達到紅黑樹的再次平衡！
關(guān)于紅黑樹的刪除操作，公認是比較難且復(fù)雜的，對于學(xué)習(xí)來說，我們需要掌握最基本的紅黑樹規(guī)則，然后知曉一些替換技巧等，剩下的就是依據(jù)具體刪除的節(jié)點去做自平衡操作，也就是刪除節(jié)點后，需要進行一系列的操作將紅黑樹再次達到平衡！
重點推薦一個可視化網(wǎng)站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
小結(jié)
紅黑樹是個比較難的高級數(shù)據(jù)結(jié)構(gòu)，我們需要掌握最核心的理論知識，理解其紅黑兩種顏色對平衡的制約，以及熟悉平衡樹的旋轉(zhuǎn)操作，剩下的就是根據(jù)情況，在紅黑樹平衡遭到破壞以后依據(jù)變色和旋轉(zhuǎn)來重新修復(fù)紅黑樹，使其在此達到平衡！
對于紅黑樹的代碼，這里不做講解，因為的確很復(fù)雜（想看看的可以往上搜搜嗎，各個語言版本都有），沒必要花那個時間去研究甚至手寫紅黑樹代碼，重點是理解紅黑樹是怎么一回事，而不是要你可以手擼紅黑樹，如果面試的時候，讓我手寫紅黑樹，我只能說一句“告辭！”
對了，另外還需知曉一下紅黑樹的插入和刪除操作的時間復(fù)雜度都是O(logN)！
ok，關(guān)于紅黑樹，我們就聊到這里！
更多數(shù)據(jù)結(jié)構(gòu)內(nèi)容請看：