我畫(huà)了 20 張圖,給女朋友講清楚紅黑樹(shù)
作者 |??程序員小吳
來(lái)源 |? 五分鐘學(xué)算法
紅黑樹(shù)是一種常見(jiàn)的自平衡二叉查找樹(shù)，常用于關(guān)聯(lián)數(shù)組、字典，在各種語(yǔ)言的底層實(shí)現(xiàn)中被廣泛應(yīng)用，Java 的 TreeMap 和 TreeSet 就是基于紅黑樹(shù)實(shí)現(xiàn)的。
本篇分享將為讀者講解紅黑樹(shù)的定義、創(chuàng)建和用途。
一.紅黑樹(shù)的定義
每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
根節(jié)點(diǎn)是黑色。
每個(gè)葉子節(jié)點(diǎn)是黑色。
如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的
從任意一個(gè)節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過(guò)的黑色節(jié)點(diǎn)是一樣的。
這段關(guān)于 紅黑樹(shù) 的描述來(lái)源于 《算法導(dǎo)論》，你看完這段話可能一臉懵逼。
本文希望能夠由淺入深地、漸進(jìn)式地引導(dǎo)讀者了解紅黑樹(shù)，因此我們會(huì)先從紅黑樹(shù)的意義說(shuō)起，為什么我們需要一棵紅黑樹(shù)。
二. 平衡二叉查找樹(shù)
我們以這樣一個(gè)數(shù)組為例 [42，37，18，12，11，6，5] 構(gòu)建一棵二叉搜索樹(shù)，由于數(shù)組中任意一點(diǎn)都可以作為二叉搜索樹(shù)的根節(jié)點(diǎn)，因此這棵二叉搜索樹(shù)并不唯一，我們來(lái)看一個(gè)極端的例子（以42作為根節(jié)點(diǎn)，順序插入元素）
在這個(gè)例子中，二叉搜索樹(shù)退化成了鏈表，搜索的時(shí)間復(fù)雜度為 O(n)，失去了作為一棵二叉搜索樹(shù)的意義。
為了讓二叉搜索樹(shù)不至于太“傾斜”，我們需要構(gòu)建一棵 平衡二叉搜索樹(shù)。
可以看出，平衡二叉搜索樹(shù)的搜索時(shí)間復(fù)雜度為O(logn)，避免了因?yàn)殡S機(jī)選取根節(jié)點(diǎn)構(gòu)建二叉搜索樹(shù)而可能造成的退化成鏈表的情況。下面再抄一段平衡二叉搜索樹(shù)的官方定義：
平衡二叉查找樹(shù)：簡(jiǎn)稱(chēng)平衡二叉樹(shù)。是由前蘇聯(lián)的數(shù)學(xué)家 Adelse-Velskil和 Landis 在 1962 年提出的高度平衡的二叉樹(shù)，根據(jù)科學(xué)家的英文名也稱(chēng)為 AVL 樹(shù)。它具有如下幾個(gè)性質(zhì)：
性質(zhì)1. 可以是空樹(shù)。?
性質(zhì)2 假如不是空樹(shù)，任何一個(gè)結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)都是平衡二叉樹(shù)，并且高度之差的絕對(duì)值不超過(guò) 1
（如果讀者還不清楚平衡二叉搜索樹(shù)的概念，可以點(diǎn)擊查閱前文 動(dòng)畫(huà)：什么是平衡二叉樹(shù)，本文不再詳細(xì)介紹平衡二叉搜索樹(shù)）
三. 2-3樹(shù)
經(jīng)過(guò)上面的例子，我們可以知道，構(gòu)建一棵平衡的二叉搜索樹(shù)的關(guān)鍵在于選取“正確”的根節(jié)點(diǎn)，那么我們?nèi)绾卧诿看螛?gòu)建平衡二叉搜索樹(shù)時(shí)都能選取合適的根節(jié)點(diǎn)呢，這里就要用到另一種重要的樹(shù)：2-3樹(shù)（讀作二三樹(shù)），2-3樹(shù)和紅黑樹(shù)是等價(jià)的，理解2-3樹(shù)對(duì)理解紅黑樹(shù)以及B類(lèi)樹(shù)都有很大的幫助。
2-3樹(shù)的基本概念
所謂2-3樹(shù)，即滿(mǎn)足二叉搜索樹(shù)的性質(zhì)，且節(jié)點(diǎn)可以存放一個(gè)元素或者兩個(gè)元素，每個(gè)節(jié)點(diǎn)有兩個(gè)或三個(gè)孩子的樹(shù)。
性質(zhì)1：滿(mǎn)足二叉搜索樹(shù)的性質(zhì)
性質(zhì)2：節(jié)點(diǎn)可以存放一個(gè)或兩個(gè)元素
性質(zhì)3：每個(gè)節(jié)點(diǎn)有兩個(gè)或三個(gè)子節(jié)點(diǎn)
2-3樹(shù)本質(zhì)上也是一棵搜索樹(shù)，和二叉搜索樹(shù)的區(qū)別在于，2-3的節(jié)點(diǎn)可能存放 2 個(gè)元素，而且每個(gè)節(jié)點(diǎn)可能擁有 3 個(gè)子節(jié)點(diǎn)。
2-3樹(shù)存在以下兩種節(jié)點(diǎn)：2-節(jié)點(diǎn)（存在兩個(gè)子節(jié)點(diǎn)）和3-節(jié)點(diǎn)（存在3個(gè)子節(jié)點(diǎn)）
2-3樹(shù)的創(chuàng)建
下面我們來(lái)看如何創(chuàng)建一棵2-3樹(shù)，創(chuàng)建2-3樹(shù)的規(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)組成的樹(shù)，并且分解后新樹(shù)的根節(jié)點(diǎn)需要向上和父節(jié)點(diǎn)融合
我們依然使用上面的示例數(shù)組[42，37，18，12，11，6，5]，依然使用順序插入的方式來(lái)構(gòu)建2-3樹(shù)，看看是否會(huì)出現(xiàn)退化成鏈表的情況。
我們可以注意到，在創(chuàng)建2-3樹(shù)的每一步中，整棵樹(shù)始終保持平衡。
既然2-3樹(shù)已經(jīng)能夠保持自平衡，為什么我們還需要一棵紅黑樹(shù)呢，這是因?yàn)?2-3樹(shù)這種每個(gè)節(jié)點(diǎn)儲(chǔ)存1~2個(gè)元素以及拆分節(jié)點(diǎn)向上融合的性質(zhì)不便于代碼操作，因此我們希望通過(guò)一些規(guī)則，將2-3樹(shù)轉(zhuǎn)換成二叉樹(shù)，且轉(zhuǎn)換后的二叉樹(shù)依然能保持平衡性。
2-3樹(shù)和紅黑樹(shù)的等價(jià)性
本小節(jié)我們以一棵2-3樹(shù)為例，將其從2-3樹(shù)轉(zhuǎn)換成為一棵紅黑樹(shù)，從而學(xué)習(xí)了解2-3樹(shù)和紅黑樹(shù)的轉(zhuǎn)換規(guī)則，并體會(huì)2-3樹(shù)和紅黑樹(shù)之間的等價(jià)性。
對(duì)于2-3樹(shù)中的2-節(jié)點(diǎn)來(lái)說(shuō)，本身就和二叉搜索樹(shù)的節(jié)點(diǎn)無(wú)異，可以直接轉(zhuǎn)換為紅黑樹(shù)的一個(gè)黑節(jié)點(diǎn)，但是對(duì)于3-節(jié)點(diǎn)來(lái)說(shuō)，我們需要進(jìn)行一點(diǎn)小轉(zhuǎn)換：
將3-節(jié)點(diǎn)拆開(kāi)，成為一棵樹(shù)，并且3-節(jié)點(diǎn)的左元素作為右元素的子樹(shù)
將原來(lái)的左元素標(biāo)記為紅色（表示紅色節(jié)點(diǎn)與其父節(jié)點(diǎn)在2-3樹(shù)中曾是平級(jí)的關(guān)系）
我們來(lái)轉(zhuǎn)換一棵復(fù)雜點(diǎn)的2-3樹(shù)，根據(jù)上邊的兩條轉(zhuǎn)換規(guī)則，我們將2-節(jié)點(diǎn)直接轉(zhuǎn)換為黑色節(jié)點(diǎn)，將3-節(jié)點(diǎn)拆成一棵子樹(shù)，并給左元素標(biāo)上紅色，這個(gè)過(guò)程應(yīng)該不難理解，另外我們可以注意到，由于紅色節(jié)點(diǎn)是由3-節(jié)點(diǎn)拆分而來(lái)，因此所有的紅色節(jié)點(diǎn)都只會(huì)出現(xiàn)在左子樹(shù)上。
四. 紅黑樹(shù)的性質(zhì)和復(fù)雜度分析
紅黑樹(shù)基本性質(zhì)分析
在完成了2-3樹(shù)到紅黑樹(shù)的轉(zhuǎn)換之后，我們重新審視紅黑樹(shù)的五條性質(zhì)：
(1) 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色
這是紅黑樹(shù)的定義，沒(méi)什么好說(shuō)的。
(2) 根節(jié)點(diǎn)是黑色
根節(jié)點(diǎn)要么對(duì)應(yīng)2-3樹(shù)的2-節(jié)點(diǎn)或者3-節(jié)點(diǎn)，而這兩者的根節(jié)點(diǎn)都是黑色的，因而根節(jié)點(diǎn)必然是黑色。從上圖2-3樹(shù)節(jié)點(diǎn)和紅黑樹(shù)節(jié)點(diǎn)對(duì)應(yīng)關(guān)系就能很容易看出來(lái)
(3) 每個(gè)葉子節(jié)點(diǎn)是黑色
注意，這里的葉子是指的為空的葉子節(jié)點(diǎn)，上圖的紅黑樹(shù)的完整形式應(yīng)該是這樣的：
(4) 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的
由于紅黑樹(shù)的每個(gè)節(jié)點(diǎn)都由2-3樹(shù)轉(zhuǎn)換而來(lái)，紅色節(jié)點(diǎn)連接的節(jié)點(diǎn)必然是一個(gè)2-節(jié)點(diǎn)或者3-節(jié)點(diǎn)，而無(wú)論是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)過(guò)的黑色節(jié)點(diǎn)是一樣多的
這是紅黑樹(shù)最重要的一條性質(zhì)，也是紅黑樹(shù)的價(jià)值所在。由于紅黑樹(shù)是由2-3樹(shù)轉(zhuǎn)換而來(lái)，因此每一個(gè)黑色節(jié)點(diǎn)必然對(duì)應(yīng)2-3樹(shù)的某個(gè)2-節(jié)點(diǎn)或者3-節(jié)點(diǎn)，因此紅黑樹(shù)的黑節(jié)點(diǎn)也能擁有2-3樹(shù)的平衡性。
如果對(duì)這條性質(zhì)還不夠理解，可以對(duì)著上文2-3樹(shù)和紅黑樹(shù)的轉(zhuǎn)換圖再理解理解。
紅黑樹(shù)時(shí)間復(fù)雜度分析
網(wǎng)上有很多使用數(shù)學(xué)歸納法來(lái)計(jì)算紅黑樹(shù)時(shí)間復(fù)雜度的證明了，這里就不再贅述。
我們可以簡(jiǎn)單思考一下，對(duì)于一棵普通的平衡二叉搜索樹(shù)來(lái)說(shuō)，它的搜索時(shí)間復(fù)雜度為O(logn)，而作為紅黑樹(shù)，存在著最壞的情況，也就是查找的過(guò)程中，經(jīng)過(guò)的節(jié)點(diǎn)全都是原來(lái)2-3樹(shù)里的3-節(jié)點(diǎn)，導(dǎo)致路徑延長(zhǎng)兩倍，時(shí)間復(fù)雜度為O(2logn)，由于時(shí)間復(fù)雜度的計(jì)算可以忽略系數(shù)，因此紅黑樹(shù)的搜索時(shí)間復(fù)雜度依然是O(logn)，當(dāng)然，由于這個(gè)系數(shù)的存在，在實(shí)際使用中，紅黑樹(shù)會(huì)比普通的平衡二叉樹(shù)（AVL樹(shù)）搜索效率要低一些。
既然紅黑樹(shù)的效率比AVL樹(shù)的效率低，那么紅黑樹(shù)的優(yōu)勢(shì)體現(xiàn)在哪呢？
事實(shí)上，紅黑樹(shù)的優(yōu)勢(shì)體現(xiàn)在它的插入和刪除操作上，紅黑樹(shù)的插入和刪除相較于AVL樹(shù)的性能會(huì)高一些，在后續(xù)紅黑樹(shù)的創(chuàng)建章節(jié)中，讀者應(yīng)該能夠體會(huì)到紅黑樹(shù)在調(diào)整樹(shù)平衡操作上的優(yōu)勢(shì)。
五. 紅黑樹(shù)的創(chuàng)建
上文中我們講解了如何由2-3樹(shù)轉(zhuǎn)換一棵紅黑樹(shù)，下面我們就來(lái)看看如何不經(jīng)過(guò)2-3樹(shù)直接創(chuàng)建一棵紅黑樹(shù)，畢竟我們寫(xiě)代碼的時(shí)候不能先創(chuàng)建一棵2-3樹(shù)再轉(zhuǎn)化成紅黑樹(shù)吧。
我們回想一下2-3樹(shù)的創(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)組成的樹(shù)，并且分解后新樹(shù)的根節(jié)點(diǎn)需要向上和父節(jié)點(diǎn)融合
簡(jiǎn)單來(lái)說(shuō)，2-3樹(shù)的創(chuàng)建分為「融合」和「拆分」兩步，為了實(shí)現(xiàn)這兩步，我們需要在創(chuàng)建二叉樹(shù)的基礎(chǔ)操作上增加另外幾個(gè)操作，分別是：
保持根節(jié)點(diǎn)黑色
左旋轉(zhuǎn)
右旋轉(zhuǎn)
顏色翻轉(zhuǎn)
保持根節(jié)點(diǎn)黑色和左旋轉(zhuǎn)
由于我們往2-3樹(shù)插入節(jié)點(diǎn)時(shí)做的都是融合，因此新加入的節(jié)點(diǎn)和原位置的節(jié)點(diǎn)是平級(jí)關(guān)系，所以我們往紅黑樹(shù)里增加節(jié)點(diǎn)的時(shí)候，增加的都是紅色節(jié)點(diǎn)。
我們插入第一個(gè)紅色節(jié)點(diǎn)42，哦吼，第一步就與紅黑樹(shù)的性質(zhì)2「根節(jié)點(diǎn)是黑色」沖突，為了解決這種沖突，我們將根節(jié)點(diǎn)變成黑色。
下面我們繼續(xù)插入節(jié)點(diǎn)37，同樣的，新插入的節(jié)點(diǎn)都為紅色
這里我們要思考一下，如果我們顛倒順序，先插入 37 再插入 42 呢，是直接把 42 加到 37 的右子樹(shù)上么，這顯然是錯(cuò)誤的，因?yàn)樵谇斑?-3樹(shù)轉(zhuǎn)紅黑樹(shù)的過(guò)程中，我們已經(jīng)了解到，所有的紅色節(jié)點(diǎn)都只會(huì)出現(xiàn)在左子樹(shù)上，因此我們需要進(jìn)行左旋轉(zhuǎn)，將節(jié)點(diǎn)的位置和顏色旋轉(zhuǎn)過(guò)來(lái)。
上面是兩個(gè)獨(dú)立的節(jié)點(diǎn)，如果節(jié)點(diǎn)擁有左右子樹(shù)，在旋轉(zhuǎn)后仍然能滿(mǎn)足二叉搜索樹(shù)的性質(zhì)嗎，我們需要推廣到一般情形。
我們來(lái)看一個(gè)例子：
經(jīng)過(guò)以上幾步，我們就完成了一般情形下的左旋轉(zhuǎn)，我們可以對(duì)應(yīng)地寫(xiě)幾句偽代碼，這里把 37 稱(chēng)作node，42 稱(chēng)作 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)
}
近期熱門(mén)推薦?
1.除了 P站，程序員在摸魚(yú)時(shí)還喜歡上了這些網(wǎng)站~~
2.會(huì)員還多花50元才能看網(wǎng)劇大結(jié)局，人民日?qǐng)?bào)怒批：吃相太難看
5.2018年所有精華文章匯總，錯(cuò)過(guò)了血虧！
關(guān)注公眾號(hào)，回復(fù)“BAT”
送進(jìn)軍BAT超全優(yōu)質(zhì)視頻資源
點(diǎn)贊是最大的支持?