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