【數據結構】考研408|數據結構高分堡壘：攻克紅黑樹五大性質與適度平衡思想詳情 - 考研,數據結構,408,C,C++,後端開發,yyds乾貨盤點蒙奇D索隆博客

(紅黑樹的定義與性質)

紅黑樹

導讀

大家好，很高興又和大家見面啦！！！在前面的內容中我們已經學習了兩種樹形查找結構：

BST：二叉排序樹，其可以是一棵空樹，也可以是滿足以下條件的樹：
- 若左子樹非空，則左子樹上所有節點的值均小於根節點
- 若右子樹非空，則右子樹上所有節點的值均大於根節點
- 其左右子樹也分別是一棵二叉排序樹
AVL：平衡二叉樹，其是一棵能夠進行自平衡旋轉的 BST

為了避免 BST 的樹高增長的過快而導致其查找效率降低，因此引入了能夠將左右子樹的高度差控制在 $-1 \sim 1$ 之間的 AVL； AVL 通過判斷樹的 平衡因子，以此來決定是否需要進行平衡旋轉：

當 平衡因子 不在 $-1 \sim 1$ 這個範圍內時，則説明該樹已經失衡，需要通過自平衡旋轉使其恢復平衡

正因如此，當我們進行頻繁的插入或刪除操作時，就很容易破壞 AVL 的平衡特性，而導致其需要進行頻繁的平衡旋轉操作；為了優化這種情況，於是我們又再一次引入了一種新的自平衡排序樹—— 紅黑樹。那什麼是 紅黑樹 呢？相比於 AVL 其又有哪些優勢呢？從今天的內容開始，我們將會逐步揭開 紅黑樹 的神秘面紗；下面就讓我們一起進入今天的內容；

一、基本概念

1.1 紅黑樹的定義

紅黑樹（Red-Black Tree, RBT）是一種滿足如下 紅黑性質 的 BST：

每個結點或是紅色，或是黑色
根結點是黑色
葉結點 （虛構的外部節點、NULL 結點）都是黑色
不存在兩個相鄰的 紅結點 （紅結點的父結點與孩子結點均為黑色）
對每個結點，從該結點出發，到任意葉結點的簡單路徑上，所含的黑結點的數量相同

因此我們可以將其總結為十二個字：

左根右：RBT 是一種 BST，滿足 $左子樹 \leq 根節點 \leq 右子樹$
根葉黑：根結點、葉結點一定是黑色
黑路同：從任一結點出發，到達任一空葉結點的路徑上經過的黑結點數量都相同
不紅紅：任何一條查找路徑上不能連續出現兩個紅結點

1.2 重要概念

黑高：一個結點的黑高是指從該結點出發（不含該結點）到達任一空葉結點的路徑上黑結點總數 葉結點：在 RBT 中，“葉結點”通常指“失敗結點”（又名：空葉結點/NULL結點/外部結點）下面我們就來通過一棵紅黑樹來進一步説明這些概念：

flowchart TB
a[6<br>bh = 2]
b[2<br>bh = 1]
a--->b
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]

c[15<br>bh = 2]
a--->c

d[11<br>bh = 1]
e[18<br>bh = 1]
c--->d
c--->e

f[8<br>bh = 1]
g[14<br>bh = 1]
d--->f
f--->f1[NULL<br>bh = 0]
f--->f2[NULL<br>bh = 0]
d--->g
g--->g1[NULL<br>bh = 0]
g--->g2[NULL<br>bh = 0]

e--->e1[NULL<br>bh = 0]
h[20<br>bh = 1]
e--->h
h--->h1[NULL<br>bh = 0]
h--->h2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Black
class b1 Black
class b2 Black
class c Red
class d Black
class e Black
class f Red
class g Red
class e1 Black
class h Red
class f1 Black
class f2 Black
class g1 Black
class g2 Black
class h1 Black
class h2 Black

在上圖中的這棵 RBT 中，其 根結點 與 葉結點 一定是黑色，並且這些 葉結點 一定是 NULL 結點；對於任一結點，其黑高指的是從該節點開始，到任一 葉結點 的路徑上，不包含該結點的黑結點數量：

根結點 6 ，其到任一 葉結點 的路徑上都會包含2個黑結點，因此其黑高為 2：
- 6 ---> 2 ---> NULL ，包含除結點 6 外的兩個黑結點：2 和 NULL
- 6 ---> 15 ---> 11 ---> 8 ---> NULL ，包含除了結點 6 外的兩個黑結點：11 和 NULL
結點 2 ，其到任一 葉結點 的路徑上都會包含1個黑結點，因此其黑高為 1 ：
- 2 ---> NULL ，包含除結點 2 外的一個黑結點：NULL

對於結點 6 而言，其左子樹之所以為黑，是因為其右子樹 15 的黑高為 2 ，為了滿足 黑路同 ，因此結點 2 只能為黑；若我們將 2 變為紅色，則會導致從結點 6 出發，到左子樹中的任一葉結點，與到右子樹中的任一葉結點所包含的黑結點數不一致；

flowchart TB
a[6<br>bh_l = 1<br>bh_r = 2<br>bh_l != bh_r]
b[2<br>bh = 1]
a--->b
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]

c[15<br>bh = 2]
a--->c

d[11<br>bh = 1]
e[18<br>bh = 1]
c--->d
c--->e

f[8<br>bh = 1]
g[14<br>bh = 1]
d--->f
f--->f1[NULL<br>bh = 0]
f--->f2[NULL<br>bh = 0]
d--->g
g--->g1[NULL<br>bh = 0]
g--->g2[NULL<br>bh = 0]

e--->e1[NULL<br>bh = 0]
h[20<br>bh = 1]
e--->h
h--->h1[NULL<br>bh = 0]
h--->h2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px

class a Black
class b Red
class b1 Black
class b2 Black
class c Red
class d Black
class e Black
class f Red
class g Red
class e1 Black
class h Red
class f1 Black
class f2 Black
class g1 Black
class g2 Black
class h1 Black
class h2 Black

因此結點 2 只能為黑；

三、性質

RBT 總共有3條性質：

從根結點到葉結點的最長路徑不大於最短路徑的2倍
有n個內部結點的紅黑樹高度$h<=2log_2(n+1)$
新插入紅黑樹中的結點初始着為紅色

這裏我們先介紹前兩條性質；

3.1 性質1

當從根結點出發，到任一葉結點的簡單路徑最短時，這條路徑上的結點必然都是黑色，如最短簡單路徑：6 --> 2 ---> NULL 當某條路徑最長時，這條路徑必然是由黑結點與紅結點相間構成，如：6 ---> 15 ---> 11 ---> 14 ---> NULL 可以看到這兩條路徑的長度分別為：3 和 5 ，而 $5 < 3 * 2$ ；

若我們在最長路徑中插入一個結點使其長度變為最短路徑的兩倍，即最長路徑長度變為：6 ，那麼根據紅黑性質——不紅紅 與 根葉黑 ，對應的路徑上其結點的顏色一定是：黑 ---> 紅 ---> 黑 ---> 紅 ---> 黑 ---> 黑 ，其根結點的黑高為： bh = 3 ；
最短路徑保持不變，即最短路徑長度為：3 ，並且該路徑上的結點均為黑色，即：黑 ---> 黑 ---> 黑，其根結點的黑高為：bh = 2
顯然此時的最短路徑與最長路徑，其根結點不滿足紅黑性質——黑路同，因此我們可以得到結論：從根結點到葉結點的最長路徑 一定小於 最短路徑的2倍

兩種計算路徑長度的方法

這裏有朋友可能會好奇，為什麼這裏的性質説的是 不大於 而我們得到的結論是 一定小於？對於這個問題，我給出的解釋是：我這裏給出的實例所計算路徑長度的方法與性質1的表述是不一致的：

方法一：計算完整路徑長度，即從根結點到外部結點的總長度
方法二：計算內部路徑長度，即從根結點到內部葉結點的總長度

前面我所展示的路徑長度計算方法使用的是方法一，因此我們會得出 嚴格小於 這個結論；當我們採用方法二進行計算時，那麼其最短路徑長度與最長路徑長度分為為：

最短路徑：6 ---> 2 ，長度為 2
最長路徑：6 ---> 15 ---> 11 ---> 14 ，長度為 4

可以看到此時的最長路徑長度就與最短路徑長度的兩倍相等；因此 性質1 的表述是以方法二的方式計算路徑長度得出的結論，而 嚴格小於 也屬於 不大於 的範疇，所以，我們如果通過方法一的方式計算路徑長度，我們同樣也可以説 不大於；希望大家能夠準確辨別空葉結點 與 內部葉結點 這二者的區別，切記不能將二者混為一談！！！

插入法

性質1的驗證，我們還有一個更簡便的方法——插入法；這裏我們以下圖進行簡單的説明：

flowchart LR
a[黑]
b[黑]
c[黑]
a--->b--->c
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black
class c Black

在這條僅由黑色塊組成的路徑中，我們需要插入紅色塊，並且保證該路徑的起點與終點為黑色，且插入的紅色塊不能連續，那麼我們能夠插入的紅色塊最多隻有2塊：

flowchart LR
a[黑]
b[黑]
c[黑]
a--->d[紅]--->b--->e[紅]--->c
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black
class c Black
class e Red
class d Red

當我們去掉終點的黑色塊後，我們不難發現，這時的紅色塊與黑色塊的數量是相同的：

flowchart LR
a[黑]
b[黑]

a--->d[紅]--->b--->e[紅]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black

class e Red
class d Red

每個黑色塊後都緊跟一個紅色塊，這樣我們就能得到以下結論：

當計算終點黑色塊時，紅色塊的總數比黑色塊少 1
當不計算終點黑色塊時，紅色塊的總數與黑色塊相等

因此對於最短路徑長度為 $N$ 的 RBT ，其最長路徑長度為：

計算終點的空葉結點時，最長路徑長度為 $2 * N - 1$
不計算終點的空葉結點時，最長路徑長度為 $2 * N$

這也進一步驗證了性質1：

從根結點到葉結點的最長路徑不大於最短路徑的 $2$ 倍

3.2 性質2

由性質1可知，在紅黑樹中，其最長路徑所包含的紅結點是最多的，且不管是用方法一計算長度還是方法二計算長度，其紅結點的數量一定不會超過黑結點的數量，即對於長度為 2N 的最長路徑：

由方法一計算得出：其紅結點的數量一定是 N - 1 ，黑結點的數量一定是 N + 1
由方法二計算得出：其紅結點的數量一定是 N，黑結點的數量一定是 N

當我們只分析 內部結點 時，即採取 方法二 的方式計算一條路徑的長度，那麼對於 n 個內部結點的紅黑樹，其樹高為 h ，這也就表明該 RBT 的最長路徑長度為 h ；

對於一棵 RBT 而言，當其最長路徑中的紅結點數量最多時，其黑高最小；

在這棵 RBT 中，其僅計算內部結點的最長路徑長度為 h ，這樣我們就能得到紅結點最多時，其紅黑結點的數量均為 $\frac{h}{2}$ ；而我們要計算根結點的黑高時，我們需要去掉根節點，並加上路徑的終點——空葉結點，這也就是説，根結點的黑高至少為 $\frac{h}{2}$ ；由二叉樹的性質我們可知，對於結點數量為 $n$ ，樹高為 $h$ 的二叉樹，其結點數量 $n$ 與樹高 $h$ 之間的關係為：

滿二叉樹時，$n$ 最大，$n = 2^{h} - 1$
只存在一條路徑時，$n$ 最小，$n = h$

在 RBT 中，其內部結點數 $n$ 與其黑高 $bh$ 之間的關係為：$n \geq 2^{bh} - 1$ ，該結論我們可以通過 數學歸納法 進行證明；

內部結點數與黑高關係證明

由 分治思想 我們可以得到，RBT 的內部總結點數是由三部分組成：

根節點
左子樹的內部結點總數
右子樹的內部結點總數

因此我們要求 RBT 的內部結點總數 $n$ 就需要獲取其左右子樹中的結點總數；假設對於一棵 RBT ，其任一結點 $x$ 的黑高為 $bh_x$ ，以該結點為根的子樹的內部結點總數為 $n_x$ ；當該結點為 空葉結點 時，其黑高 $bh_{x} = 0$ ，其內部結點數為：$n_{x} = 2^{bh_{x}} - 1 = 2^0 - 1 = 1 - 1 = 0$，此時結論成立；在 RBT 中，其任一結點 $x$ 的左右子樹的黑高至少為：$bh_{x} - 1$ 這是因為當結點 $x$ 的子樹根結點為黑結點時，其子樹的黑高為：$bh_{x}- 1$ ；

flowchart TB
a[bh = 2] ---> b[bh = 1]
a--->c[bh = 1]
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]
c--->c1[NULL<br>bh = 0]
c--->c2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Black
class c Black
class b1 Black
class c1 Black
class b2 Black
class c2 Black

當結點 $x$ 的子樹根結點為紅結點時，其子樹的黑高為：$bh_{x}$；

flowchart TB
a[bh = 1] ---> b[bh = 1]
a--->c[bh = 1]
b--->b1[NULL<br>bh = 0]
b--->b2[NULL<br>bh = 0]
c--->c1[NULL<br>bh = 0]
c--->c2[NULL<br>bh = 0]
classDef Red color: white, fill: red, stroke: red, stroke-width:2px
classDef Black color:white, fill: black, stroke:black, stroke-width:2px
class a Black
class b Red
class c Red
class b1 Black
class c1 Black
class b2 Black
class c2 Black

因此我們可以假設：任一結點 $x$ 其左右子樹的內部結點數量為：

$$ n_{x_l} \geq 2^{bh_x - 1} - 1 \ n_{x_r} \geq 2^{bh_x - 1} - 1 $$

那麼對於以結點 $x$ 為根的子樹，其內部結點數量 $n_x$ 為：

$$ \begin{align*} n_x &= n_{x_l} + n_{x_r} + 1 \ n_x &\geq 2^{bh_x - 1} - 1 + 2^{bh_x - 1} - 1 + 1 \ n_x &\geq 2 * 2^{bh_x - 1} - 1 \ n_x &\geq 2^{bh_x} - 1 \end{align*} $$

性質2的證明

在前面我們已經證明了，一棵高度為 $h$ 的 RBT ，其黑高 $bh \geq \frac{h}{2}$ ；現在我們只需要將黑高 $bh$ 帶入到內部結點 $n$ 與黑高 $bh$ 的公式 $n \geq 2^{bh} - 1$ 中，就可以得到性質2：

$$ \begin{align*} n &\geq 2^{bh} - 1 \ n &\geq 2^{\frac{h}{2}} - 1 \ n + 1 &\geq 2^{\frac{h}{2}} \ \log_2 (n + 1) &\geq \frac{h}{2} \ 2 * \log_2 (n + 1) &\geq h \end{align*} $$

當一棵 RBT 的黑高為 $bh = h$ 時，其對應的樹高為與內部結點數分別為：

當最長路徑中不存在紅結點時，樹高最小為 $h$ ，對應的內部結點數最少，為 $2^h - 1$
當最長路徑中紅結點數量最多時，樹高最大為 $2h$ ，對應的內部結點數最大，為 $2^{2h} - 1$

可見，RBT 的 適度平衡 ，由 AVL 的 高度平衡 ，降低到了 任一結點左右子樹的高度，相差不超過 $2$ 倍。這種調整同時也降低了動態操作時的調整頻率。

RBT與AVL

對於一棵動態查找樹，若插入和刪除操作比較少，查找操作比較多，則採用 AVL 比較合適，否則採用 RBT 比較合適。由於維護 AVL 這種 高度平衡 所付出的代價比獲得的效益大的多，因此在實際應用中，RBT 的應用更為廣泛，如 C++ 中的 map/set 、JAVA 中的 TreeMap/TreeSet 就是用 RBT 實現的。

結語

通過本文的學習，我們系統性地探討了紅黑樹（Red-Black Tree, RBT）的核心定義與關鍵性質。紅黑樹作為一種自平衡的二叉查找樹，通過其獨特的五大性質確保了樹的近似平衡：

根葉黑：根結點與葉結點（空葉結點）均為黑
不紅紅：不存在連續的兩個紅結點
黑路同：從任一結點 $x$ 出發，到達任一葉結點的簡單路徑上的黑結點數量相同

與AVL樹對高度平衡的嚴格要求不同，紅黑樹以"適度平衡"換取了在頻繁插入刪除場景下更少的旋轉操作，這使得它的實際應用更為廣泛，如C++ STL中的map/set、Java的TreeMap/TreeSet 📌 核心知識點回顧

最長路徑不超過最短路徑的兩倍
- 這一特性源於"紅結點不相鄰"和"黑路同"的約束，保證了紅黑樹不會退化為近似鏈表的形態
樹高 $h \leq 2 \log_2(n+1)$
- 此性質決定了紅黑樹的搜索效率為 $O(log n)$，儘管平衡性略遜於AVL 樹，但維護成本更低
實際應用優勢在需要頻繁動態更新的場景中，紅黑樹的統計性能更優，是效率與實用性平衡的典範

🔜 下一篇內容預告 在接下來的篇章中，我們將深入探討紅黑樹最核心的操作——插入操作，重點分析：

"紅插"原則：新節點為什麼默認為紅色
平衡調整策略：變色與旋轉（左旋、右旋）的組合運用
雙紅衝突處理：叔叔節點顏色不同時的差異化處理方案

掌握這些情況及其處理流程，是真正理解和應用紅黑樹的關鍵。敬請期待！

互動與分享

點贊👍 - 您的認可是我持續創作的最大動力
收藏⭐ - 方便隨時回顧這些重要的基礎概念
轉發↗️ - 分享給更多可能需要的朋友
評論💬 - 歡迎留下您的寶貴意見或想討論的話題

感謝您的耐心閲讀！關注博主，不錯過更多技術乾貨。我們下一篇再見！

蒙奇D索隆博客

蒙奇D索隆博客

博客 / 詳情