linux內核開發技術詳解學習（一篇帶你全面了解Linux內核-紅黑樹原理）

2023-05-07 23:36:42 2

二叉查找樹由於在頻繁的動態更新過程中，可能會出現樹的高度遠大於 log2n的情況，所以就會導致各個操作效率下降，最壞的情況下就會退化為鍊表，變為O(n)．很明顯，想要解決這個問題，有效的一種辦法就是使得樹的高度不要差很多，也就是平衡它．最先發明的平衡二叉查找樹是AVL樹，（它嚴格符合平衡二叉查找樹的定義，即任何節點的左右子樹高度相差不超過 1，是一種高度平衡的二叉查找樹。）但是在工程中，我們經常聽到的通常是紅黑樹，而不是AVL樹．那麼為什麼工程中都喜歡用紅黑樹，而不是其他平衡二叉查找樹呢？其實在這裡，我們應該能有一些想法了．既然他嚴格按照規定執行，每次的插入，刪除，都就會引發樹的調整．調整的多了，自然會影響樹的效率．那麼紅黑樹又是怎樣解決這個問題的吶？其實，平衡二叉查找樹中「平衡」的意思，其實就是讓整棵樹左右看起來比較「對稱」、比較「平衡」，不要出現左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應的插入、刪除、查找等操作的效率高一些。所以紅黑樹就是這種設計思路(近似平衡)了．

更多linux內核視頻教程文檔資料免費領取後臺私信【內核】自行獲取.

Linux內核源碼/內存調優/文件系統/進程管理/設備驅動/網絡協議棧-學習視頻教程-騰訊課堂

紅黑樹的定義紅黑樹的英文是「Red-Black Tree」，簡稱 R-B Tree。它是一種不嚴格的平衡二叉查找樹．顧名思義，紅黑樹中的節點，一類被標記為黑色，一類被標記為紅色。除此之外，一棵紅黑樹還需要滿足這樣四個要求：重要根節點是黑色的；每個葉子節點都是黑色的空節點，也就是說，葉子節點不存儲數據；任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的；每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；這裡的第二點要求「葉子節點都是黑色的空節點」，主要是為了簡化紅黑樹的代碼實現而設置的．現在，我們暫時不管這一點．下面是兩個紅黑樹的圖例，你可以看下。

為什麼紅黑樹是近似平衡的吶？首先，我們知道二叉查找樹很多操作的性能都跟樹的高度成正比。一棵極其平衡的二叉樹（滿二叉樹或完全二叉樹）的高度大約是 log2n，所以如果要證明紅黑樹是近似平衡的，我們只需要分析，紅黑樹的高度是否比較穩定地趨近 log2n 就好了。首先，我們來看，如果我們將紅色節點從紅黑樹中去掉，那單純包含黑色節點的紅黑樹的高度是多少呢？紅色節點刪除之後，有些節點就沒有父節點了，它們會直接拿這些節點的祖父節點（父節點的父節點）作為父節點。所以，之前的二叉樹就變成了四叉樹。

這時我們可以將有些節點拿出來組成一個完全二叉樹，而完全二叉樹的高度是 log2n ,很明顯，我們的四叉樹根本不會高於 log2n我們現在知道只包含黑色節點的「黑樹」的高度，那我們現在把紅色節點加回去，高度會變成多少呢？從上面我畫的紅黑樹的例子和定義看，在紅黑樹中，紅色節點不能相鄰，也就是說，有一個紅色節點就要至少有一個黑色節點，將它跟其他紅色節點隔開．紅黑樹中包含最多黑色節點的路徑不會超過 log2n，所以加入紅色節點之後，最長路徑不會超過 2log2n，也就是說，紅黑樹的高度近似 2log2n。所以，紅黑樹的高度只比高度平衡的 AVL 樹的高度（log2n）僅僅大了一倍，在性能上，下降得並不多。這樣推導出來的結果不夠精確，實際上紅黑樹的性能更好。OK，紅黑樹的原理我們已經知道了，那麼我們現在就來了解一下它的實現思想實現紅黑樹的基本思想在極客時間中老師用了魔方的例子來講解其思想，我覺得很恰當．這裡直接拿來用不知道你有沒有玩過魔方？其實魔方的復原解法是有固定算法的：遇到哪幾面是什麼樣子，對應就怎麼轉幾下。你只要跟著這個復原步驟，就肯定能將魔方復原。實際上，紅黑樹的平衡過程跟魔方復原非常神似，大致過程就是：遇到什麼樣的節點排布，我們就對應怎麼去調整。只要按照這些固定的調整規則來操作，就能將一個非平衡的紅黑樹調整成平衡的。其實想想AVL樹，不就是這樣嗎？在想想計算機，不就是不斷"重複"的去做一些事情的嗎？和AVL樹一樣，在進行節點的插入和刪除時，就會破壞紅黑樹的一些規則．在紅黑樹中主要破壞的是以下兩點：任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的；每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；很顯然，我們需要也僅僅需要處理的就是如何把被破壞了的這兩點規則還原回去．在還原之前，我們需要了解兩個很重要的操作：左旋與右旋（圍繞某個節點的右旋），如圖，其中 a，b，r 表示子樹，可以為空。

感覺有個動畫的效果是最好的了，哈哈哈～～不過也可以自己在腦中想像了啦插入紅黑樹規定，插入的節點必須是紅色的。而且，二叉查找樹中新插入的節點都是放在葉子節點上。所以，關於插入操作的平衡調整，有這樣兩種特殊情況，但是也都非常好處理。如果插入節點的父節點是黑色的，那我們什麼都不用做，它仍然滿足紅黑樹的定義。如果插入的節點是根節點，那我們直接改變它的顏色，把它變成黑色就可以了。其他：都會違背紅黑樹的定義，於是我們就需要進行調整，調整的過程包含兩種基礎的操作：左右旋轉和改變顏色。其他情況主要有三種，如果要實現，可以對應各個情況各個擊破，紅黑樹的平衡調整過程是一個迭代的過程。就想魔方一樣！！！對應規則調整就行了．刪除刪除操作的平衡調整分為兩步，第一步是針對刪除節點初步調整。初步調整隻是保證整棵紅黑樹在一個節點刪除之後，仍然滿足最後一條定義的要求，也就是說，每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；第二步是針對關注節點進行二次調整，讓它滿足紅黑樹的第三條定義，即不存在相鄰的兩個紅色節點。

1. 針對刪除節點初步調整

紅黑樹的定義中「只包含紅色節點和黑色節點」，經過初步調整之後，為了保證滿足紅黑樹定義的最後一條要求，有些節點會被標記成兩種顏色，「紅 - 黑」或者「黑 - 黑」。如果一個節點被標記為了「黑 - 黑」，那在計算黑色節點個數的時候，要算成兩個黑色節點。這裡具體有：三種情況

2. 針對關注節點進行二次調整

經過初步調整之後，關注節點變成了「紅 - 黑」或者「黑 - 黑」節點。針對這個關注節點，我們再分四種情況來進行二次調整。二次調整是為了讓紅黑樹中不存在相鄰的紅色節點。這裡具體有：四種情況提問：如何理解紅黑樹定義的＂任何相鄰的節點都不能同時為紅色＂？如果一個結點是紅色的，則它的兩個孩子都是黑色的．也就是說只要用線連起來的都不能同時是紅色如何理解紅黑樹定義的＂每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；＂？ nullptr ．為什麼插入的節點偏偏是紅色呢？將插入的結點著色為紅色，不會違背「性質 4」。而少違背一條性質，就意味著我們需要處理的情況越少。為什麼紅黑樹的定義中，要求葉子節點是黑色的空節點？或者說是到底那裡方便了？只要滿足這一條要求，那在任何時刻，紅黑樹的平衡操作都可以歸結為上面的那幾種情況。而且是簡潔的．

2. 給紅黑樹添加黑色的空的葉子節點，會不會比較浪費存儲空間呢?

一張圖給你，立馬明白：

為什麼平衡的二叉樹（滿二叉樹或完全二叉樹）的高度大約是 log2n？？時間複雜度其實都跟樹的高度成正比，也就是 O(height)。既然這樣，現在問題就轉變成另外一個了，也就是，如何求一棵包含 n 個節點的完全二叉樹的高度？樹的高度就等於最大層數減一，為了方便計算，我們轉換成層來表示。從圖中可以看出，包含 n 個節點的完全二叉樹中，第一層包含 1 個節點，第二層包含 2 個節點，第三層包含 4 個節點，依次類推，下面一層節點個數是上一層的 2 倍，第 K 層包含的節點個數就是 2^(K-1)。不過，對於完全二叉樹來說，最後一層的節點個數有點兒不遵守上面的規律了。它包含的節點個數在 1 個到 2^(L-1) 個之間（我們假設最大層數是 L）。如果我們把每一層的節點個數加起來就是總的節點個數 n。也就是說，如果節點的個數是 n，那麼 n 滿足這樣一個關係：

n >= 1 2 4 8 ... 2^(L-2) 1n <= 1 2 4 8 ... 2^(L-2) 2^(L-1)

藉助等比數列的求和公式，我們可以計算出，L 的範圍是 [log2(n 1), log2n 1]。完全二叉樹的層數小於等於 log2n 1，也就是說，完全二叉樹的高度小於等於 log2n。