資料結構與算法之美-9 二叉樹紅黑樹 [MD]

博文位址

我的GitHub	我的部落格	我的微信	我的郵箱
baiqiantao		bqt20094	[email protected]

- 25 | 紅黑樹（上）：為什麼工程中都用紅黑樹這種二叉樹？
  - 平衡二叉查找樹
  - 紅黑樹的定義
  - 為什麼說紅黑樹是“近似平衡”的？
  - 解答開篇
  - 三種動态資料結構
- 26 | 紅黑樹（下）：掌握這些技巧，你也可以實作一個紅黑樹
  - 實作紅黑樹的基本思想
  - 插入操作的平衡調整
  - 删除操作的平衡調整
    - 針對删除節點初步調整
    - 針對關注節點進行二次調整
  - 内容小結
- 27 | 遞歸樹：如何借助樹來求解遞歸算法的時間複雜度？
  - 遞歸樹
  - 歸并排序
  - 快速排序
  - 斐波那契數列
  - 全排列

平衡二叉樹 ：二叉樹中任意一個節點的左右子樹的 高度相差不能大于 1 。
平衡二叉查找樹 ：除了滿足上面平衡二叉樹的定義，還滿足二叉查找樹的特點。

最先被發明的平衡二叉查找樹是

AVL

樹，它嚴格符合

平衡二叉查找樹

的定義，即任何節點的左右子樹高度相差不超過 1，是一種高度平衡的二叉查找樹。但是很多平衡二叉查找樹其實并沒有

嚴格符合

上面的定義，比如下面要講的紅黑樹，它從根節點到各個葉子節點的最長路徑，有可能會比最短路徑大一倍。

發明平衡二叉查找樹這類資料結構的初衷是，解決普通二叉查找樹在

頻繁的插入、删除

等動态更新的情況下，出現

時間複雜度退化

的問題。

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

是以，隻要一個平衡二叉查找樹的高度不比

logn

大很多，盡管它不嚴格符合平衡二叉查找樹的定義，但仍然是一個合格的平衡二叉查找樹。

平衡二叉查找樹其實有很多，比如，Splay Tree（伸展樹）、Treap（樹堆）等，但是提到平衡二叉查找樹，聽到的基本都是紅黑樹。它的出鏡率甚至要高于“平衡二叉查找樹”這幾個字，有時候，我們甚至預設平衡二叉查找樹就是紅黑樹。

紅黑樹的英文是

Red-Black Tree

，簡稱

R-B Tree

，它是一種

不嚴格

的平衡二叉查找樹。

紅黑樹中的節點，一類被标記為黑色，一類被标記為紅色。除此之外，一棵紅黑樹還需要滿足這樣幾個要求：

根節點是黑色的
每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存儲資料
- 這一條主要是為了簡化紅黑樹的代碼實作而設定的
- 下面在畫圖和講解的時候，會将黑色的、空的葉子節點都省略掉
任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的
每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點

平衡二叉查找樹的初衷是為了解決二叉查找樹因為動态更新導緻的性能退化問題。是以，“平衡”的意思可以等價為性能不退化。“近似平衡”就等價為性能不會退化得太嚴重。

一棵極其平衡的二叉樹（滿二叉樹或完全二叉樹）的高度大約是

logn

，是以如果要證明紅黑樹是近似平衡的，隻需要分析紅黑樹的高度是否比較穩定地趨近

logn

就好了。

後面省略若幹内容......

前面提到的 Treap、Splay Tree，絕大部分情況下，它們操作的效率都很高，但是也

無法避免極端情況下時間複雜度的退化

。盡管這種情況出現的機率不大，但是對于單次操作時間非常敏感的場景來說，它們并不适用。

AVL 樹是一種

高度平衡

的二叉樹，是以查找的效率非常高，但是，有利就有弊，AVL 樹為了維持這種高度的平衡，就要付出更多的代價。每次插入、删除都要做調整，就比較複雜、耗時。是以，對于有頻繁的插入、删除操作的資料集合，使用 AVL 樹的代價就有點高了。

紅黑樹隻是做到了

近似平衡

，并不是嚴格的平衡，是以在維護平衡的成本上，要比 AVL 樹要低。是以，紅黑樹的插入、删除、查找各種操作性能都比較

穩定

，時間複雜度都是

O(logn)

。對于工程應用來說，要面對各種異常情況，為了支撐這種工業級的應用，更傾向于這種

性能穩定

支援動态的資料插入、删除、查找操作的動态資料結構：

散清單：插入删除查找都是 O(1) ，是最常用的，但其缺點是不能順序周遊以及擴容縮容的性能損耗。适用于那些不需要順序周遊，資料更新不那麼頻繁的。
跳表：插入删除查找都是 O(logn) ，并且能順序周遊。缺點是空間複雜度 O(n) 。适用于不那麼在意記憶體空間的，其順序周遊和區間查找非常友善。
紅黑樹：插入删除查找都是 O(logn) ，中序周遊即是順序周遊，穩定。缺點是難以實作，去查找不友善。其實跳表更佳，但紅黑樹已經用于很多地方了。

實際上，魔方的複原解法是有固定算法的：遇到哪幾面是什麼樣子，對應就怎麼轉幾下。你隻要跟着這個複原步驟，就肯定能将魔方複原。

紅黑樹的平衡過程跟魔方複原非常神似，大緻過程就是：遇到什麼樣的節點排布，我們就對應怎麼去調整。隻要按照這些固定的調整規則來操作，就能将一個非平衡的紅黑樹調整成平衡的。

左旋（rotate left）：圍繞某個節點的左旋
右旋（rotate right）：圍繞某個節點的右旋

下圖中的 a，b，r 表示子樹，可以為空

紅黑樹規定，插入的節點必須是紅色的。而且，二叉查找樹中新插入的節點都是放在葉子節點上。是以，關于插入操作的平衡調整，有這樣兩種非常好處理特殊情況：

如果插入節點的父節點是 黑色 的，那我們什麼都不用做，它仍然滿足紅黑樹的定義
如果插入的節點是 根節點 ，那我們直接改變它的顔色，把它變成黑色就可以了

除此之外，其他情況都會違背紅黑樹的定義，于是我們就需要進行調整，調整的過程包含兩種基礎的操作：

左右旋轉

和

改變顔色

紅黑樹的平衡調整過程是一個

疊代

的過程。我們把正在處理的節點叫做

關注節點

。關注節點會随着不停地疊代處理，而不斷發生變化。最開始的關注節點就是新插入的節點。

新節點插入之後，如果紅黑樹的平衡被打破，那一般會有下面三種情況。我們隻需要根據每種情況的特點，不停地調整，就可以讓紅黑樹繼續符合定義，也就是繼續保持平衡。

為了簡化描述，我把父節點的兄弟節點叫做

叔叔節點

，父節點的父節點叫做

祖父節點

CASE 1：如果關注節點是 a，它的叔叔節點 d 是紅色

我們就依次執行下面的操作：

将關注節點 a 的父節點 b、叔叔節點 d 的顔色都設定成黑色
将關注節點 a 的祖父節點 c 的顔色設定成紅色
關注節點變成 a 的祖父節點 c
跳到 CASE 2 或者 CASE 3

CASE 2：如果關注節點是 a，它的叔叔節點 d 是黑色，關注節點 a 是其父節點 b 的右子節點

關注節點變成節點 a 的父節點 b
圍繞新的關注節點 b 左旋
跳到 CASE 3

CASE 3：如果關注節點是 a，它的叔叔節點 d 是黑色，關注節點 a 是其父節點 b 的左子節點

圍繞關注節點 a 的祖父節點 c 右旋
将關注節點 a 的父節點 b、兄弟節點 c 的顔色互換
調整結束

紅黑樹插入操作的平衡調整還不是很難，但是它的删除操作的平衡調整相對就要難多了。不過原理都是類似的，我們依舊隻需要根據關注節點與周圍節點的排布特點，按照一定的規則去調整就行了。

删除操作的平衡調整分為兩步，第一步是

針對删除節點初步調整

。初步調整隻是保證整棵紅黑樹在一個節點删除之後，仍然滿足最後一條定義的要求，也就是說，每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；第二步是

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

，讓它滿足紅黑樹的第三條定義，即不存在相鄰的兩個紅色節點。

這裡需要注意一下，紅黑樹的定義中“隻包含紅色節點和黑色節點”，經過初步調整之後，為了保證滿足紅黑樹定義的最後一條要求，有些節點會被标記成兩種顔色，“紅 - 黑”或者“黑 - 黑”。如果一個節點被标記為了“黑 - 黑”，那在計算黑色節點個數的時候，要算成兩個黑色節點。

在下面的講解中，如果一個節點既可以是紅色，也可以是黑色，在畫圖的時候，我會用一半紅色一半黑色來表示。如果一個節點是“紅 - 黑”或者“黑 - 黑”，我會用左上角的一個小黑點來表示額外的黑色。

CASE 1：如果要删除的節點是 a，它隻有一個子節點 b

那我們就依次進行下面的操作：

删除節點 a，并且把節點 b 替換到節點 a 的位置，這一部分操作跟普通的二叉查找樹的删除操作一樣
節點 a 隻能是黑色，節點 b 也隻能是紅色，其他情況均不符合紅黑樹的定義。這種情況下，我們把節點 b 改為黑色
調整結束，不需要進行二次調整

CASE 2：如果要删除的節點 a 有兩個非空子節點，并且它的後繼節點就是節點 a 的右子節點 c

我們就依次進行下面的操作：

如果節點 a 的後繼節點就是右子節點 c，那右子節點 c 肯定沒有左子樹。我們把節點 a 删除，并且将節點 c 替換到節點 a 的位置。這一部分操作跟普通的二叉查找樹的删除操作無異
然後把節點 c 的顔色設定為跟節點 a 相同的顔色
如果節點 c 是黑色，為了不違反紅黑樹的最後一條定義，我們給節點 c 的右子節點 d 多加一個黑色，這個時候節點 d 就成了“紅 - 黑”或者“黑 - 黑”
這個時候，關注節點變成了節點 d，第二步的調整操作就會針對關注節點來做

CASE 3：如果要删除的是節點 a，它有兩個非空子節點，并且節點 a 的後繼節點不是右子節點

找到後繼節點 d，并将它删除，删除後繼節點 d 的過程參照 CASE 1
将節點 a 替換成後繼節點 d
把節點 d 的顔色設定為跟節點 a 相同的顔色
如果節點 d 是黑色，為了不違反紅黑樹的最後一條定義，我們給節點 d 的右子節點 c 多加一個黑色，這個時候節點 c 就成了“紅 - 黑”或者“黑 - 黑”
這個時候，關注節點變成了節點 c，第二步的調整操作就會針對關注節點來做

經過初步調整之後，關注節點變成了“紅 - 黑”或者“黑 - 黑”節點。針對這個關注節點，我們再分四種情況來進行二次調整。二次調整是為了讓紅黑樹中不存在相鄰的紅色節點。

CASE 1：如果關注節點是 a，它的兄弟節點 c 是紅色的

圍繞關注節點 a 的父節點 b 左旋
關注節點 a 的父節點 b 和祖父節點 c 交換顔色
關注節點不變
繼續從四種情況中選擇适合的規則來調整

CASE 2：如果關注節點是 a，它的兄弟節點 c 是黑色的，并且節點 c 的左右子節點 d、e 都是黑色的

将關注節點 a 的兄弟節點 c 的顔色變成紅色
從關注節點 a 中去掉一個黑色，這個時候節點 a 就是單純的紅色或者黑色
給關注節點 a 的父節點 b 添加一個黑色，這個時候節點 b 就變成了“紅 - 黑”或者“黑 - 黑”
關注節點從 a 變成其父節點 b
繼續從四種情況中選擇符合的規則來調整

CASE 3：如果關注節點是 a，它的兄弟節點 c 是黑色，c 的左子節點 d 是紅色，c 的右子節點 e 是黑色

圍繞關注節點 a 的兄弟節點 c 右旋
節點 c 和節點 d 交換顔色
跳轉到 CASE 4，繼續調整

CASE 4：如果關注節點 a 的兄弟節點 c 是黑色的，并且 c 的右子節點是紅色的

将關注節點 a 的兄弟節點 c 的顔色，跟關注節點 a 的父節點 b 設定成相同的顔色
将關注節點 a 的父節點 b 的顔色設定為黑色
從關注節點 a 中去掉一個黑色，節點 a 就變成了單純的紅色或者黑色
将關注節點 a 的叔叔節點 e 設定為黑色

為什麼紅黑樹的定義中，要求葉子節點是黑色的空節點？

之是以有這麼奇怪的要求，其實就是為了實作起來友善。隻要滿足這一條要求，那在任何時刻，紅黑樹的平衡操作都可以歸結為我們剛剛講的那幾種情況。

假設紅黑樹的定義中不包含剛剛提到的那一條“葉子節點必須是黑色的空節點”，我們往一棵紅黑樹中插入一個資料，新插入節點的父節點也是紅色的，兩個紅色的節點相鄰，這個時候，紅黑樹的定義就被破壞了。那我們應該如何調整呢？

你會發現，這個時候，我們前面在講插入時，三種情況下的平衡調整規則，沒有一種是适用的。但是，如果我們把黑色的空節點都給它加上，變成下面這樣，你會發現，它滿足 CASE 2 了。

你可能會說，你可以調整一下平衡調整規則啊。比如把 CASE 2 改為“如果關注節點 a 的叔叔節點 b 是黑色或者不存在，a 是父節點的右子節點，就進行某某操作”。當然可以，但是這樣的話規則就沒有原來簡潔了。

你可能還會說，這樣給紅黑樹添加黑色的空的葉子節點，會不會比較浪費存儲空間呢？答案是不會的。雖然我們在講解或者畫圖的時候，每個黑色的、空的葉子節點都是獨立畫出來的。實際上，在具體實作的時候，我們隻需要像下面這樣，共用一個黑色的、空的葉子節點就行了。

很多人都認為紅黑樹很難學，其實主要原因是，他們都試圖去記住它的

平衡調整政策

。實際上，你隻需要

了解

這個調整過程就可以了，沒有必要去記。

現在，我就來總結一下，如何比較輕松地看懂我今天講的操作過程。

第一點，把紅黑樹的平衡調整的過程比作 魔方複原 ，不要過于深究這個算法的正确性。你隻需要明白，隻要 按照固定的操作步驟 ，保持插入、删除的過程，不破壞平衡樹的定義就行了。
第二點，找準 關注節點 ，不要搞丢、搞錯關注節點。因為每種操作規則，都是基于關注節點來做的，隻有弄對了關注節點，才能對應到正确的操作規則中。在疊代的調整過程中，關注節點在不停地改變，是以，這個過程一定要注意，不要弄丢了關注節點。
第三點，插入操作的平衡調整比較簡單，但是删除操作就比較複雜。針對删除操作，我們有兩次調整，第一次是針對要删除的節點做初步調整，讓調整後的紅黑樹繼續滿足第四條定義。但是這個時候，第三條定義就不滿足了，有可能會存在兩個紅色節點相鄰的情況。第二次調整就是解決這個問題，讓紅黑樹不存在相鄰的紅色節點。

遞歸代碼的

時間複雜度

分析起來很麻煩，前面我們講過如何利用

遞推公式

求解歸并排序、快速排序的時間複雜度。但是，有些情況用遞推公式的話，會涉及非常複雜的數學推導。今天，我們就來學習另外一種方法，借助

遞歸樹

來分析遞歸算法的時間複雜度。

遞歸的思想就是将大問題分解為小問題來求解，然後再将小問題分解為小小問題。這樣一層一層地分解，直到問題的資料規模被分解得足夠小，不用繼續遞歸分解為止。

如果我們把這個一層一層的

分解過程

畫成圖，它其實就是一棵樹。我們給這棵樹起一個名字，叫作

遞歸樹

下圖是

斐波那契數列

的遞歸樹，節點裡的數字表示資料的規模，一個節點的求解可以分解為左右子節點兩個問題的求解。

利用遞歸樹的時間複雜度分析方法并不難了解，關鍵還是在實戰。

歸并排序每次會将資料規模一分為二，現在我們就借助歸并排序來看看如何用遞歸樹，分析遞歸代碼的時間複雜度。

我們把歸并排序畫成遞歸樹，就是下面這個樣子：

歸并算法中比較耗時的是

歸并操作

，也就是把兩個

子數組

合并為

大數組

。從圖中我們可以看出，

每一層歸并操作消耗的時間總和是一樣的

，跟要排序的資料規模有關，我們把每一層歸并操作消耗的時間記作 n。

現在，我們隻需要知道這棵樹的高度 h，用高度 h 乘以每一層的時間消耗 n，就可以得到總的時間複雜度

O(n∗h)

從歸并排序的原理和遞歸樹可以看出來，歸并排序遞歸樹是一棵

滿二叉樹

，滿二叉樹的高度大約是

logn

，是以，歸并排序遞歸實作的時間複雜度就是

O(nlogn)

為什麼用遞推公式來求解平均時間複雜度非常複雜？

快速排序在最好情況下，每次分區都能一分為二，這個時候用遞推公式

T(n) = 2*T(n/2) + n

，很容易就能推導出時間複雜度是

O(nlogn)

。但是，我們并不可能每次分區都正好一分為二。

假設平均情況下，每次分區之後，兩個分區的大小比例為

1:k

。當 k=9 時，用遞推公式的方法來求解時間複雜度的話，遞推公式就寫成

T(n)=T(n/10) + T(9n/10) + n

這個公式可以推導出時間複雜度，但是推導過程非常複雜。

如果我們把遞歸分解的過程畫成遞歸樹，就是下面這個樣子：

快速排序的過程中，每次分區都要周遊待分區區間的所有資料，是以，

每一層

分區操作所周遊的資料的個數之和就是 n。我們現在隻要求出遞歸樹的高度 h，這個快排過程周遊的資料個數就是

h∗n

，也就是說，時間複雜度就是

O(h∗n)

因為每次分區并不是均勻地一分為二，是以遞歸樹并不是滿二叉樹。這樣一個遞歸樹的高度是多少呢？

我們知道，快速排序結束的條件就是待排序的小區間大小為 1，也就是說葉子節點裡的資料規模是 1。從根節點 n 到葉子節點 1，遞歸樹中最短的一個路徑每次都乘以

1/10

，最長的一個路徑每次都乘以

9/10

。通過計算，我們可以得到：

是以，周遊資料的個數總和就介于最短路徑和最長路徑之間，是以，當分區大小比例是

1:9

時，快速排序的時間複雜度仍然是

O(nlogn)

剛剛我們假設 k=9，那如果 k=99，也就是說，每次分區極其不平均，兩個區間大小是

1:99

，這個時候的時間複雜度是多少呢？

我們可以類比上面 k=9 的分析過程。當 k=99 的時候，盡管底數變了，但是時間複雜度也仍然是

O(nlogn)

也就是說，對于 k 等于 9，99，甚至是 999，9999……，隻要

k 的值不随 n 變化

，是一個事先确定的常量，那快排的時間複雜度就是

O(nlogn)

斐波那契數列的代碼實作

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

把上面的遞歸代碼畫成遞歸樹，就是下面這個樣子：

這棵遞歸樹的高度是多少呢？

f(n) 分解為

f(n−1)

f(n−2)

，每次資料規模都是 −1 或者 −2，是以，從根節點走到葉子節點，每條路徑是長短不一的。如果每次都是 −1，那最長路徑大約就是

；如果每次都是 −2，那最短路徑大約就是

n/2

每次分解之後的合并操作隻需要一次加法運算，我們把這次加法運算的時間消耗記作 1。是以，從上往下，第一層的總時間消耗是 1，第二層的總時間消耗是 2，第三層的總時間消耗就是

2^2

。依次類推，第 k 層的時間消耗就是

2^(k−1)

，那整個算法的總的時間消耗就是每一層時間消耗之和。

如果路徑長度都為 n，那這個總和就是

2^n − 1

是以，這個算法的時間複雜度就介于

O(2^n)

O(2^n/2)

之間。

如何把 n 個資料的所有排列都找出來，這就是全排列的問題。

比如，1，2，3 這樣 3 個資料，有下面這幾種不同的排列：

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

如何程式設計列印一組資料的所有排列呢？這裡就可以用遞歸來實作。

如果我們确定了最後一位資料，那就變成了求解剩下

n−1

個資料的排列問題。而最後一位資料可以是 n 個資料中的任意一個，是以它的取值就有 n 種情況。是以，n 個資料的全排列問題，就可以分解成 n 個

n−1

個資料的全排列的子問題。

遞推公式：

假設數組中存儲的是1，2， 3...n
f(1,2,...n) = {最後一位是1, f(n-1)} + {最後一位是2, f(n-1)} + ... + {最後一位是n, f(n-1)}

// 調用方式：
// int[]a = a={1, 2, 3, 4}; printPermutations(a, 4, 4);
// k表示要處理的子數組的資料個數
public void printPermutations(int[] data, int n, int k) {
  if (k == 1) {
    for (int i = 0; i < n; ++i) {
      System.out.print(data[i] + " ");
    }
    System.out.println();
  }

  for (int i = 0; i < k; ++i) {
    int tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;

    printPermutations(data, n, k - 1);

    tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;
  }
}

如果不用遞歸樹分析方法，這個遞歸代碼的時間複雜度會比較難分析。

首先，我們還是畫出遞歸樹。不過，現在的遞歸樹已經不是标準的二叉樹了。

第一層分解有 n 次交換操作，第二層有 n 個節點，每個節點分解需要

n−1

次交換，是以第二層總的交換次數是

n∗(n−1)

。第三層有

n∗(n−1)

個節點，每個節點分解需要

n−2

次交換，是以第三層總的交換次數是

n∗(n−1)∗(n−2)

以此類推，第 k 層總的交換次數就是

n∗(n−1)∗(n−2)∗...∗(n−k+1)

。最後一層的交換次數就是

n∗(n−1)∗(n−2)∗...∗2∗1

。每一層的交換次數之和就是總的交換次數。

n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1

有些代碼的時間複雜度比較适合用 遞推公式 來分析，比如歸并排序、快速排序的最好情況時間複雜度
有些比較适合采用 遞歸樹 來分析，比如快速排序的平均時間複雜度
有些可能兩個都不怎麼适合使用，比如二叉樹的遞歸前中後序周遊

資料結構與算法之美-9 二叉樹紅黑樹 [MD]

繼續閱讀

設計模式-組合模式（Composite Pattern）

推薦一款個人感覺比較好用的 JSON 格式化 chrome 插件-JSON-handle

HDU 5379 Mahjong tree

百度面試題-“盜夢空間”

bzoj 1010--玩具裝箱toy

資料結構之遞歸實作

程式員的算法趣題Q09: 落單的男女1. 問題描述2. 解題分析3. 代碼及測試4. 思考

時間複雜度及空間複雜度直白了解/快排/冒泡時間複雜度及空間複雜度直白了解/快排/冒泡

時間複雜度和空間複雜度時間複雜度空間複雜度推導過程

歸并排序的時間複雜度

HDU 1207 漢諾塔II

遞歸經典整數劃分問題

Redis：清單LPUSH、LPUSHX、RPUSH、RPUSHX、LPOP、RPOP指令介紹

PAT (Top Level) Practise 1007 Red-black Tree (35)

UVA 110 Meta-Loopless Sorts

UVA 620 Cellular Structure

資料結構與算法之美-9 二叉樹 紅黑樹 [MD]

繼續閱讀

資料結構與算法之美-9 二叉樹紅黑樹 [MD]