了解紅黑樹的起源，理解紅黑樹的本質
前言
你好，我是彤哥。
前面兩節，我們一起學習了關于跳表的理論知識，并手寫了兩種完全不同的實現，我們放一張圖來簡單地回顧一下：
實現跳表的關鍵之處是在有序鏈表的基礎上加上各層索引，通過這些索引可以做到O(log n)的時間復雜度快速地插入、刪除、查找元素。
說起跳表，我們就不得不提另一種非常經典的數據結構——紅黑樹，紅黑樹相對于跳表來說，雖然時間復雜度都是O(log n)，但是紅黑樹的使用場景相對更廣泛一些，在早期的Linux內核中就一直存在紅黑樹的實現，也運用在了更高效的多路復用器Epoll中。
所以，紅黑樹是每一個程序員不得不會的知識點，甚至有些變態的面試官，還會讓你手寫紅黑樹的一部分實現，比如左旋、右旋、插入平衡的過程、刪除平衡的過程，這些內容非常復雜，靠死記硬背往往很難徹底掌握。
彤哥也是一直在尋找一種紅黑樹的記憶法，總算讓我找到了那么一種還算不錯的方式，從紅黑樹的起源出發，理解紅黑樹的本質，再從本質出發，徹底掌握不用死記硬背的方法，最后再把它手寫出來。
從本節開始，我也將把這種方法傳遞給你，因此，紅黑樹的部分，我會分成三個小節來講解：
- 從紅黑樹的起源，到紅黑樹的本質
- 從紅黑樹的本質，找到不用死記硬背的方法
- 不靠死記硬背，手寫紅黑樹
好了，下面我們就進入第一小節。
紅黑樹的起源
二叉樹
說起樹，我們不得不說最有名的樹，那就是二叉樹，什么是二叉樹呢?
二叉樹(binary tree)，是指樹中的每個節點最多只有兩個子節點的樹。
當然，二叉樹本身似乎沒什么用，我們平時說的二叉樹基本上都是指二叉查找樹，或者叫有序二叉樹、二叉搜索樹、二叉排序樹。
二叉查找樹
二叉查找樹(BST，binary search tree)，就是在二叉樹的基礎上增加有序性，這個有序性一般是指自然順序，有了有序性，我們就可以使用二叉樹來快速的查找、刪除、插入元素了。
比如，上面這顆二叉查找樹，查找元素的平均時間復雜度為O(log n)。
但是，二叉查找樹有個非常嚴重的問題，試想，還是這三個元素，如果按照A、B、C的順序插入元素會怎樣?
這是啥?單鏈表?沒錯，當按照元素的自然順序插入元素的時候，二叉查找樹就退化成單鏈表了，單鏈表的插入、刪除、查找元素的時間復雜度是多少?O(n)。
所以，在極限情況下，二叉查找樹的時間復雜度是非常差的。
既然，插入元素后有可能導致二叉查找樹的性能變差，那么，我們是否可以增加一些手段，讓插入元素后的二叉查找樹依然性能良好呢?
答案是肯定的，這種手段就叫做平衡，這種可以自平衡的樹就叫做平衡樹。
平衡樹
平衡樹(self-balancing or height-balanced binary search tree)，是指插入、刪除元素后可以自平衡的二叉查找樹，使得它的時間復雜度可以一直漸近于O(log n)。
比如，上面那顆樹，按A、B、C插入元素后，做一次旋轉操作，就可以再次變成查找時間復雜度為O(log n)的樹。
但是，平衡樹一直只是一個概念，直到1962年才由兩個蘇聯人發明了第一種平衡樹——AVL樹。
嚴格來說，平衡樹是指可以自平衡的二叉查找樹，三個關鍵詞：自平衡、二叉、查找(有序)。
AVL樹
AVL樹(由發明者Adelson-Velsky 和 Landis 的首字母縮寫命名)，是指任意節點的兩個子樹的高度差不超過1的平衡樹。
比如，上面這顆樹，就是一顆AVL樹，不信你可以數數看，是不是每個節點的兩個子樹的高度差都不超過1。
是不是很難發現它真的是一顆AVL樹，沒錯，這是AVL樹的第一個缺點，不夠直觀，特別是節點個數多的時候。
第二個缺點，就是插入、刪除元素的時候自平衡的過程非常復雜，比如，上面這顆樹插入一個節點T：
我們從T往上找，它的父節點U，U的兩顆子樹的高度差為1，滿足AVL樹的規則，再往上，S的兩顆子樹的高度差為1，也滿足規則，再往上，V的兩顆子樹的高度差為2，不滿足規則，此時，需要一個自平衡的過程，該如何自平衡呢?
我下面給出圖示，你可以試著理解一下：
紅色節點表示旋轉的軸。
經過兩次旋轉，讓這顆樹再次變成了AVL樹，而且這只是其中一種插入場景，真實的情況還要根據插入的位置的不同做不同的旋轉，你可以多插入幾個節點自己嘗試平衡一下。
同樣地，AVL樹的代碼也不是那么好實現的，反正，到目前為止，彤哥是沒搞懂AVL樹的各種規則。
基于這些缺點，所以，后來又發展出來了各種各樣的神奇的平衡樹。
2-3樹
2-3樹，是指每個具有子節點的節點(內部節點，internal node)要么有兩個子節點和一個數據元素，要么有三個子節點和兩個數據元素的自平衡的樹，它的所有葉子節點都具有相同的高度。
簡單點講，2-3樹的非葉子節點都具有兩個分叉或者三個分叉，所以，稱作2叉-3叉樹更容易理解。
另外一種說法，具有兩個子節點和一個數據元素的節點又稱作2節點，具有三個子節點和兩個數據元素的節點又稱作3節點，所以，整顆樹叫做2-3樹。
2-3樹，插入元素后自平衡的過程相對于AVL樹就要簡單得多了，比如，上面這顆樹，再插入一個元素K，它會先找到I J這個節點，插入元素K，形成臨時節點I J K，不符合2-3樹的規則，所以分裂，J往上移，F H這個節點變成了F H J了，也不符合2-3樹的規則，繼續上移H，根節點變為D H，同時，上移的過程中，子節點也要相應的分裂，過程大致如下：
畫圖辛苦了，關注一波：彤哥讀源碼。
可以看到，上面自平衡的過程中，出現了一種節點，它具有四個子節點和三個數據元素，這個節點可以稱作4節點，如果把4節點當作是可以允許存在的，那么，就出現了另一種樹：2-3-4樹。
2-3-4樹
2-3-4樹，它的每個非葉子節點，要么是2節點，要么是3節點，要么是4節點，且可以自平衡，所以稱作2-3-4樹。
2節點、3節點、4節點的定義在上面已經提及，我們再重申一下：
2節點：包含兩個子節點和一個數據元素;
3節點：包含三個子節點和兩個數據元素;
4節點：包含四個子節點和三個數據元素;
當然，2-3-4樹插入元素的過程也很好理解，比如，上面這顆樹，插入元素M，找到K L這個節點，插入即可，形成4節點，滿足規則，不需要自平衡：
再插入元素N呢?過程與2-3樹一樣，向上分裂即可，此時，中間節點有兩個，取任意一個上移都是可以的，我們這里以左中節點上移為例，大致過程如下：
是不是挺簡單的，至少比AVL樹那種左旋右旋簡單得多。
同樣地，在2-3-4樹自平衡的過程中出現了臨時的5節點，所以，如果允許5節點的存在呢?
嗯，2-3-4-5樹由此誕生!
同樣地，還有2-3-4-5-6樹、2-3-4-5-6-7樹……子子孫孫，無窮盡也~
所以，有人就把這一類樹歸納為一個新的名字：B樹。
B樹
B樹，表示的是一類樹，它允許一個節點可以有多于兩個子節點，同時，也是自平衡的，葉子節點的高度都是相同的。
所以，為了更好地區分一顆B樹到底屬于哪一類樹，我們給它一個新的屬性：度(Degree)。
具有度為3的B樹，表示一個節點最多有三個子節點，也就是2-3樹的定義。
具有度為4的B樹，表示一個節點最多有四個子節點，也就是2-3-4樹的定義。
B樹，一個節點可以存儲多個元素，有利于緩存磁盤數據，整體的時間復雜度趨向于O(log n)，原理也比較簡單，所以，經常用于數據庫的索引，包括早期的mysql也是使用B樹來作為索引的。
但是，B樹有個大缺陷，比如，我要按范圍查找元素，以上面的2-3-4樹為例，查找大于B且小于K的所有元素，該怎么實現呢?
很難，幾乎無解，所以，后面又出現替代B樹的方案：B+樹。
當然了，B+樹不是本節的重點，本節的重點是紅黑樹。
納尼，紅黑樹在哪里?寫了3000多字了，還沒見到紅黑樹的影子，我尬了~
來了來了，有意思的紅黑樹來了~~
紅黑樹
先上一張圖，請仔細體會：
看明白了沒有?紅黑樹是啥?紅黑樹就是2-3-4樹!!!
OK，本節到此結束。
后記
本節，我們一起從二叉樹出發，一路經過二叉查找樹、平衡樹、AVL樹、2-3樹、2-3-4樹、B樹，最后終于得出了紅黑樹的本質，紅黑樹的本質就是一顆2-3-4樹，換了個皮膚而已。
那么，為什么要再造一個紅黑樹呢?直接用2-3-4樹它不香么?
本文轉載自微信公眾號「彤哥讀源碼」，可以通過以下二維碼關注。轉載本文請聯系彤哥讀源碼公眾號。
