我畫了 20 張圖,給女朋友講清楚紅黑樹

作者 |??程序員小吳

來源 |? 五分鐘學(xué)算法

紅黑樹是一種常見的自平衡二叉查找樹，常用于關(guān)聯(lián)數(shù)組、字典，在各種語(yǔ)言的底層實(shí)現(xiàn)中被廣泛應(yīng)用，Java 的 TreeMap 和 TreeSet 就是基于紅黑樹實(shí)現(xiàn)的。

本篇分享將為讀者講解紅黑樹的定義、創(chuàng)建和用途。

一.紅黑樹的定義

1. 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。

2. 根節(jié)點(diǎn)是黑色。

3. 每個(gè)葉子節(jié)點(diǎn)是黑色。

4. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的

5. 從任意一個(gè)節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過的黑色節(jié)點(diǎn)是一樣的。

這段關(guān)于 紅黑樹 的描述來源于 《算法導(dǎo)論》，你看完這段話可能一臉懵逼。

本文希望能夠由淺入深地、漸進(jìn)式地引導(dǎo)讀者了解紅黑樹，因此我們會(huì)先從紅黑樹的意義說起，為什么我們需要一棵紅黑樹。

二. 平衡二叉查找樹

我們以這樣一個(gè)數(shù)組為例 [42，37，18，12，11，6，5] 構(gòu)建一棵二叉搜索樹，由于數(shù)組中任意一點(diǎn)都可以作為二叉搜索樹的根節(jié)點(diǎn)，因此這棵二叉搜索樹并不唯一，我們來看一個(gè)極端的例子（以42作為根節(jié)點(diǎn)，順序插入元素）

在這個(gè)例子中，二叉搜索樹退化成了鏈表，搜索的時(shí)間復(fù)雜度為 O(n)，失去了作為一棵二叉搜索樹的意義。

為了讓二叉搜索樹不至于太“傾斜”，我們需要構(gòu)建一棵 平衡二叉搜索樹。

可以看出，平衡二叉搜索樹的搜索時(shí)間復(fù)雜度為O(logn)，避免了因?yàn)殡S機(jī)選取根節(jié)點(diǎn)構(gòu)建二叉搜索樹而可能造成的退化成鏈表的情況。下面再抄一段平衡二叉搜索樹的官方定義：

平衡二叉查找樹：簡(jiǎn)稱平衡二叉樹。是由前蘇聯(lián)的數(shù)學(xué)家 Adelse-Velskil和 Landis 在 1962 年提出的高度平衡的二叉樹，根據(jù)科學(xué)家的英文名也稱為 AVL 樹。它具有如下幾個(gè)性質(zhì)：

性質(zhì)1. 可以是空樹。?

性質(zhì)2 假如不是空樹，任何一個(gè)結(jié)點(diǎn)的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對(duì)值不超過 1

（如果讀者還不清楚平衡二叉搜索樹的概念，可以點(diǎn)擊查閱前文 動(dòng)畫：什么是平衡二叉樹，本文不再詳細(xì)介紹平衡二叉搜索樹）

三. 2-3樹

經(jīng)過上面的例子，我們可以知道，構(gòu)建一棵平衡的二叉搜索樹的關(guān)鍵在于選取“正確”的根節(jié)點(diǎn)，那么我們?nèi)绾卧诿看螛?gòu)建平衡二叉搜索樹時(shí)都能選取合適的根節(jié)點(diǎn)呢，這里就要用到另一種重要的樹：2-3樹（讀作二三樹），2-3樹和紅黑樹是等價(jià)的，理解2-3樹對(duì)理解紅黑樹以及B類樹都有很大的幫助。

2-3樹的基本概念

所謂2-3樹，即滿足二叉搜索樹的性質(zhì)，且節(jié)點(diǎn)可以存放一個(gè)元素或者兩個(gè)元素，每個(gè)節(jié)點(diǎn)有兩個(gè)或三個(gè)孩子的樹。

• 性質(zhì)1：滿足二叉搜索樹的性質(zhì)

• 性質(zhì)2：節(jié)點(diǎn)可以存放一個(gè)或兩個(gè)元素

• 性質(zhì)3：每個(gè)節(jié)點(diǎn)有兩個(gè)或三個(gè)子節(jié)點(diǎn)

2-3樹本質(zhì)上也是一棵搜索樹，和二叉搜索樹的區(qū)別在于，2-3的節(jié)點(diǎn)可能存放 2 個(gè)元素，而且每個(gè)節(jié)點(diǎn)可能擁有 3 個(gè)子節(jié)點(diǎn)。

2-3樹存在以下兩種節(jié)點(diǎn)：2-節(jié)點(diǎn)（存在兩個(gè)子節(jié)點(diǎn)）和3-節(jié)點(diǎn)（存在3個(gè)子節(jié)點(diǎn)）

2-3樹的創(chuàng)建

下面我們來看如何創(chuàng)建一棵2-3樹，創(chuàng)建2-3樹的規(guī)則如下：

規(guī)則1. 加入新節(jié)點(diǎn)時(shí)，不會(huì)往空的位置添加節(jié)點(diǎn)，而是添加到最后一個(gè)葉子節(jié)點(diǎn)上

規(guī)則2. 四節(jié)點(diǎn)可以被分解三個(gè)2-節(jié)點(diǎn)組成的樹，并且分解后新樹的根節(jié)點(diǎn)需要向上和父節(jié)點(diǎn)融合

我們依然使用上面的示例數(shù)組[42，37，18，12，11，6，5]，依然使用順序插入的方式來構(gòu)建2-3樹，看看是否會(huì)出現(xiàn)退化成鏈表的情況。

我們可以注意到，在創(chuàng)建2-3樹的每一步中，整棵樹始終保持平衡。

既然2-3樹已經(jīng)能夠保持自平衡，為什么我們還需要一棵紅黑樹呢，這是因?yàn)?2-3樹這種每個(gè)節(jié)點(diǎn)儲(chǔ)存1~2個(gè)元素以及拆分節(jié)點(diǎn)向上融合的性質(zhì)不便于代碼操作，因此我們希望通過一些規(guī)則，將2-3樹轉(zhuǎn)換成二叉樹，且轉(zhuǎn)換后的二叉樹依然能保持平衡性。

2-3樹和紅黑樹的等價(jià)性

本小節(jié)我們以一棵2-3樹為例，將其從2-3樹轉(zhuǎn)換成為一棵紅黑樹，從而學(xué)習(xí)了解2-3樹和紅黑樹的轉(zhuǎn)換規(guī)則，并體會(huì)2-3樹和紅黑樹之間的等價(jià)性。

對(duì)于2-3樹中的2-節(jié)點(diǎn)來說，本身就和二叉搜索樹的節(jié)點(diǎn)無異，可以直接轉(zhuǎn)換為紅黑樹的一個(gè)黑節(jié)點(diǎn)，但是對(duì)于3-節(jié)點(diǎn)來說，我們需要進(jìn)行一點(diǎn)小轉(zhuǎn)換：

1. 將3-節(jié)點(diǎn)拆開，成為一棵樹，并且3-節(jié)點(diǎn)的左元素作為右元素的子樹

1. 將原來的左元素標(biāo)記為紅色（表示紅色節(jié)點(diǎn)與其父節(jié)點(diǎn)在2-3樹中曾是平級(jí)的關(guān)系）

我們來轉(zhuǎn)換一棵復(fù)雜點(diǎn)的2-3樹，根據(jù)上邊的兩條轉(zhuǎn)換規(guī)則，我們將2-節(jié)點(diǎn)直接轉(zhuǎn)換為黑色節(jié)點(diǎn)，將3-節(jié)點(diǎn)拆成一棵子樹，并給左元素標(biāo)上紅色，這個(gè)過程應(yīng)該不難理解，另外我們可以注意到，由于紅色節(jié)點(diǎn)是由3-節(jié)點(diǎn)拆分而來，因此所有的紅色節(jié)點(diǎn)都只會(huì)出現(xiàn)在左子樹上。

四. 紅黑樹的性質(zhì)和復(fù)雜度分析

紅黑樹基本性質(zhì)分析

在完成了2-3樹到紅黑樹的轉(zhuǎn)換之后，我們重新審視紅黑樹的五條性質(zhì)：

(1) 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色

這是紅黑樹的定義，沒什么好說的。

(2) 根節(jié)點(diǎn)是黑色

根節(jié)點(diǎn)要么對(duì)應(yīng)2-3樹的2-節(jié)點(diǎn)或者3-節(jié)點(diǎn)，而這兩者的根節(jié)點(diǎn)都是黑色的，因而根節(jié)點(diǎn)必然是黑色。從上圖2-3樹節(jié)點(diǎn)和紅黑樹節(jié)點(diǎn)對(duì)應(yīng)關(guān)系就能很容易看出來

(3) 每個(gè)葉子節(jié)點(diǎn)是黑色

注意，這里的葉子是指的為空的葉子節(jié)點(diǎn)，上圖的紅黑樹的完整形式應(yīng)該是這樣的：

(4) 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的

由于紅黑樹的每個(gè)節(jié)點(diǎn)都由2-3樹轉(zhuǎn)換而來，紅色節(jié)點(diǎn)連接的節(jié)點(diǎn)必然是一個(gè)2-節(jié)點(diǎn)或者3-節(jié)點(diǎn)，而無論是2-節(jié)點(diǎn)還是3-節(jié)點(diǎn)，其根節(jié)點(diǎn)都是黑色的，因此紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必然是黑色的

(5) 從任意一個(gè)節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過的黑色節(jié)點(diǎn)是一樣多的

這是紅黑樹最重要的一條性質(zhì)，也是紅黑樹的價(jià)值所在。由于紅黑樹是由2-3樹轉(zhuǎn)換而來，因此每一個(gè)黑色節(jié)點(diǎn)必然對(duì)應(yīng)2-3樹的某個(gè)2-節(jié)點(diǎn)或者3-節(jié)點(diǎn)，因此紅黑樹的黑節(jié)點(diǎn)也能擁有2-3樹的平衡性。

如果對(duì)這條性質(zhì)還不夠理解，可以對(duì)著上文2-3樹和紅黑樹的轉(zhuǎn)換圖再理解理解。

紅黑樹時(shí)間復(fù)雜度分析

網(wǎng)上有很多使用數(shù)學(xué)歸納法來計(jì)算紅黑樹時(shí)間復(fù)雜度的證明了，這里就不再贅述。

我們可以簡(jiǎn)單思考一下，對(duì)于一棵普通的平衡二叉搜索樹來說，它的搜索時(shí)間復(fù)雜度為O(logn)，而作為紅黑樹，存在著最壞的情況，也就是查找的過程中，經(jīng)過的節(jié)點(diǎn)全都是原來2-3樹里的3-節(jié)點(diǎn)，導(dǎo)致路徑延長(zhǎng)兩倍，時(shí)間復(fù)雜度為O(2logn)，由于時(shí)間復(fù)雜度的計(jì)算可以忽略系數(shù)，因此紅黑樹的搜索時(shí)間復(fù)雜度依然是O(logn)，當(dāng)然，由于這個(gè)系數(shù)的存在，在實(shí)際使用中，紅黑樹會(huì)比普通的平衡二叉樹（AVL樹）搜索效率要低一些。

既然紅黑樹的效率比AVL樹的效率低，那么紅黑樹的優(yōu)勢(shì)體現(xiàn)在哪呢？

事實(shí)上，紅黑樹的優(yōu)勢(shì)體現(xiàn)在它的插入和刪除操作上，紅黑樹的插入和刪除相較于AVL樹的性能會(huì)高一些，在后續(xù)紅黑樹的創(chuàng)建章節(jié)中，讀者應(yīng)該能夠體會(huì)到紅黑樹在調(diào)整樹平衡操作上的優(yōu)勢(shì)。

五. 紅黑樹的創(chuàng)建

上文中我們講解了如何由2-3樹轉(zhuǎn)換一棵紅黑樹，下面我們就來看看如何不經(jīng)過2-3樹直接創(chuàng)建一棵紅黑樹，畢竟我們寫代碼的時(shí)候不能先創(chuàng)建一棵2-3樹再轉(zhuǎn)化成紅黑樹吧。

我們回想一下2-3樹的創(chuàng)建規(guī)則：

規(guī)則1. 加入新節(jié)點(diǎn)時(shí)，不會(huì)往空的位置添加節(jié)點(diǎn)，而是添加到最后一個(gè)葉子節(jié)點(diǎn)上?

規(guī)則2. 四節(jié)點(diǎn)可以被分解三個(gè)2-節(jié)點(diǎn)組成的樹，并且分解后新樹的根節(jié)點(diǎn)需要向上和父節(jié)點(diǎn)融合

簡(jiǎn)單來說，2-3樹的創(chuàng)建分為「融合」和「拆分」兩步，為了實(shí)現(xiàn)這兩步，我們需要在創(chuàng)建二叉樹的基礎(chǔ)操作上增加另外幾個(gè)操作，分別是：

1. 保持根節(jié)點(diǎn)黑色

1. 左旋轉(zhuǎn)

1. 右旋轉(zhuǎn)

1. 顏色翻轉(zhuǎn)

保持根節(jié)點(diǎn)黑色和左旋轉(zhuǎn)

由于我們往2-3樹插入節(jié)點(diǎn)時(shí)做的都是融合，因此新加入的節(jié)點(diǎn)和原位置的節(jié)點(diǎn)是平級(jí)關(guān)系，所以我們往紅黑樹里增加節(jié)點(diǎn)的時(shí)候，增加的都是紅色節(jié)點(diǎn)。

我們插入第一個(gè)紅色節(jié)點(diǎn)42，哦吼，第一步就與紅黑樹的性質(zhì)2「根節(jié)點(diǎn)是黑色」沖突，為了解決這種沖突，我們將根節(jié)點(diǎn)變成黑色。

下面我們繼續(xù)插入節(jié)點(diǎn)37，同樣的，新插入的節(jié)點(diǎn)都為紅色

這里我們要思考一下，如果我們顛倒順序，先插入 37 再插入 42 呢，是直接把 42 加到 37 的右子樹上么，這顯然是錯(cuò)誤的，因?yàn)樵谇斑?-3樹轉(zhuǎn)紅黑樹的過程中，我們已經(jīng)了解到，所有的紅色節(jié)點(diǎn)都只會(huì)出現(xiàn)在左子樹上，因此我們需要進(jìn)行左旋轉(zhuǎn)，將節(jié)點(diǎn)的位置和顏色旋轉(zhuǎn)過來。

上面是兩個(gè)獨(dú)立的節(jié)點(diǎn)，如果節(jié)點(diǎn)擁有左右子樹，在旋轉(zhuǎn)后仍然能滿足二叉搜索樹的性質(zhì)嗎，我們需要推廣到一般情形。

我們來看一個(gè)例子：

經(jīng)過以上幾步，我們就完成了一般情形下的左旋轉(zhuǎn)，我們可以對(duì)應(yīng)地寫幾句偽代碼，這里把 37 稱作node，42 稱作 target

function leftRotate(node) {
 ?  node.right = target.left
 ?  target.left = node
 ?  target.color = node.color
 ?  node.color = RED
}
function flipColors(node) {
 ?  node.color = RED
 ?  node.left.color = BLACK
 ?  node.right.color = BLACK
}
function rightRotate(node) { ?
 ?  node.left = T1 ?
 ?  target.right = node ?
 ?  target.color = node.color ?
 ?  node.color = RED
}
function add(node) { ?
 ?  //如果右節(jié)點(diǎn)為紅色,左節(jié)點(diǎn)為黑色, 那么進(jìn)行左旋轉(zhuǎn), 對(duì)應(yīng)情況2 ?
 ?  if(isRed(node.right) && !isRed(node.left)) node = leftRotate(node) ?

 ?  //如果左節(jié)點(diǎn)為紅色,左節(jié)點(diǎn)的左節(jié)點(diǎn)也為紅色, 那么進(jìn)行右旋轉(zhuǎn), 對(duì)應(yīng)情況3 ?
 ?  if(isRed(node.left) && isRed(node.left.left)) node = rightRotate(node) ? ?

 ?  //如果左右節(jié)點(diǎn)都為紅色, 那么進(jìn)行顏色翻轉(zhuǎn), 對(duì)應(yīng)情況4 ?
 ?  if(isRed(node.left) && isRed(node.right)) flipColors(node)

}

（完）

近期熱門推薦?

1.除了 P站，程序員在摸魚時(shí)還喜歡上了這些網(wǎng)站~~

2.會(huì)員還多花50元才能看網(wǎng)劇大結(jié)局，人民日?qǐng)?bào)怒批：吃相太難看

3.假如有人把支付寶存儲(chǔ)服務(wù)器炸了

4.程序員除了會(huì)CRUD之外，還要知道CQRS！

5.2018年所有精華文章匯總，錯(cuò)過了血虧！

關(guān)注公眾號(hào)，回復(fù)“BAT”
送進(jìn)軍BAT超全優(yōu)質(zhì)視頻資源

點(diǎn)贊是最大的支持?