寫在前面

紅黑樹是比較難的資料結構之一，在JDK1.8中，紅黑樹已經廣泛應用到HashMap、TreeMap等基礎集合類之中，筆者之前也研究過一段時間的紅黑樹，現將自己的學習和研究所得整理出來，供廣大同仁參考，
本文分為3部分：
第一部分為“紅黑樹筑基：二叉查找樹、AVL樹、B樹和2-3-4樹”，對于沒有資料結構基礎的人直接學習紅黑樹比較困難，需要先閱讀此部分，如果讀者先前學過AVL樹、B樹等資料結構，請跳過此部分，直接從第二部分為“紅黑樹起步：性質與原理”讀起，
第二部分為“紅黑樹起步：性質與原理”，主要講述紅黑樹的歷史演變程序和紅黑樹的五大性質，以及為什么紅黑樹會有五大性質，讀者閱讀之后可以做到不需要死記硬背也能一輩子也忘不了紅黑樹的性質，
第三部分為：“紅黑樹成長：操作與自平衡”，講述紅黑樹的插入和洗掉等操作以及插入或洗掉后實作自平衡的方式，又為什么能使用這些方式實作自平衡，讀者閱讀之后既可以自己玩轉紅黑樹了，

紅黑樹筑基：二叉查找樹、AVL樹、B樹和2-3-4樹

紅黑樹是一種比較高級的資料結構，要學習紅黑樹，首先需要一定的資料結構基礎，務必掌握二叉查找樹、AVL樹和B樹等資料結構，否則直接學習紅黑樹的話將如水中撈月、霧里看花，對于有一定資料結構基礎的人，可以直接跳過此節內容，

二叉查找樹

二叉查找樹的定義

回憶一下，我們小時候經常玩的一個猜字游戲，給一個數字范圍，讓參與者猜謎底是哪個字，很多人都是一點點的提高數值來猜，但是這樣猜會很沒有效率，因此，有些聰明人都知道需要利用折半查找的思想去猜測，假定某個產品在100元的范圍內，那么可以在7次之內猜出結果來，由于是100以內的正整數，所以我們先猜50（100的一半），被告之“大了”，于是再猜25（50的一半），被告之“小了”，再猜37（25與50的中間數），小了，于是猜43，大了，40，大了，38，小了，39，完全正確，

在計算機中，我們要在一組數字中查找其中一個，如果這組數字是無序存盤，則需要逐個遍歷，但是采用二叉樹的結構存盤的話，在查找時就可以實作每次遍歷后都能把剩余數字的范圍縮小一半的效果，

二叉查找樹是一種特殊的二叉樹，其改善了二叉樹結點查找的效率，二叉查找樹具有以下性質：
對于任意一個節點n：
1、其左子樹下的每個后代節點的值都小于節點n的值，
2、其右子樹下的每個后代節點的值都大于節點n的值，
3、左右子樹也均為二叉查找樹，
所謂節點 n 的子樹，可以將其看作是以節點 n 為根節點的樹，子樹的所有節點都是節點 n 的后代，而子樹的根則是節點 n 本身，

如下圖為典型的二叉查找樹：

二叉查找樹的型別

二叉查找樹按照其結構特征可以分為以下幾種型別，
一、斜樹
所有的結點都只有左子樹的二叉樹叫左斜樹，所有結點都是只有右子樹的二叉樹叫右斜樹，這兩者統稱為斜樹，
如下為右斜樹：

二、滿二叉樹
在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子節點（即沒有子節點的節點）都在同一層上，這樣的二叉樹稱為滿二叉樹，
滿二叉樹的特點有：
a.葉子節點只能出現在最下一層，出現在其它層就不可能達成平衡，
b.非葉子結點的度（結點擁有的子樹數目稱為結點的度）一定是2，
c.在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多，
如下為滿二叉樹

三、完全二叉樹
對一顆具有n個結點的二叉樹按層編號（按從上至下、從左到右的順序進行編號），如果編號為i(1<=i<=n)的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹，
完全二叉樹的特點：
a.葉子結點只能出現在最下層和次下層，
b.最下層的葉子結點集中在樹的左部，
c.倒數第二層若存在葉子結點，一定在右部連續位置，
d.如果結點度為1，則該結點只有左子節點，沒有右子節點，
e.同樣結點數目的二叉樹，完全二叉樹深度最小，
注：滿二叉樹一定是完全二叉樹，但反過來不一定成立，
下圖展示一棵完全二叉樹

前驅節點和后繼節點

前驅和后繼節點在樹的洗掉操作中有很重要的應用，
仍然以下面的二叉樹為例來說明：

（1）前驅節點
定義：中序遍歷的上一個節點（中序遍歷方法后面介紹），就是比當前節點的值小的最大的節點，
查找方法：
①若一個節點有左子樹，那么該節點的前驅節點是其左子樹中val值最大的節點（也就是左子樹中所謂的rightMostNode），例如12的前驅節點是11，因為11是其左子樹中的最大值，
②若一個節點沒有左子樹，那么判斷該節點和其父節點的關系
a. 若該節點是其父節點的右子節點，那么該節點的前驅結點即為其父節點，例如15的前驅節點是14，因為15是14的右子節點，
b. 若該節點是其父節點的左邊孩子，那么需要沿著其父親節點一直向樹的頂端尋找，直到找到第一個節點P，P節點是其父節點Q的右子節點，那么Q就是該節點的后繼節點，例如13的前驅節點是12，因為14是12的右子節點，因此12是13的前驅節點，

（2）后繼節點
定義：中序遍歷的下一個節點，就是比當前節點的值大的最小的節點，
查找方法：
①若一個節點有右子樹，那么該節點的后繼節點是其右子樹中val值最小的節點（也就是右子樹中所謂的leftMostNode），例如12的后繼節點是13，因為12是其右子樹的最小值，
②若一個節點沒有右子樹，那么判斷該節點和其父節點的關系，
a. 若該節點是其父節點的左子節點，那么該節點的后繼結點即為其父節點 ，例如13的后繼結點為14，因為13是14的左子節點，
b. 若該節點是其父節點的右子節點，那么需要沿著其父親節點一直向樹的頂端尋找，直到找到第一個節點P，P節點是其父節點Q的左子節點，那么Q就是該節點的后繼節點，例如11的后繼節點為12，因為10是12的左子節點，則12是11的后繼節點，

前驅與后繼節點的另一個查找方法是投射法，此方法在紅黑樹中通用，具體做法為：將二叉查找樹的所有節點投射到一條X軸上，則每個節點的左右相鄰的兩個節點即為其前驅節點和后繼節點，
如下圖所示，可以輕易看出13的前驅節點是12，后繼結點是13，

二叉查找樹的操作

一、查找
查找（紅黑樹通用）：查找每個節點我們從根節點開始查找查找值比當前值大，則搜索右子樹查找值等于當前值，停止查找，回傳當前節點查找值比當前值小，則搜索左子樹，具體步驟為：
（1）如果二叉查找樹為空，查找失敗，回傳null
（2）如果根節點的鍵等于要查找的鍵，回傳根節點的值
（3）否則，繼續在子樹中查找，如果要查找的鍵小于根節點的鍵，則在左子樹中查找，反之在右子樹中查找，如果根節點已經沒有即將需要查找的子樹，則查找失敗，
（4）重復以上步驟，直到查找成功或失敗為止，

對于 二叉查找樹的查找演算法來說，其十分依賴于樹中節點的拓撲結構，也就是節點間的布局關系，如果二叉查找樹n個節點構成高度為log-2n+1的二叉查找樹，其查找時間復雜度最小為 O(log-2n)，當二叉樹是斜二叉樹時，二叉查找樹已經退化為一個鏈表，此時查找的時間復雜度最大為O(n)，
因為在二叉查找樹是滿二叉樹的情況下，每一次經過數值比對之后，我們都能確定在左子樹中還是右子樹中繼續查找，然后需要查找的節點范圍就減少了一半，這樣不斷的減半，使得查找的時間復雜度為O(log-2n)，

二、遍歷
二叉查找樹的遍歷方式有三種，分別為：
（1）前序遍歷：先訪問根節點，再訪問左節點，最后訪問右節點（根、左、右），
（2）中序遍歷：先訪問左節點，再訪問根節點，最后訪問右節點（左、根、右），
（3）后序遍歷：先訪問左節點，再訪問右節點，最后訪問根節點（左、右、根），

以本文中的示例二叉查找樹為例，其如果按照中序遍歷的方式來進行遍歷的話：

①以4為根節點，按照按照先左再根后右的順序為246；
②以2為根節點，按照以上順序遍歷為123，則總順序為12346
③以6為根節點，按照以上順序遍歷為567，則總順序為1234567

三、插入
在二叉搜索樹中插入新元素時，必須先檢測該元素是否在樹中已經存在，如果已經存在，則不進行插入；否則將新元素加入到搜索停止的地方，
二叉搜索樹的插入很簡單，有一個核心點，不管是什么樹，最后都可以插入到葉節點的下面，不必在中間插入，因此，本質還是搜索，用二叉查找樹的搜索演算法，一直搜索到搜索失敗的葉子節點，最后比較要插入的值和葉節點的值大小決定是成為該葉節點的左節點還是右節點即可，

四、洗掉
洗掉操作的本質就是找前驅或者后繼節點來替代被洗掉的節點
（1）葉子節點直接洗掉（沒有前驅或后繼節點）
（2）只有一個子節點的用子節點替代（本質上就是找的前驅節點或者是后繼節點，左節點就是前驅節點，右節點就是后繼節點）
（3）有兩個子節點的，需要找到替代節點（替代節點就是前驅節點或者后繼節點），用前驅節點或者后繼節點來替代被洗掉的節點，

二叉查找樹的洗掉操作舉例，以下圖的二叉查找樹為基礎操作：

在以上的這個二叉查找樹中，如果洗掉節點15，因為15為葉子節點，所以可以直接洗掉：

繼續洗掉節點14，因為14已經只有1個子節點13，所以直接用13節點代替14節點即可，

然后再洗掉4，因為4有兩個子節點，所以需要使用其前驅節點或者后繼結點替代，使用后繼節點（4的后繼節點為5）替代則為：

二叉查找樹的局限性

BST存在的問題是，樹在插入的時候會導致傾斜，不同的插入順序會導致數的高度不一樣，而樹的高度直接影響了樹的查找效率，最壞的情況所有的節點都在一條斜線上，這樣樹的高度為N，此時的查查找效率最差，

基于BST存在的問題，平衡查找二叉樹（Balanced BST）產生了，平衡二叉樹在插入和洗掉的時候，會通過旋轉等操作將高度保持在LogN，其中兩種具有代表性的平衡二叉樹分別為AVL樹和紅黑樹，

AVL樹

AVL樹的概念

平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹，是一種具有自平衡功能的二叉查找樹，其具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹，因此AVL樹規定了任意節點的兩個子樹的高度查不能超過1，所以AVL樹不會一直向一個方向生長為斜樹，
例如，以下是AVL樹：

AVL樹的自平衡

AVL樹本質上就是一種有限制條件的二叉查找樹（二叉查找樹是空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹），因此其查找、插入和洗掉的方法和二叉查找樹是一樣的，但是因為AVL樹需要維持自身高度差絕對值不超過1的性質，所以在每次行程插入或者洗掉操作后需要對其結構進行調整，調整的程序就是AVL樹的自平衡，其自平衡的方法有兩種：左旋和右旋，

由于AVL樹的左旋、右旋方法和紅黑樹相同，所以將此部分內容放入紅黑樹部分講述，在此先展示以下左旋和右旋

如下為AVL樹左旋

如下為右旋

AVL樹的缺點

AVL樹嚴格規定了每一個節點的兩個子樹的高度差不能超過1，是一種強平衡的二叉樹，所以在每次新增或者洗掉節點中都需要通過旋轉來進行自平衡操作，其維持平衡性的成本太高，對于經常要進行插入和洗掉的資料，使用AVL樹來存盤并不合適，

B樹

B樹的概念

由于AVL樹的強平衡性，每次新增或者洗掉節點時都有進行自平衡操作，但是如果讓AVL樹的每個節點能包含多個元素，那么每次向AVL樹插入或洗掉元素時，就并不一定會引起其節點的變化，也就是不一定需要進行自平衡操作，則維護平衡性的成本就會大大降低，但是這樣做也會降低其查找效率，
按照這個解決思路，B樹應運而生，
B樹（B-tree）是一種樹狀資料結構，它能夠存盤資料、對其進行排序并允許以O(log n)的時間復雜度運行進行查找、順序讀取、插入和洗掉的資料結構，B樹，概括來說是一個節點可以擁有多于2個子節點的二叉查找樹，每個節點的子樹的數量成為B樹的階數，對于M階B樹，其其具有以下特點：
1、根節點和葉子節點至少有2個分支（子樹），其它節點至少有M/2向上取整個子節點，
2、每個節點最多有M個分支，
3、有n（k<=n<=M）個分支的節點有n-1個元素，它們按照遞增順序排列，其中k=2（根節點）或M/2向上取整（非根節點），
4、節點內的關鍵字互不相等，
5、葉子節點處于同一層，可以用空指標表示，代表查找失敗的位置，

如下為四階B-樹：

B樹的插入和洗掉

一、插入
針對M階高度為h的B樹，插入一個元素時，首先查找該元素在B樹中是否存在，如果不存在，即在葉子結點處結束，然后在葉子結點中插入該新的元素，
B樹插入的規則如下：
（1）若該節點元素個數小于m-1，直接插入；

（2）若該節點元素個數等于m-1，引起節點分裂；以該節點中間元素為分界，取中間元素（偶數個數，中間兩個隨機選取）插入到父節點中；

（3）重復上面動作，直到所有節點符合B樹的規則；最壞的情況一直分裂到根節點，生成新的根節點，高度增加1；

二、洗掉
B樹的洗掉規則為：首先查找B樹中需洗掉的元素,如果該元素在B樹中存在，則將該元素在其結點中進行洗掉；洗掉該元素后，首先判斷該元素是否有左右孩子結點，如果有，則上移孩子結點中的某相近元素(“左孩子最右邊的節點”或“右孩子最左邊的節點”)到父節點中，然后是移動之后的情況；如果沒有，直接洗掉，
（1）某結點中元素數目大于等于（m/2）-1,(m/2)向上取整，直接洗掉；
如以下4階B-樹中進行洗掉元素16：

（2）某結點中元素數目不大于（m/2）-1,(m/2)向上取整，但是兄弟節點的元素數量大于此值，則可以向兄弟節點借一個元素；
注意，如果B-樹的借元素只能間接的借，讓父節點中最近的元素下來與該元素所在的節點合并，兄弟節點最近的元素上去并入父節點，否則將破壞B-樹中元素分布的順序性，
如下圖的B-樹需要洗掉8，8元素所在的節點元素數量不夠，需要從兄弟節點借一個元素，此時需要把兄弟節點中與其最近的元素12上移與父節點合并，父節點中與其最近的元素10下移與8元素所在的節點合并，最后洗掉元素8，

（3）如果其相鄰兄弟不豐滿，即其結點中元素數量小于或等于(m/2)-1，則在該結點的父節點取出與該節點相連的元素，讓該元素下移，合并該節點與其相鄰的兄弟結點成一個結點；
例如要在下面的B-樹中洗掉10，兄弟節點和父節點都沒有多余的元素可以借，所以將父節點中與該節點相連的元素12下移，讓該節點和兄弟節點合并，然后洗掉：

2-3-4樹

2-3-4樹就是一種階為4的B-樹，因為其每個節點可能含有2、3、4個子節點，所以叫做2-3-4樹，在此不再介紹，
如下為2-3-4樹：

紅黑樹起步：性質與原理

前世今生

2-3-4樹的局限性

2-3-4樹的查詢操作像普通的二叉搜索樹一樣，非常簡單，并且因為2-3-4樹是一種弱平衡的二叉樹，所以每次進行插入和洗掉操作時，維護其平衡性的成本較低，但由于其結點元素數不確定，在一些編程語言中實作起來并不方便，
因為2-3-4樹是一種4階B樹，每個節點可以包含最多3個元素，所以在2-3-4樹進行插入和洗掉操作后，不一定每次都需要都進行自平衡操作，維護其平衡性的代價比AVL樹小的多，但是也因為其每個節點包含多個元素，所以其查找性能不如AVL樹，2-3-4樹實際上是在二叉樹的查找性能和維護平衡性的代價之間做出的權衡，
如果用編程語言來實作2-3-4樹，節點之間可以用指標來表達其關系，但是節點內部又包含多個元素，又要用內部的指標來表達，因此用編程語言來實作2-3-4樹非常繁瑣，

紅黑樹的由來

為了解決2-3-4樹用編程語言不易實作的缺點，最簡單的方法就是將包含多個元素的節點重新拆分為只包含一個元素的多個節點，形成一種新的二叉樹，拆分之后，原2-3-4樹的一個節點將變成多個只包含一個元素的節點，則需要給原2-3-4樹的每個節點做一個標記，以便能掌控拆分之后的二叉樹的高度，不讓其生長為斜樹，標記的方法為原2-3-4樹的一個節點中的多個元素拆成多個節點后，其中有且僅有1個節點使用黑色著色，其他節點均使用紅色，這種新的二叉樹就叫做紅黑樹，

因為2-3-4樹從其任一節點到它所能到達得葉子節點的所有簡單路徑包含的節點數相同，而且2-3-4樹的每個節點都會拆分為紅黑樹的一個黑色節點和多個紅色節點，所以在紅黑樹中從其任一節點到它所能到達得葉子節點的所有簡單路徑包含的相同的黑色節點，這就是紅黑樹的重要性質“黑色完美平衡”的由來，

2-3-4樹與紅黑樹的等價關系

紅黑樹就是由2-3-4樹的每個節點按照關鍵字進行拆分，然后進行重新組合而來的資料結構，
1、2-3-4樹的包含一個元素的節點等價紅黑樹中的黑色節點；
2、2-3-4樹的包含兩個元素的節點等價紅黑樹中的上黑下紅的兩個節點；
2、2-3-4樹的包含三個元素的節點等價紅黑樹中的上黑下兩紅的三個節點；

2-3-4樹上的3種節點拆分方法如下圖：

按照這種等價關系，我們可以將下面的2-3-4樹拆分重組成紅黑樹：

紅黑樹的五大性質

五大性質的內容

最初學習紅黑樹時，筆者首先看到的就是紅黑樹的五大性質，
（1）每個節點或者是黑色，或者是紅色，
（2）根節點是黑色，
（3）每個葉子節點（NIL）是黑色， [注意：這里葉子節點，是指為空(NIL或NULL)的葉子節點！]
（4）如果一個節點是紅色的，則它的子節點必須是黑色的，
（5）從一個節點到該葉子節點的所有路徑上包含相同數目的黑節點，

五大性質的原理

如果不懂紅黑樹的由來，就根本無法知道為什么需要有這五個性質，現在我們已經知道紅黑樹由2-3-4樹按照一定的規則拆分而來，就可以對這五個性質進行解釋：

紅黑樹的特性與原理：

（1）每個節點或者是黑色，或者是紅色，
紅黑樹由2-3-4樹轉變而來，2-3-4樹的每個節點按照關鍵字來拆分后，拆分而且的節點中需要選一個使用唯一顏色標記，代表原2-3-4樹上的一個節點，以便掌握紅黑樹的高度，這個唯一顏色就是黑色，其他節點用紅色區分，因此，2-3-4樹到紅黑樹的轉變方式決定了紅黑樹只要紅色或者黑色，

（2）根節點是黑色，
2-3-4樹到紅黑樹的轉變方式中，如果節點只有1個元素，則只拆分成1個黑色節點；如果節點有多個元素，則拆分后的節點都是上黑下紅的結構；無論2-3-4樹的根節點有幾個元素，拆分成紅黑樹后最上面的節點都是黑色，因此紅黑樹的根節點一定是黑色，

（3）每個葉子節點（NIL）是黑色， [注意：這里葉子節點，是指為空(NIL或NULL)的葉子節點！]
這個是人為規定的，不需要解釋，

（4）如果一個節點是紅色的，則它的子節點必須是黑色的，
在拆分2-3-4樹時，節點拆分之后的節點只有單個黑色，上黑下紅兩種形式，拼接在一起時不可能出現紅色相連，

（5）從一個節點到葉子節點的所有路徑上包含相同數目的黑節點，
因為2-3-4樹從其任一節點到它所能到達得葉子節點的所有簡單路徑包含的節點數相同，而且2-3-4樹的每個節點都會拆分為紅黑樹的一個黑色節點和多個紅色節點，可以說紅黑樹中的一個黑色節點即可代表2-3-4樹上的單個節點，所以在紅黑樹中從其任一節點到它所能到達得葉子節點的所有簡單路徑包含的相同的黑色節點，

紅黑樹成長：操作與自平衡

自平衡的方法與原理

紅黑樹要求達到黑色完美平衡，即從一個節點到葉子節點的所有路徑上包含相同數目的黑節點，如果我們對紅黑樹進行插入或者洗掉操作，可能會破壞這種平衡性，這時候就需要進行自平衡操作，

旋轉和變色

紅黑樹實作自平衡的方式有兩種，即旋轉和變色，其中變色很簡單，顧名思義就是將紅色節點變為黑色，或者將黑色節點變為紅色，旋轉的操作就稍顯復雜，會造成節點之間指標的變化，

紅黑樹的旋轉分為左旋和右旋，下面以右旋來論述旋轉的操作方法，
因為只討論旋轉，不涉及變色，所以此處的節點都定為無色，

如有以下的樹，有3個節點，該樹就是不平衡的，如果想讓該樹平衡，最簡單的辦法就是讓2和8分別成為5的左右子節點，

如下圖所示，2和8分別成為5的左右子節點，則該樹恢復平衡，
觀察從左到右的變化，相當于節點8向右順時針旋轉了大約90度，這種旋轉方式就是右旋，8節點叫做旋轉的支點，
到此，我們可以將右旋定義為：以P為支點，其左子節點為Q，將P向右下方旋轉，使得P變為Q的右子節點，這種旋轉方式為右旋，（P和Q為圖中標識的節點），

但實際上，我們需要做右旋的情況遠比這個要復雜，主要有以下情況需要處理
1、旋轉的支點P有父節點N
在完成右旋之后，P會變為其原左子節點Q的右子節點，因此P已經有了新的父節點，那么原有的父節點則需要作為Q的父節點，

2、旋轉節點的左子結點Q如果有右子結點
旋轉之后，支點P將會變成其左子節點P的右子節點，那么如果Q原本就有右子節點M，則M需要變更父節點，因為P在右旋時已經失去了左子節點Q（其左子節點Q變為P的父節點），所以M可以作為P的左子節點，

綜上，我們可以總結出，右旋：
以P為支點，其左子節點為Q，將P向右下方旋轉，使得P變為Q的右子節點，這種旋轉方式為右旋，如果支點P原本有父節點N，那么N在旋轉后變為Q的父節點；如果Q原本有右子結點N，那么N在旋轉后作為P的左子節點，

同樣的方法，我們也可以推匯出左旋：
以P為支點，其右子節點為Q，將P向左下方旋轉，使得P變為Q的左子節點，這種旋轉方式為左旋，
如果支點P原本有父節點N，那么N在旋轉后變為Q的父節點；如果Q原本有左子結點M，那么N在旋轉后作為P的右子節點，

下圖為左旋：

旋轉和變色在2-3-4樹中的等價效果

紅黑樹由2-3-4樹轉化而來，那么紅黑樹的變色和旋轉在2-3-4樹中都會對應一個等價效果，如果掌握這種等價效果，就能知道紅黑樹自平衡的方法及原理，

一、2-3-4樹節點分裂對應紅黑樹的節點變色
在2-3-4樹中，如果插入一個元素使得節點的元素數量大于3個則需要進行節點分裂，我們來看分裂前的2-3-4樹和分裂后的2-3-4樹分別對應的紅黑樹是什么樣子，
（注：？表示任意滿足要求的數字）

在上圖中，紅黑樹的變化是6的兩個子節點由黑邊紅，

如果最后6是根節點，還需要將6變為黑色，此時黑紅色高度增長了1，

在上圖中，紅黑樹的變化同樣是6的兩個子節點由黑邊紅，不同的是6依然是黑色，
由此，我們可以總結出：
規律一：2-3-4樹的節點分裂等價于紅黑樹的節點變色，2-3-4樹中包含4個元素的節點需要進行向上分裂，其中上移的元素為P；等價于在紅黑樹中將黑色節點P的兩個紅色子節點變為黑色，如果P是根節點，則最終需要變黑色，否則為紅色，

二、2-3-4樹的兄弟節點互借元素對應紅黑樹的旋轉加變色
1、向右邊兄弟節點借元素
在2-3-4樹中，如果需要從一個節點洗掉元素，這個節點中包含的元素不夠的話，首先要看其兄弟節點是否有多余的元素，有的話向兄弟節點借一個元素再洗掉自身的，借元素的方法為，兄弟節點與自己最近的元素上移與父節點合并，父節點與自己最近的元素下移與自己合并，

上圖的紅黑樹變化是以10為支點進行左旋，并且8由黑變紅色，12變為紅色，
如果變化后的12最終為根節點，則需要維持黑色：

上圖的紅黑樹變化依然是以10為支點進行左旋，并且8由黑變紅色，不同的是12最終維持黑色，
由此我們可以總結出：
規律二：2-3-4樹中某節點P需要從右邊的兄弟節點Q借關鍵字的操作方法，等價于紅黑樹中以該節點P的父節點M為支點進行左旋，并且將P變為紅色，如果旋轉后M為根節點則最終為黑色，否則為紅色，

2、向左兄弟節點借元素
如果2-3-4樹中的某個節點在洗掉時需要向左兄弟節點借一個元素，對應的紅黑樹變化又是什么情況呢，請看下圖：
在下圖中，我們需要從2-3-4中洗掉12，則需要從左兄弟節點中借一個元素：

上圖中的紅黑樹變化是以10為支點進行右旋，并且12由黑變紅，8變為紅色；
同樣的，如果紅黑樹中8最后是根節點，需要變黑色：

上圖中的紅黑樹變化同樣是以10為支點進行右旋，并且12由黑變紅，不同的是8維持黑色；
由此我們可以總結出：
規律三：2-3-4樹中某節點P需要從左邊的兄弟節點Q借關鍵字的操作方法，等價于紅黑樹中以該節點P的父節點M為支點進行右旋，并且將P變為紅色，如果旋轉后M為根節點則最終為黑色，否則為紅色，

三、2-3-4樹中節點合并對應紅黑樹的變色
當2-3-4樹需要洗掉一個元素時，如果兄弟節點沒有多余的元素，則需要父節點的元素下來與其合并：

上圖中紅黑樹的變化是10的兩個子節點由黑變紅，10變為黑色，
從以上我們可以看出，
規律四：2-3-4樹中父節點的某元素P下來與子節點合并等價于紅黑樹中的將P的黑色子節點變紅色，P本身變黑色，

總結：通過以上我們可以看出：紅黑樹通過旋轉和變色可以實作對應的2-3-4樹的節點分裂、合并和節點互借元素等自平衡方式，

紅黑樹的插入

紅黑樹的插入和AVL樹相似，都是在葉子節點上進行操作；不同的是紅黑樹在插入新的節點后，需要用過旋轉和變色這兩種方式來實作“黑色完美平衡”
因為紅黑樹需要維持黑色平衡，所以新插入的節點需要默認為紅色，以便減少自平衡的成本，當插入紅色的節點破壞了樹的平衡之后再進行調整，

各種插入場景

1、如果插入節點的父節點是黑色
相當于2-3-4樹中只包含1個元素的節點新增一個元素，不需要做任何自平衡的操作，只需要將紅色節點直接插入即可，

2、如果插入節點的父節點是紅色，并且父節點沒有兄弟節點或者兄弟節點是黑色
這個時候相當于在2-3-4樹中包含2個元素的節點內新增一個元素（因為兄弟節點是黑色，所以在2-3-4樹中是一個單獨的節點）
如下圖為插入之前：

此時我們只需要看插入的節點，其叔叔節點沒有變化不需要處理，
新增后的紅黑樹節點可能會得到以下四種結果：

其中的①和④顯然違反了紅黑樹的性質，即紅色節點不能相連，
其中對①的調整方式為先以1為支點進行右旋，再將1變為紅色，2變為黑色，則恢復黑色平衡

同樣的，對于④也是先旋轉再變色

3、如果插入節點的父節點是紅色，并且父節點的兄弟節點也是紅色
這種情況實際上對應2-3-4樹是在包含3個元素的節點上新增元素，在新增之前兩種分別為：

2-3-4樹的性質規定了每個節點只能含有最多3個關鍵字，如果多出3個，則需要向上分裂，在此，需要復習一下B樹的分裂方法：取出節點的中間元素，如果該節點沒有父節點，則中間元素向上分裂成為根節點；如果該節點有父節點，則中間元素向上與父節點合并，

我們在“自平衡的方法和原理”一節中已經得到規律一：“2-3-4樹的節點分裂等價于紅黑樹的節點變色，2-3-4樹中包含4個元素的節點需要進行向上分裂，其中上移的元素為P；等價于在紅黑樹中將黑色節點P的兩個紅色子節點變為黑色，如果P是根節點，則最終需要變黑色，否則為紅色”，現在可以按照此規律實作插入節點后的自平衡，

下面請看兩個插入關鍵字的操作：

（1）如果向葉子節點插入關鍵字3，則2-3-4樹會發生以下分裂動作，分兩種情況
①2-3-4樹中的葉子節點有父節點，則中間元素取出后需要與父節點合并
備注：其中的“？”號代表改葉子節點原父節點中的關鍵字
2-3-4樹分裂：

根據規律一：6需要向上分裂則將6的子節點變為黑色，如果6變換后非根節點則變為紅色，
因此，對應紅黑樹的變化為：

②如果2-3-4樹的葉子節點沒有父節點，則中間元素向上成為根節點，按照規律一，需要再把6節點變為黑色，紅黑樹的高度增長了1，

2-3-4樹分裂：

對應紅黑樹的變化為：

（2）如果向葉子節點插入關鍵字12
①2-3-4樹的葉子節點有父節點，則中間元素取出后需要與父節點合并
2-3-4樹分裂：

同樣我們利用規律一來實作紅黑樹插入后的自平衡，6需要向上移動分裂，則6的子節點由紅色變為黑色，對應紅黑樹的變化為：

②如果2-3-4樹的葉子節點沒有父節點，則中間元素向上成為根節點，因為紅黑樹的性質規定根節點必須是黑色，所以此時需要再把6節點變為黑色，紅黑樹的高度增長了1，
2-3-4樹分裂：

對應紅黑樹的變化為：

綜上，往2-3-4樹的四節點插入關鍵字時，節點需要向上分裂；對應的紅黑樹的節點需要變色，如果該節點沒有父節點，則紅黑樹的高度會增長1，

案例演示

在掌握了紅黑樹的新增操作后，我們來做一個小練習：
在以下2-3-4樹和等價的紅黑樹中分別新增13，并且實作自平衡：

首先我們來看2-3-4樹，13插入后首先會與10-11-12這個節點合并，然后該節點的關鍵字數量大于3，則需要向上分裂，其變化程序如圖所示：

在此2-3-4樹中，先后有兩個節點發生了變化，
①節點分裂：10-11-12這個節點新增13關鍵字后發生了分裂；

②節點新增關鍵字：7-9節點隨后新增了11關鍵字；

現在我們把兩步對應的紅黑樹操作分別進行一次，觀察效果：
1、節點分裂
在“自平衡方法和原理”一節中，我們得出規律：規律一：2-3-4樹的節點分裂等價于紅黑樹的節點變色，2-3-4樹中包含4個元素的節點需要進行向上分裂，其中上移的元素為P；等價于在紅黑樹中將黑色節點P的兩個紅色子節點變為黑色，如果P是根節點，則最終需要變黑色，否則為紅色，；因此在紅黑樹中我們首先把11的兩個紅色子節點變黑色，11非根節點因此本身變紅色；

2、節點新增關鍵字
在本節中我們得出，2-3-4樹的三節點新增關鍵字對應的紅黑樹操作是先旋轉再變色，因此我們要以7為支點進行左旋，再變色

這樣，我們就完成了紅黑樹的自平衡，

紅黑樹的洗掉

洗掉操作是紅黑樹最難的一環節，堅持就是勝利！

紅黑樹的洗掉方式

AVL樹、B樹、2-3-4樹等資料結構的新增都是在葉子節點上進行的，洗掉也是，即使洗掉的不是葉子節點的元素，也可不斷的使用其前驅和后繼節點來替代需要洗掉的節點，直到洗掉的是葉子節點為止，

1、如果要洗掉的替代節點是葉子節點，直接洗掉

2、如果洗掉的節點有唯一子節點，則使用子節點替代被洗掉的節點，

3、如果洗掉的節點有兩個子節點，則使用其前驅節點或者后繼節點來替代被洗掉的節點

另外：紅黑樹的洗掉在使用替代節點對洗掉節點進行替代之后，相當于洗掉了替代節點的那個位置，而且不論洗掉的是哪個節點，最終都可以轉化為洗掉葉子節點，即一個節點即將被洗掉，如果其前驅節點P和后繼節點Q均非葉子節點，那么可以使用P或Q的前驅或后繼節點再次對P/Q進行替代，最終轉化為洗掉葉子節點，
例如以下紅黑樹中洗掉5，5的后繼節點是6，則需要使用6來替代5，但是6并不是葉子節點，然而6也有自己的后繼節點6.5，則可以使用6.5再替代6的位置，這個時候就相當于洗掉了葉子節點6.5的位置了，

洗掉后的自平衡

因為紅黑樹由2-3-4樹演變而來，所以下面依然結合2-3-4樹來決議紅黑樹洗掉節點后的各種自平衡方法，
一、洗掉節點的替代節點為紅色
因為替代節點是紅色，所以洗掉以后不會影響紅黑樹的平衡性，直接洗掉即可，無需做任何自平衡操作，

二、替代節點是黑色
如果替代節點是黑色，那么洗掉以后紅黑樹將直接失去平衡，此時我們需要做自平衡了，
最終洗掉的替代節點都是葉子節點，如果這個葉子節點為黑色，說明在原始2-3-4樹中對應的是包含一個關鍵字的節點，
在2-3-4中，如果只包含一個關鍵字的節點被洗掉的化，也需要進行平衡操作，下面，將兩種樹的操作方法結合起來看，

1、替代節點的兄弟節點有紅色子節點
（1）替代節點的兄弟節點有1個紅色子節點
替代節點的兄弟節點有1個紅色子節點相當于在2-3-4中，洗掉節點的兄弟節點有多余的1個元素可以借，在紅黑樹中也可以使用借節點的方式來實作平衡，

以下圖為例，需要洗掉元素8所在的節點，其兄弟節點有12、14兩個關鍵字，其對應的紅黑樹如右圖（紅黑樹中的8為需要洗掉的替代節點），
注：其中“？”表示所以符合條件的元素，

首先看2-3-4樹的操作方法為：
①借關鍵字
父節點的下來與需要洗掉的節點合并，然后從兄弟節點選最近的一個關鍵是向上替代原父節點，使用的是這種間接借的方法，
②洗掉關鍵字8

回顧一下我們在“自平衡的方法與原理”中得到的規律二“2-3-4樹中某節點P需要從右邊的兄弟節點Q借關鍵字的操作方法，等價于紅黑樹中以該節點P的父節點M為支點進行左旋，并且將P變為紅色，如果旋轉后M為根節點則最終為黑色，否則為紅色”，

根據規律二，對應的紅黑樹的操作為，先以8的父節點10為支點左旋，再將8變為紅色，M如果最后不是根節點則為紅色，

如果M在旋轉后為根節點，則需要為黑色，此時對應的2-3-4樹和紅黑樹變化為：

（2）替代節點的兄弟節點有2個紅色子節點
替代節點的兄弟節點有2個紅色子節點相當于在2-3-4中，洗掉節點的兄弟節點有多余的2個元素可以借，但是因為2-3-4樹向兄弟節點借元素必須借的是兄弟節點中最近的一個元素，為了在紅黑樹中實作等價效果，需要多一次旋轉讓2-3-4中里替代節點最近的元素被借走，
例如有下面的2-3-4樹和紅黑樹，需要洗掉節點8，

因為再2-3-4樹中，應當將10上移與父節點合并，9下移與8元素的節點合并，但是此時在紅黑樹中10并不是8的相鄰節點，直接以11左旋，無法實作2-3-4樹中等價的借元素效果，所以以下為錯誤的做法：

正確的做法為：先在紅黑樹中以11為支點右旋，讓10與8相鄰，再依據我們以上總結的規律二，以9為支點進行左旋，8變為紅色：

同樣的，10最后為根節點，需要是黑色：

2、替代節點的父節點為紅色或者有紅色子節點
替代節點的父節點為紅色或者有紅色子節點，則相當于在2-3-4樹中，父節點有多余的元素，此時可以向父節點借一個元素，兩者在洗掉之前如下圖，最后需要洗掉的替代節點是8：

2-3-4樹的洗掉操作為將10元素下移與8、12節點合并成新的節點，然后從新節點中洗掉8元素：

根據規律四：2-3-4樹中父節點的某元素P下來與子節點合并等價于紅黑樹中的將P的黑色子節點變紅色，P本身變為黑色，因此，我們將下移的10節點的子節點變成紅色，10節點變為黑色，即可進行洗掉，
對應紅黑樹操作為：

3、替代節點的父節點為黑色并且無紅色子節點
替代節點的父節點為黑色并且無紅色子節點，對應的2-3-4樹為父節點和兄弟節點均只含有1個元素，

這個時候，我們依然利用“自平衡方法和原理”中得到的根據規律四：2-3-4樹中父節點的某元素P下來與子節點合并等價于紅黑樹中的將P的黑色子節點變紅色，P本身變為黑色，將6和12均變為紅色，10依然為黑色即可，

案例實戰

在以下紅黑樹及其對應的2-3-4樹中洗掉8：

直接給出答案，筆者累了，不再解釋
2-3-4樹的洗掉方式為：

對應的紅黑樹的洗掉方式為：