[[342450]]

前言

你好，我是彤哥。

前面兩節(jié)，我們一起學(xué)習(xí)了關(guān)于跳表的理論知識(shí)，并手寫(xiě)了兩種完全不同的實(shí)現(xiàn)，我們放一張圖來(lái)簡(jiǎn)單地回顧一下：

實(shí)現(xiàn)跳表的關(guān)鍵之處是在有序鏈表的基礎(chǔ)上加上各層索引，通過(guò)這些索引可以做到O(log n)的時(shí)間復(fù)雜度快速地插入、刪除、查找元素。

說(shuō)起跳表，我們就不得不提另一種非常經(jīng)典的數(shù)據(jù)結(jié)構(gòu)——紅黑樹(shù)，紅黑樹(shù)相對(duì)于跳表來(lái)說(shuō)，雖然時(shí)間復(fù)雜度都是O(log n)，但是紅黑樹(shù)的使用場(chǎng)景相對(duì)更廣泛一些，在早期的Linux內(nèi)核中就一直存在紅黑樹(shù)的實(shí)現(xiàn)，也運(yùn)用在了更高效的多路復(fù)用器Epoll中。

所以，紅黑樹(shù)是每一個(gè)程序員不得不會(huì)的知識(shí)點(diǎn)，甚至有些變態(tài)的面試官，還會(huì)讓你手寫(xiě)紅黑樹(shù)的一部分實(shí)現(xiàn)，比如左旋、右旋、插入平衡的過(guò)程、刪除平衡的過(guò)程，這些內(nèi)容非常復(fù)雜，靠死記硬背往往很難徹底掌握。

彤哥也是一直在尋找一種紅黑樹(shù)的記憶法，總算讓我找到了那么一種還算不錯(cuò)的方式，從紅黑樹(shù)的起源出發(fā)，理解紅黑樹(shù)的本質(zhì)，再?gòu)谋举|(zhì)出發(fā)，徹底掌握不用死記硬背的方法，最后再把它手寫(xiě)出來(lái)。

從本節(jié)開(kāi)始，我也將把這種方法傳遞給你，因此，紅黑樹(shù)的部分，我會(huì)分成三個(gè)小節(jié)來(lái)講解：

• 從紅黑樹(shù)的起源，到紅黑樹(shù)的本質(zhì)
• 從紅黑樹(shù)的本質(zhì)，找到不用死記硬背的方法
• 不靠死記硬背，手寫(xiě)紅黑樹(shù)

好了，下面我們就進(jìn)入第一小節(jié)。

紅黑樹(shù)的起源

二叉樹(shù)

說(shuō)起樹(shù)，我們不得不說(shuō)最有名的樹(shù)，那就是二叉樹(shù)，什么是二叉樹(shù)呢?

二叉樹(shù)(binary tree)，是指樹(shù)中的每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)的樹(shù)。

當(dāng)然，二叉樹(shù)本身似乎沒(méi)什么用，我們平時(shí)說(shuō)的二叉樹(shù)基本上都是指二叉查找樹(shù)，或者叫有序二叉樹(shù)、二叉搜索樹(shù)、二叉排序樹(shù)。

二叉查找樹(shù)

二叉查找樹(shù)(BST，binary search tree)，就是在二叉樹(shù)的基礎(chǔ)上增加有序性，這個(gè)有序性一般是指自然順序，有了有序性，我們就可以使用二叉樹(shù)來(lái)快速的查找、刪除、插入元素了。

比如，上面這顆二叉查找樹(shù)，查找元素的平均時(shí)間復(fù)雜度為O(log n)。

但是，二叉查找樹(shù)有個(gè)非常嚴(yán)重的問(wèn)題，試想，還是這三個(gè)元素，如果按照A、B、C的順序插入元素會(huì)怎樣?

這是啥?單鏈表?沒(méi)錯(cuò)，當(dāng)按照元素的自然順序插入元素的時(shí)候，二叉查找樹(shù)就退化成單鏈表了，單鏈表的插入、刪除、查找元素的時(shí)間復(fù)雜度是多少?O(n)。

所以，在極限情況下，二叉查找樹(shù)的時(shí)間復(fù)雜度是非常差的。

既然，插入元素后有可能導(dǎo)致二叉查找樹(shù)的性能變差，那么，我們是否可以增加一些手段，讓插入元素后的二叉查找樹(shù)依然性能良好呢?

答案是肯定的，這種手段就叫做平衡，這種可以自平衡的樹(shù)就叫做平衡樹(shù)。

平衡樹(shù)

平衡樹(shù)(self-balancing or height-balanced binary search tree)，是指插入、刪除元素后可以自平衡的二叉查找樹(shù)，使得它的時(shí)間復(fù)雜度可以一直漸近于O(log n)。

比如，上面那顆樹(shù)，按A、B、C插入元素后，做一次旋轉(zhuǎn)操作，就可以再次變成查找時(shí)間復(fù)雜度為O(log n)的樹(shù)。

但是，平衡樹(shù)一直只是一個(gè)概念，直到1962年才由兩個(gè)蘇聯(lián)人發(fā)明了第一種平衡樹(shù)——AVL樹(shù)。

嚴(yán)格來(lái)說(shuō)，平衡樹(shù)是指可以自平衡的二叉查找樹(shù)，三個(gè)關(guān)鍵詞：自平衡、二叉、查找(有序)。

AVL樹(shù)

AVL樹(shù)(由發(fā)明者Adelson-Velsky 和 Landis 的首字母縮寫(xiě)命名)，是指任意節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度差不超過(guò)1的平衡樹(shù)。

比如，上面這顆樹(shù)，就是一顆AVL樹(shù)，不信你可以數(shù)數(shù)看，是不是每個(gè)節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度差都不超過(guò)1。

是不是很難發(fā)現(xiàn)它真的是一顆AVL樹(shù)，沒(méi)錯(cuò)，這是AVL樹(shù)的第一個(gè)缺點(diǎn)，不夠直觀，特別是節(jié)點(diǎn)個(gè)數(shù)多的時(shí)候。

第二個(gè)缺點(diǎn)，就是插入、刪除元素的時(shí)候自平衡的過(guò)程非常復(fù)雜，比如，上面這顆樹(shù)插入一個(gè)節(jié)點(diǎn)T：

我們從T往上找，它的父節(jié)點(diǎn)U，U的兩顆子樹(shù)的高度差為1，滿(mǎn)足AVL樹(shù)的規(guī)則，再往上，S的兩顆子樹(shù)的高度差為1，也滿(mǎn)足規(guī)則，再往上，V的兩顆子樹(shù)的高度差為2，不滿(mǎn)足規(guī)則，此時(shí)，需要一個(gè)自平衡的過(guò)程，該如何自平衡呢?

我下面給出圖示，你可以試著理解一下：

紅色節(jié)點(diǎn)表示旋轉(zhuǎn)的軸。

經(jīng)過(guò)兩次旋轉(zhuǎn)，讓這顆樹(shù)再次變成了AVL樹(shù)，而且這只是其中一種插入場(chǎng)景，真實(shí)的情況還要根據(jù)插入的位置的不同做不同的旋轉(zhuǎn)，你可以多插入幾個(gè)節(jié)點(diǎn)自己嘗試平衡一下。

同樣地，AVL樹(shù)的代碼也不是那么好實(shí)現(xiàn)的，反正，到目前為止，彤哥是沒(méi)搞懂AVL樹(shù)的各種規(guī)則。

基于這些缺點(diǎn)，所以，后來(lái)又發(fā)展出來(lái)了各種各樣的神奇的平衡樹(shù)。

2-3樹(shù)

2-3樹(shù)，是指每個(gè)具有子節(jié)點(diǎn)的節(jié)點(diǎn)(內(nèi)部節(jié)點(diǎn)，internal node)要么有兩個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素，要么有三個(gè)子節(jié)點(diǎn)和兩個(gè)數(shù)據(jù)元素的自平衡的樹(shù)，它的所有葉子節(jié)點(diǎn)都具有相同的高度。

簡(jiǎn)單點(diǎn)講，2-3樹(shù)的非葉子節(jié)點(diǎn)都具有兩個(gè)分叉或者三個(gè)分叉，所以，稱(chēng)作2叉-3叉樹(shù)更容易理解。

另外一種說(shuō)法，具有兩個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素的節(jié)點(diǎn)又稱(chēng)作2節(jié)點(diǎn)，具有三個(gè)子節(jié)點(diǎn)和兩個(gè)數(shù)據(jù)元素的節(jié)點(diǎn)又稱(chēng)作3節(jié)點(diǎn)，所以，整顆樹(shù)叫做2-3樹(shù)。

2-3樹(shù)，插入元素后自平衡的過(guò)程相對(duì)于AVL樹(shù)就要簡(jiǎn)單得多了，比如，上面這顆樹(shù)，再插入一個(gè)元素K，它會(huì)先找到I J這個(gè)節(jié)點(diǎn)，插入元素K，形成臨時(shí)節(jié)點(diǎn)I J K，不符合2-3樹(shù)的規(guī)則，所以分裂，J往上移，F(xiàn) H這個(gè)節(jié)點(diǎn)變成了F H J了，也不符合2-3樹(shù)的規(guī)則，繼續(xù)上移H，根節(jié)點(diǎn)變?yōu)镈 H，同時(shí)，上移的過(guò)程中，子節(jié)點(diǎn)也要相應(yīng)的分裂，過(guò)程大致如下：

畫(huà)圖辛苦了，關(guān)注一波：彤哥讀源碼。

可以看到，上面自平衡的過(guò)程中，出現(xiàn)了一種節(jié)點(diǎn)，它具有四個(gè)子節(jié)點(diǎn)和三個(gè)數(shù)據(jù)元素，這個(gè)節(jié)點(diǎn)可以稱(chēng)作4節(jié)點(diǎn)，如果把4節(jié)點(diǎn)當(dāng)作是可以允許存在的，那么，就出現(xiàn)了另一種樹(shù)：2-3-4樹(shù)。

2-3-4樹(shù)

2-3-4樹(shù)，它的每個(gè)非葉子節(jié)點(diǎn)，要么是2節(jié)點(diǎn)，要么是3節(jié)點(diǎn)，要么是4節(jié)點(diǎn)，且可以自平衡，所以稱(chēng)作2-3-4樹(shù)。

2節(jié)點(diǎn)、3節(jié)點(diǎn)、4節(jié)點(diǎn)的定義在上面已經(jīng)提及，我們?cè)僦厣暌幌拢?/p>

2節(jié)點(diǎn)：包含兩個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素;

3節(jié)點(diǎn)：包含三個(gè)子節(jié)點(diǎn)和兩個(gè)數(shù)據(jù)元素;

4節(jié)點(diǎn)：包含四個(gè)子節(jié)點(diǎn)和三個(gè)數(shù)據(jù)元素;

當(dāng)然，2-3-4樹(shù)插入元素的過(guò)程也很好理解，比如，上面這顆樹(shù)，插入元素M，找到K L這個(gè)節(jié)點(diǎn)，插入即可，形成4節(jié)點(diǎn)，滿(mǎn)足規(guī)則，不需要自平衡：

再插入元素N呢?過(guò)程與2-3樹(shù)一樣，向上分裂即可，此時(shí)，中間節(jié)點(diǎn)有兩個(gè)，取任意一個(gè)上移都是可以的，我們這里以左中節(jié)點(diǎn)上移為例，大致過(guò)程如下：

是不是挺簡(jiǎn)單的，至少比AVL樹(shù)那種左旋右旋簡(jiǎn)單得多。

同樣地，在2-3-4樹(shù)自平衡的過(guò)程中出現(xiàn)了臨時(shí)的5節(jié)點(diǎn)，所以，如果允許5節(jié)點(diǎn)的存在呢?

嗯，2-3-4-5樹(shù)由此誕生!

同樣地，還有2-3-4-5-6樹(shù)、2-3-4-5-6-7樹(shù)……子子孫孫，無(wú)窮盡也~

所以，有人就把這一類(lèi)樹(shù)歸納為一個(gè)新的名字：B樹(shù)。

B樹(shù)

B樹(shù)，表示的是一類(lèi)樹(shù)，它允許一個(gè)節(jié)點(diǎn)可以有多于兩個(gè)子節(jié)點(diǎn)，同時(shí)，也是自平衡的，葉子節(jié)點(diǎn)的高度都是相同的。

所以，為了更好地區(qū)分一顆B樹(shù)到底屬于哪一類(lèi)樹(shù)，我們給它一個(gè)新的屬性：度(Degree)。

具有度為3的B樹(shù)，表示一個(gè)節(jié)點(diǎn)最多有三個(gè)子節(jié)點(diǎn)，也就是2-3樹(shù)的定義。

具有度為4的B樹(shù)，表示一個(gè)節(jié)點(diǎn)最多有四個(gè)子節(jié)點(diǎn)，也就是2-3-4樹(shù)的定義。

B樹(shù)，一個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)元素，有利于緩存磁盤(pán)數(shù)據(jù)，整體的時(shí)間復(fù)雜度趨向于O(log n)，原理也比較簡(jiǎn)單，所以，經(jīng)常用于數(shù)據(jù)庫(kù)的索引，包括早期的mysql也是使用B樹(shù)來(lái)作為索引的。

但是，B樹(shù)有個(gè)大缺陷，比如，我要按范圍查找元素，以上面的2-3-4樹(shù)為例，查找大于B且小于K的所有元素，該怎么實(shí)現(xiàn)呢?

很難，幾乎無(wú)解，所以，后面又出現(xiàn)替代B樹(shù)的方案：B+樹(shù)。

當(dāng)然了，B+樹(shù)不是本節(jié)的重點(diǎn)，本節(jié)的重點(diǎn)是紅黑樹(shù)。

納尼，紅黑樹(shù)在哪里?寫(xiě)了3000多字了，還沒(méi)見(jiàn)到紅黑樹(shù)的影子，我尬了~

來(lái)了來(lái)了，有意思的紅黑樹(shù)來(lái)了~~

紅黑樹(shù)

先上一張圖，請(qǐng)仔細(xì)體會(huì)：

看明白了沒(méi)有?紅黑樹(shù)是啥?紅黑樹(shù)就是2-3-4樹(shù)!!!

OK，本節(jié)到此結(jié)束。

后記

本節(jié)，我們一起從二叉樹(shù)出發(fā)，一路經(jīng)過(guò)二叉查找樹(shù)、平衡樹(shù)、AVL樹(shù)、2-3樹(shù)、2-3-4樹(shù)、B樹(shù)，最后終于得出了紅黑樹(shù)的本質(zhì)，紅黑樹(shù)的本質(zhì)就是一顆2-3-4樹(shù)，換了個(gè)皮膚而已。

那么，為什么要再造一個(gè)紅黑樹(shù)呢?直接用2-3-4樹(shù)它不香么?

本文轉(zhuǎn)載自微信公眾號(hào)「彤哥讀源碼」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系彤哥讀源碼公眾號(hào)。