原文連結
紅黑樹是一種常見的自平衡二叉查找樹，常用于關聯數組、字典，在各種語言的底層實作中被廣泛應用，Java 的 TreeMap 和 TreeSet 就是基于紅黑樹實作的。
本篇分享将為讀者講解紅黑樹的定義、建立和用途。
一.紅黑樹的定義
- 每個節點或者是黑色，或者是紅色。
- 根節點是黑色。
- 每個葉子節點是黑色。
- 如果一個節點是紅色的，則它的子節點必須是黑色的
- 從任意一個節點到葉子節點，經過的黑色節點是一樣的。
這段關于 紅黑樹 的描述來源于 《算法導論》，你看完這段話可能一臉懵逼。
本文希望能夠由淺入深地、漸進式地引導讀者了解紅黑樹，是以我們會先從紅黑樹的意義說起，為什麼我們需要一棵紅黑樹。
二. 平衡二叉查找樹
我們以這樣一個數組為例 [42，37，18，12，11，6，5] 建構一棵二叉搜尋樹，由于數組中任意一點都可以作為二叉搜尋樹的根節點，是以這棵二叉搜尋樹并不唯一，我們來看一個極端的例子（以42作為根節點，順序插入元素）
在這個例子中，二叉搜尋樹退化成了連結清單，搜尋的時間複雜度為 O(n)，失去了作為一棵二叉搜尋樹的意義。
為了讓二叉搜尋樹不至于太“傾斜”，我們需要建構一棵 平衡二叉搜尋樹。
可以看出，平衡二叉搜尋樹的搜尋時間複雜度為O(logn)，避免了因為随機選取根節點建構二叉搜尋樹而可能造成的退化成連結清單的情況。下面再抄一段平衡二叉搜尋樹的官方定義：
平衡二叉查找樹：簡稱平衡二叉樹。是由前蘇聯的數學家 Adelse-Velskil和 Landis 在 1962 年提出的高度平衡的二叉樹，根據科學家的英文名也稱為 AVL 樹。它具有如下幾個性質：
性質1. 可以是空樹。
性質2 假如不是空樹，任何一個結點的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對值不超過 1
三. 2-3樹
經過上面的例子，我們可以知道，建構一棵平衡的二叉搜尋樹的關鍵在于選取“正确”的根節點，那麼我們如何在每次建構平衡二叉搜尋樹時都能選取合适的根節點呢，這裡就要用到另一種重要的樹：2-3樹（讀作二三樹），2-3樹和紅黑樹是等價的，了解2-3樹對了解紅黑樹以及B類樹都有很大的幫助。
2-3樹的基本概念
所謂2-3樹，即滿足二叉搜尋樹的性質，且節點可以存放一個元素或者兩個元素，每個節點有兩個或三個孩子的樹。
- 性質1：滿足二叉搜尋樹的性質
- 性質2：節點可以存放一個或兩個元素
- 性質3：每個節點有兩個或三個子節點
2-3樹本質上也是一棵搜尋樹，和二叉搜尋樹的差別在于，2-3的節點可能存放 2 個元素，而且每個節點可能擁有 3 個子節點。
2-3樹存在以下兩種節點：2-節點（存在兩個子節點）和3-節點（存在3個子節點）
2-3樹的建立
下面我們來看如何建立一棵2-3樹，建立2-3樹的規則如下：
規則1. 加入新節點時，不會往空的位置添加節點，而是添加到最後一個葉子節點上
規則2. 四節點可以被分解三個2-節點組成的樹，并且分解後新樹的根節點需要向上和父節點融合
我們依然使用上面的示例數組[42，37，18，12，11，6，5]，依然使用順序插入的方式來建構2-3樹，看看是否會出現退化成連結清單的情況。
我們可以注意到，在建立2-3樹的每一步中，整棵樹始終保持平衡。
既然2-3樹已經能夠保持自平衡，為什麼我們還需要一棵紅黑樹呢，這是因為 2-3樹這種每個節點儲存1~2個元素以及拆分節點向上融合的性質不便于代碼操作，是以我們希望通過一些規則，将2-3樹轉換成二叉樹，且轉換後的二叉樹依然能保持平衡性。
2-3樹和紅黑樹的等價性
本小節我們以一棵2-3樹為例，将其從2-3樹轉換成為一棵紅黑樹，進而學習了解2-3樹和紅黑樹的轉換規則，并體會2-3樹和紅黑樹之間的等價性。
對于2-3樹中的2-節點來說，本身就和二叉搜尋樹的節點無異，可以直接轉換為紅黑樹的一個黑節點，但是對于3-節點來說，我們需要進行一點小轉換：
- 将3-節點拆開，成為一棵樹，并且3-節點的左元素作為右元素的子樹
- 将原來的左元素标記為紅色（表示紅色節點與其父節點在2-3樹中曾是平級的關系）
我們來轉換一棵複雜點的2-3樹，根據上邊的兩條轉換規則，我們将2-節點直接轉換為黑色節點，将3-節點拆成一棵子樹，并給左元素标上紅色，這個過程應該不難了解，另外我們可以注意到，由于紅色節點是由3-節點拆分而來，是以所有的紅色節點都隻會出現在左子樹上。
四. 紅黑樹的性質和複雜度分析
紅黑樹基本性質分析
在完成了2-3樹到紅黑樹的轉換之後，我們重新審視紅黑樹的五條性質：
(1) 每個節點或者是黑色，或者是紅色
這是紅黑樹的定義，沒什麼好說的。
(2) 根節點是黑色
根節點要麼對應2-3樹的2-節點或者3-節點，而這兩者的根節點都是黑色的，因而根節點必然是黑色。從上圖2-3樹節點和紅黑樹節點對應關系就能很容易看出來
(3) 每個葉子節點是黑色
注意，這裡的葉子是指的為空的葉子節點，上圖的紅黑樹的完整形式應該是這樣的：
(4) 如果一個節點是紅色的，則它的子節點必須是黑色的
由于紅黑樹的每個節點都由2-3樹轉換而來，紅色節點連接配接的節點必然是一個2-節點或者3-節點，而無論是2-節點還是3-節點，其根節點都是黑色的，是以紅色節點的子節點必然是黑色的
(5) 從任意一個節點到葉子節點，經過的黑色節點是一樣多的
這是紅黑樹最重要的一條性質，也是紅黑樹的價值所在。由于紅黑樹是由2-3樹轉換而來，是以每一個黑色節點必然對應2-3樹的某個2-節點或者3-節點，是以紅黑樹的黑節點也能擁有2-3樹的平衡性。
如果對這條性質還不夠了解，可以對着上文2-3樹和紅黑樹的轉換圖再了解了解。
紅黑樹時間複雜度分析
網上有很多使用數學歸納法來計算紅黑樹時間複雜度的證明了，這裡就不再贅述。
我們可以簡單思考一下，對于一棵普通的平衡二叉搜尋樹來說，它的搜尋時間複雜度為O(logn)，而作為紅黑樹，存在着最壞的情況，也就是查找的過程中，經過的節點全都是原來2-3樹裡的3-節點，導緻路徑延長兩倍，時間複雜度為O(2logn)，由于時間複雜度的計算可以忽略系數，是以紅黑樹的搜尋時間複雜度依然是O(logn)，當然，由于這個系數的存在，在實際使用中，紅黑樹會比普通的平衡二叉樹（AVL樹）搜尋效率要低一些。
既然紅黑樹的效率比AVL樹的效率低，那麼紅黑樹的優勢展現在哪呢？
事實上，紅黑樹的優勢展現在它的插入和删除操作上，紅黑樹的插入和删除相較于AVL樹的性能會高一些，在後續紅黑樹的建立章節中，讀者應該能夠體會到紅黑樹在調整樹平衡操作上的優勢。
五. 紅黑樹的建立
上文中我們講解了如何由2-3樹轉換一棵紅黑樹，下面我們就來看看如何不經過2-3樹直接建立一棵紅黑樹，畢竟我們寫代碼的時候不能先建立一棵2-3樹再轉化成紅黑樹吧。
我們回想一下2-3樹的建立規則：
簡單來說，2-3樹的建立分為「融合」和「拆分」兩步，為了實作這兩步，我們需要在建立二叉樹的基礎操作上增加另外幾個操作，分别是：
- 保持根節點黑色
- 左旋轉
- 右旋轉
- 顔色翻轉
保持根節點黑色和左旋轉
由于我們往2-3樹插入節點時做的都是融合，是以新加入的節點和原位置的節點是平級關系，是以我們往紅黑樹裡增加節點的時候，增加的都是紅色節點。
我們插入第一個紅色節點42，哦吼，第一步就與紅黑樹的性質2「根節點是黑色」沖突，為了解決這種沖突，我們将根節點變成黑色。
下面我們繼續插入節點37，同樣的，新插入的節點都為紅色
這裡我們要思考一下，如果我們颠倒順序，先插入 37 再插入 42 呢，是直接把 42 加到 37 的右子樹上麼，這顯然是錯誤的，因為在前邊2-3樹轉紅黑樹的過程中，我們已經了解到，所有的紅色節點都隻會出現在左子樹上，是以我們需要進行左旋轉，将節點的位置和顔色旋轉過來。
上面是兩個獨立的節點，如果節點擁有左右子樹，在旋轉後仍然能滿足二叉搜尋樹的性質嗎，我們需要推廣到一般情形。
我們來看一個例子：
經過以上幾步，我們就完成了一般情形下的左旋轉，我們可以對應地寫幾句僞代碼，這裡把 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) {
//如果右節點為紅色,左節點為黑色, 那麼進行左旋轉, 對應情況2
if(isRed(node.right) && !isRed(node.left)) node = leftRotate(node)
//如果左節點為紅色,左節點的左節點也為紅色, 那麼進行右旋轉, 對應情況3
if(isRed(node.left) && isRed(node.left.left)) node = rightRotate(node)
//如果左右節點都為紅色, 那麼進行顔色翻轉, 對應情況4
if(isRed(node.left) && isRed(node.right)) flipColors(node) } 來源 | 五分鐘學算法
作者 | 程式員小吳