• 二叉查找樹由于在頻繁的動(dòng)態(tài)更新過程中，可能會出現(xiàn)樹的高度遠(yuǎn)大于 log2n的情況，所以就會導(dǎo)致各個(gè)操作效率下降，最壞的情況下就會退化為鏈表，變?yōu)镺(n)．很明顯，想要解決這個(gè)問題，有效的一種辦法就是使得樹的高度不要差很多，也就是平衡它．

• 最先發(fā)明的平衡二叉查找樹是AVL樹，（它嚴(yán)格符合平衡二叉查找樹的定義，即任何節(jié)點(diǎn)的左右子樹高度相差不超過 1，是一種高度平衡的二叉查找樹。）但是在工程中，我們經(jīng)常聽到的通常是紅黑樹，而不是AVL樹．那么為什么工程中都喜歡用紅黑樹，而不是其他平衡二叉查找樹呢？

• 其實(shí)在這里，我們應(yīng)該能有一些想法了．既然他嚴(yán)格按照規(guī)定執(zhí)行，每次的插入，刪除，都就會引發(fā)樹的調(diào)整．調(diào)整的多了，自然會影響樹的效率．那么紅黑樹又是怎樣解決這個(gè)問題的吶？

• 其實(shí)，平衡二叉查找樹中“平衡”的意思，其實(shí)就是讓整棵樹左右看起來比較“對稱”、比較“平衡”，不要出現(xiàn)左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應(yīng)的插入、刪除、查找等操作的效率高一些。

• 所以紅黑樹就是這種設(shè)計(jì)思路(近似平衡)了．

紅黑樹的定義

• 紅黑樹的英文是“Red-Black Tree”，簡稱 R-B Tree。它是一種不嚴(yán)格的平衡二叉查找樹． 顧名思義，紅黑樹中的節(jié)點(diǎn)，一類被標(biāo)記為黑色，一類被標(biāo)記為紅色。除此之外，一棵紅黑樹還需要滿足這樣四個(gè)要求：

• 重要

1. 根節(jié)點(diǎn)是黑色的；

2. 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)，也就是說，葉子節(jié)點(diǎn)不存儲數(shù)據(jù)；

3. 任何相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色，也就是說，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開的；

4. 每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)葉子節(jié)點(diǎn)的所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)；

• 這里的第二點(diǎn)要求“葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)”，主要是為了簡化紅黑樹的代碼實(shí)現(xiàn)而設(shè)置的．現(xiàn)在，我們暫時(shí)不管這一點(diǎn)．

• 下面是兩個(gè)紅黑樹的圖例，你可以看下。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！??！前100名進(jìn)群領(lǐng)取，額外贈(zèng)送一份價(jià)值699的內(nèi)核資料包（含視頻教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)?

• 首先，我們知道二叉查找樹很多操作的性能都跟樹的高度成正比。一棵極其平衡的二叉樹（滿二叉樹或完全二叉樹）的高度大約是 log2n，所以如果要證明紅黑樹是近似平衡的，我們只需要分析，紅黑樹的高度是否比較穩(wěn)定地趨近 log2n 就好了。

• 首先，我們來看，如果我們將紅色節(jié)點(diǎn)從紅黑樹中去掉，那單純包含黑色節(jié)點(diǎn)的紅黑樹的高度是多少呢？ 紅色節(jié)點(diǎn)刪除之后，有些節(jié)點(diǎn)就沒有父節(jié)點(diǎn)了，它們會直接拿這些節(jié)點(diǎn)的祖父節(jié)點(diǎn)（父節(jié)點(diǎn)的父節(jié)點(diǎn)）作為父節(jié)點(diǎn)。所以，之前的二叉樹就變成了四叉樹。

• 這時(shí)我們可以將有些節(jié)點(diǎn)拿出來組成一個(gè)完全二叉樹，而完全二叉樹的高度是 log2n ,很明顯，我們的四叉樹根本不會高于 log2n

• 我們現(xiàn)在知道只包含黑色節(jié)點(diǎn)的“黑樹”的高度，那我們現(xiàn)在把紅色節(jié)點(diǎn)加回去，高度會變成多少呢？

• 從上面我畫的紅黑樹的例子和定義看，在紅黑樹中，紅色節(jié)點(diǎn)不能相鄰，也就是說，有一個(gè)紅色節(jié)點(diǎn)就要至少有一個(gè)黑色節(jié)點(diǎn)，將它跟其他紅色節(jié)點(diǎn)隔開．紅黑樹中包含最多黑色節(jié)點(diǎn)的路徑不會超過 log2n，所以加入紅色節(jié)點(diǎn)之后，最長路徑不會超過 2log2n，也就是說，紅黑樹的高度近似 2log2n。

• 所以，紅黑樹的高度只比高度平衡的 AVL 樹的高度（log2n）僅僅大了一倍，在性能上，下降得并不多。這樣推導(dǎo)出來的結(jié)果不夠精確，實(shí)際上紅黑樹的性能更好。

• OK，紅黑樹的原理我們已經(jīng)知道了，那么我們現(xiàn)在就來了解一下它的實(shí)現(xiàn)思想

• 實(shí)現(xiàn)紅黑樹的基本思想

• 在極客時(shí)間中老師用了魔方的例子來講解其思想，我覺得很恰當(dāng)．這里直接拿來用

• 不知道你有沒有玩過魔方？其實(shí)魔方的復(fù)原解法是有固定算法的：遇到哪幾面是什么樣子，對應(yīng)就怎么轉(zhuǎn)幾下。你只要跟著這個(gè)復(fù)原步驟，就肯定能將魔方復(fù)原。

• 實(shí)際上，紅黑樹的平衡過程跟魔方復(fù)原非常神似，大致過程就是：遇到什么樣的節(jié)點(diǎn)排布，我們就對應(yīng)怎么去調(diào)整。只要按照這些固定的調(diào)整規(guī)則來操作，就能將一個(gè)非平衡的紅黑樹調(diào)整成平衡的。

• 其實(shí)想想AVL樹，不就是這樣嗎？在想想計(jì)算機(jī)，不就是不斷"重復(fù)"的去做一些事情的嗎？

• 和AVL樹一樣，在進(jìn)行節(jié)點(diǎn)的插入和刪除時(shí)，就會破壞紅黑樹的一些規(guī)則．在紅黑樹中主要破壞的是以下兩點(diǎn)：

1. 任何相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色，也就是說，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開的；

2. 每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)葉子節(jié)點(diǎn)的所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)；

• 很顯然，我們需要也僅僅需要處理的就是如何把被破壞了的這兩點(diǎn)規(guī)則還原回去．在還原之前，我們需要了解兩個(gè)很重要的操作：左旋與右旋（圍繞某個(gè)節(jié)點(diǎn)的右旋）， 如圖，其中 a，b，r 表示子樹，可以為空。

• 感覺有個(gè)動(dòng)畫的效果是最好的了，哈哈哈～～不過也可以自己在腦中想象了啦

• 插入

• 紅黑樹規(guī)定，插入的節(jié)點(diǎn)必須是紅色的。而且，二叉查找樹中新插入的節(jié)點(diǎn)都是放在葉子節(jié)點(diǎn)上。所以，關(guān)于插入操作的平衡調(diào)整，有這樣兩種特殊情況，但是也都非常好處理。

1. 如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的，那我們什么都不用做，它仍然滿足紅黑樹的定義。

2. 如果插入的節(jié)點(diǎn)是根節(jié)點(diǎn)，那我們直接改變它的顏色，把它變成黑色就可以了。

• 其他：都會違背紅黑樹的定義，于是我們就需要進(jìn)行調(diào)整，調(diào)整的過程包含兩種基礎(chǔ)的操作：左右旋轉(zhuǎn)和改變顏色。

• 其他情況主要有三種，如果要實(shí)現(xiàn)，可以對應(yīng)各個(gè)情況各個(gè)擊破，紅黑樹的平衡調(diào)整過程是一個(gè)迭代的過程。就想魔方一樣?。?！對應(yīng)規(guī)則調(diào)整就行了．

• 刪除

• 刪除操作的平衡調(diào)整分為兩步，第一步是針對刪除節(jié)點(diǎn)初步調(diào)整。初步調(diào)整只是保證整棵紅黑樹在一個(gè)節(jié)點(diǎn)刪除之后，仍然滿足最后一條定義的要求，也就是說，每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)葉子節(jié)點(diǎn)的所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)；第二步是針對關(guān)注節(jié)點(diǎn)進(jìn)行二次調(diào)整，讓它滿足紅黑樹的第三條定義，即不存在相鄰的兩個(gè)紅色節(jié)點(diǎn)。

1. 針對刪除節(jié)點(diǎn)初步調(diào)整

• 紅黑樹的定義中“只包含紅色節(jié)點(diǎn)和黑色節(jié)點(diǎn)”，經(jīng)過初步調(diào)整之后，為了保證滿足紅黑樹定義的最后一條要求，有些節(jié)點(diǎn)會被標(biāo)記成兩種顏色，“紅 - 黑”或者“黑 - 黑”。如果一個(gè)節(jié)點(diǎn)被標(biāo)記為了“黑 - 黑”，那在計(jì)算黑色節(jié)點(diǎn)個(gè)數(shù)的時(shí)候，要算成兩個(gè)黑色節(jié)點(diǎn)。

• 這里具體有：三種情況

2. 針對關(guān)注節(jié)點(diǎn)進(jìn)行二次調(diào)整

• 經(jīng)過初步調(diào)整之后，關(guān)注節(jié)點(diǎn)變成了“紅 - 黑”或者“黑 - 黑”節(jié)點(diǎn)。針對這個(gè)關(guān)注節(jié)點(diǎn)，我們再分四種情況來進(jìn)行二次調(diào)整。二次調(diào)整是為了讓紅黑樹中不存在相鄰的紅色節(jié)點(diǎn)。

• 這里具體有：四種情況

• 提問：

1. 如何理解紅黑樹定義的＂任何相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色＂？ ? 如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子都是黑色的．也就是說只要用線連起來的都不能同時(shí)是紅色

2. 如何理解紅黑樹定義的＂每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)葉子節(jié)點(diǎn)的所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)； ＂？ ? nullptr ．

3. 為什么插入的節(jié)點(diǎn)偏偏是紅色呢？

• ? 將插入的結(jié)點(diǎn)著色為紅色，不會違背 “性質(zhì) 4”。而少違背一條性質(zhì)，就意味著我們需要處理的情況越少。

1. 為什么紅黑樹的定義中，要求葉子節(jié)點(diǎn)是黑色的空節(jié)點(diǎn)？或者說是到底那里方便了？

• ?只要滿足這一條要求，那在任何時(shí)刻，紅黑樹的平衡操作都可以歸結(jié)為上面的那幾種情況。而且是簡潔的．

2. 給紅黑樹添加黑色的空的葉子節(jié)點(diǎn)，會不會比較浪費(fèi)存儲空間呢?

• ? 一張圖給你，立馬明白：

1. 為什么平衡的二叉樹（滿二叉樹或完全二叉樹）的高度大約是 log2n？？

• 時(shí)間復(fù)雜度其實(shí)都跟樹的高度成正比，也就是 O(height)。既然這樣，現(xiàn)在問題就轉(zhuǎn)變成另外一個(gè)了，也就是，如何求一棵包含 n 個(gè)節(jié)點(diǎn)的完全二叉樹的高度？

• 樹的高度就等于最大層數(shù)減一，為了方便計(jì)算，我們轉(zhuǎn)換成層來表示。從圖中可以看出，包含 n 個(gè)節(jié)點(diǎn)的完全二叉樹中，第一層包含 1 個(gè)節(jié)點(diǎn)，第二層包含 2 個(gè)節(jié)點(diǎn)，第三層包含 4 個(gè)節(jié)點(diǎn)，依次類推，下面一層節(jié)點(diǎn)個(gè)數(shù)是上一層的 2 倍，第 K 層包含的節(jié)點(diǎn)個(gè)數(shù)就是 2^(K-1)。

• 不過，對于完全二叉樹來說，最后一層的節(jié)點(diǎn)個(gè)數(shù)有點(diǎn)兒不遵守上面的規(guī)律了。它包含的節(jié)點(diǎn)個(gè)數(shù)在 1 個(gè)到 2^(L-1) 個(gè)之間（我們假設(shè)最大層數(shù)是 L）。如果我們把每一層的節(jié)點(diǎn)個(gè)數(shù)加起來就是總的節(jié)點(diǎn)個(gè)數(shù) n。也就是說，如果節(jié)點(diǎn)的個(gè)數(shù)是 n，那么 n 滿足這樣一個(gè)關(guān)系：

借助等比數(shù)列的求和公式，我們可以計(jì)算出，L 的范圍是 [log2(n+1), log2n +1]。完全二叉樹的層數(shù)小于等于 log2n +1，也就是說，完全二叉樹的高度小于等于 log2n。