紅黑樹以及JAVA實現（一）
前言
紅黑樹是一種特殊的B樹是B樹種2-3-4樹的一種特殊實現，紅黑樹保證了每個節點只會有兩個子節點，通過對每個節點進行染色，然後通過不同顏色的節點組合來分別代表2-3-4的2節點、3節點、4節點樹的情況。在學習紅黑樹之前，我們需要先去了解2-3-4樹。
一、 B樹
那麼如果想要對紅黑樹有一個較為深刻的理解，我認為首先去理解其根源，也就是B樹是必不可少的
1.1 概念
樹形結構首先可以分為等叉樹和不等叉樹，等叉樹是每個節點的鍵值個數都相同、子節點個數也都相同，不等叉樹是每個節點的鍵值個數不一定相同、子節點個數也不一定相同。
最簡單的等叉樹是二叉樹，直接二叉樹的作用並不大，我們一般會要求二叉樹所有的節點按照一定的順序排列，這樣我們進行插入、刪除、查找時效率就會非常高，我們把這樣的樹叫做二叉搜索樹或者二叉查找樹。它的具體定義是這樣的，二叉搜索樹，要麼是個空樹，要麼符合以下幾個條件:
- 左子樹如果存在的話，左子樹所有節點的鍵值都要小於根節點的鍵值
- 右子樹如果存在的話，右子樹所有節點的鍵值都要大於根節點的鍵值
- 它的所有子樹也都要符合前面的兩個條件(前面的小於同時換成大於也成立)。
經過這樣定義之後，二叉樹就變成了二叉搜索樹，它的插入、刪除、查找效率一般情況下都是O(logn)。
相較於等叉樹，我們可以對不等叉樹的節點鍵數值數和插入、刪除邏輯添加一些特殊的要求使其能達到絕對平衡的效果，我們把這種樹叫做 B樹，全稱Balance Tree，是一種自平衡樹，它和等叉樹最大的不同首先表現在存儲結構上，等叉樹上每個幾點的鍵值數和分叉數都是相同的，而B樹不是。如果某個B樹上所有節點的分叉數最大值是m，則把這個B數叫做m階B數。下面我們來看一下B樹的具體定義：
- 所有節點最多有m個子節點
- 非根非葉子結點至少有m/2(向上取整)個子節點
- 根節點至少有兩個子節點(除非總結點數不足3個)
- 所有葉子節點都在同一層
- 任意節點如果有k個鍵值，則有k+1個子節點指針，鍵值要按照從小到大排列，子節點數上所有的鍵值都要在對應的兩個鍵值之間
B樹看似5條定義很複雜，但實際上自己分析一下理解後會發現還是蠻簡單的。第一條，對子節點數進行限制，這也是m階B樹m的由來，第二條，是用來限制樹的緊湊性，避免樹又高又長。第三條沒什麼好說的。第四條規定了B樹是一個絕對平衡樹不會退化為線性結構，所以B樹的效率永遠是O(logn)。第5條保證了B樹的元素的有序，以便高效率的查找。
1.2 2-3-4樹
2-3-4樹其實就是4階的B樹，目前網上講的紅黑樹大多數就是2-3樹或者是2-3-4樹轉化而成的。這裡僅對2-3-4樹進行講解
1.3 2-3-4樹的插入
節點分類
- 2節點：一個節點中有1個鍵值，2條鏈接
- 3節點：一個節點中有2個鍵值，3條鏈接
- 4節點：一個節點中有3個鍵值，4條鏈接
首先是2節點的插入，由於2-3-4樹是4階B樹，最多可以有4條連接，一個節點最多有3個鍵值，所以這裡直接添加即可
然後是3節點的插入，2節點插入之後，轉化為4節點，仍保持一個節點的狀態
4節點插入,由於2-3-4樹是4階B樹，所以當對4節點插入的時候，就需要對4節點進行分裂，首先將中間的節點上升，然後,根據B樹定義，將新增的節點和葉子的其中一個節點結合，形成一個3節點，比如，下圖中要插入4,首先123分裂，之後4根據大小順序，放在3的右邊，和3形成一個3節點。
之後如果繼續插入，第二層節點如果再形成4節點的情況下插入，那麼分裂之後出來的節點，應該和父節點再構成節點
如果向上和父節點構成節點，但是父節點已經是4節點了，這個時候父節點就需要繼續分裂，在往上的情況一次類推，進行遞歸分裂
1.4 2-3-4樹的刪除
相對於插入，B樹的刪除就相對複雜，需要分情況討論
1.4.1 當刪除節點是葉子節點
當刪除節點是葉子節點的時候，又分為以下情況
1.4.1.1 當刪除節點為非2節點
直接刪除即可，因為從一個非2節點中刪除一個鍵值以後，並不違反B樹的定義
1.4.1.2 當刪除節點為2節點
這種情況又要分多種情況
1.4.1.2.1 兄弟節點是非2節點
當兄弟節點是非2節點，我們可以直接從兄弟節點借一個元素過來，讓當前刪除節點形成非2節點，這樣情況就轉換為了2.3.3.1的情況，直接刪除要刪除的節點既可
1.4.1.2.2 兄弟節點是2節點
如果兄弟節點是2節點，那麼此時就需要從父節點借元素了，待刪除結點和父節點、兄弟節點構成一個4節點，然後將待刪除節點刪。
如果父節點是非2節點，那麼借走就接走了，如果是2節點，借走了當前位置就空了，所以需要再從這個節點的兄弟或父節點借一個元素，如果直到根節點也沒有找到一個非2節點，那麼這個B樹的高度就會減一。
1.4.2 如果刪除節點是非葉子節點
- 如果被刪除節點是非葉子節點，那麼我們就需要找到他的後繼元素，然後將後繼元素的值覆蓋被刪除元素，再將後繼元素刪除即可
- 那麼如何尋找後繼節點呢？一般來說就是key大小最接近被刪除元素的葉子節點中的元素，這個元素可以大於key也可以小於key，這個是我們可以自己定義，這裡我們選小於被刪除元素的那個。也就是左子樹節點中最大的元素。
二、 紅黑樹
通過上一節，我們了解了紅黑樹的前身或者說是其本源B樹之後我們再來看紅黑樹，相信你能夠更容易理解紅黑樹，看出其操作的底層邏輯
在講解之前我先講紅黑樹的類結構放出來
public class RedBlackBST<Key extends Comparable<Key>, Value> {
//很明顯，這個常量用來代指紅或黑
private static final boolean Red = true;
private static final boolean Black = false;
//根節點
private Node root;
//節點類結構
private class Node {
Key key;
Value value;
Node left, right, parent;
int N;
boolean color;
public Node(Key key, Value value, Node parent, int n, boolean color) {
this.key = key;
this.value = value;
N = n;
this.color = color;
this.parent = parent;
}
}
public RedBlackBST() {
}
//用來判斷一個節點是還是黑色
private boolean isRed(Node x) {
if (x == null) return false;
return x.color == Red;
}
}
2.1 紅黑樹的定義
紅黑樹，本質上其實就是將一個B樹（我們這裡討論2-3-4樹）轉化為一個二叉樹。那麼如何去轉化的同時又能繼承B樹絕對平衡性呢？答案就是通過染色和旋轉，到這裡打住，讓我們先來看紅黑樹的定義
- 所有的節點不是黑色就是紅色
- 根節點是黑色的
- 所有葉子節點是黑色的
- 從每個葉子到跟的所有路徑上不能有兩個連續的紅色節點
- 從任意節點到其每個葉子的所有路徑都包含相同數目的黑色節點
2.2 2-3-4樹節點到紅黑樹的轉換
在解釋這幾個定義之前我們需要先來開2-3-4樹中節點轉化到紅黑樹中的形式是怎樣的
首先我們要明白的是，在紅黑樹中，只有黑色節點才計入高度，紅色節點代表著其和父節點的鏈接是紅色的。
非2節點由黑色節點+紅色節點組合的形式表示，紅黑樹對應到2-3-4樹的節點組合中只會存在一個黑色節點。
2.2.1 2節點轉換
2.2.2 3節點轉換
3節點轉換成紅黑樹就是一個黑色節點帶著紅色子節點的樹，這個樹可以是左傾的也可以是右傾的，根據節點的key來決定，在以2-3樹為基礎實現的紅黑樹中，我們一般只允許左傾或則右傾樹存在，如果出現不允許的傾斜樹情況，一般會通過旋轉變色來調整。
2.2.3 4節點轉換
2.2.4 例子
2.3 紅黑樹定義解釋
先在我們再來來挨個看這5條定義
- 第一條這個沒什麼好說的，紅黑樹紅黑樹，那肯定節點不是紅色就是黑色
- 由於根節點必然是沒有父節點的，而在上面我們所列舉的轉換形式中並沒有紅色節點為父節點的結構，所以根節點必然是黑色的
- 在紅黑樹中葉子節點會默認擁有兩個為null的子節點，顏色自然是黑色
- 不允許又連續兩個紅色節點是為了限制紅黑樹的階數為4，不允許出現2、3、4節點之外的節點類型
- 對應2-3-4樹的第五條，保證了樹的絕對平衡，對應到紅黑樹中只有黑色節點代表高度，所以只需要保證黑色節點的數目一致即可。
2.3.1 紅黑樹的旋轉與變色
我們在對紅黑樹進行添加的時候，一開始按照二叉樹的方式添加，每個新節點的初始元素為紅色（root節點為黑色），當我們繼續進行添加，發現當前的紅黑樹結構不符合定義時，我們就需要通過旋轉和對節點變色來重新平衡紅黑樹。
2.3.2 紅黑樹的旋轉
先說旋轉，紅黑樹的旋轉分為左旋和右旋，我們先通過左旋來進行詳細講解。左旋就是一個節點繞著他的右子節點逆時針旋轉，變成右子節點的左子節點，我們以下圖為例
A進行左旋，變成B的左子節點，於此同時，B原先的左子樹變成A的右子樹，A的父節點變為B的父節點。
A的左子樹依舊是A的左子樹，B的右子樹也依舊是B的右子樹，不做變化。
這樣，我們就完成了一次左旋，右旋則是繞則操作節點自身的子節點順時針旋轉，變成左子節點的右子樹，左子節點的右子樹遷移到操作節點的左子樹，操作節點的父節點變成左子節點的父節點。原理一模一樣。
2.3.3 紅黑樹的變色
當然，我們在旋轉以後，如果不變色，結果肯定是不正確的，只有進行變色之後的紅黑樹才是正確的，由於變色有很多種情況，所以我們這裡只舉一個簡單的例子，後面在講解添加和刪除的時候再進行細緻列舉。
首先我們這裡有一個兩個節點的二叉樹，現在他是正確的，這個時候我們再插入一個新的節點3，那麼根據二叉樹的性質，插入後這個樹會變成這個樣子
當然，這個結果明顯是錯誤的，其結構明顯不符合我們我們在2.2.2中展示的任何一種形式,所以我們要通過旋轉和變色變換為2.2.2中的哪幾種形式。
首先這個組合在2-3-4樹種是一個4節點，但是他的形態並不符合紅黑樹的節點，所以我們需要將它轉換為已個合法的形態，先進行旋轉，1節點左旋，這個時候結構對了，但是顏色不對，需要將2變色為黑色，而1變色為紅色，這樣我們的這個紅黑樹就完全符合定義了。
這就是一個最簡單的旋轉變色的紅黑樹自動平衡過程。
下面是左旋和右旋的java程式碼實現，並沒有添加變色，因為變色的邏輯並不是固定的故而我們將其解耦到其他方法中
//左旋
Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
if(h.right!=null){
h.right.parent = h;
}
x.parent = h.parent;
h.parent = x;
x.left = h;
if(x.left!=null){
x.left.parent = x;
}
if(x.parent!=null){
int cmp = x.parent.key.compareTo(x.key);
if(cmp>0) x.parent.left = x;
else x.parent.right = x;
}
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
show();
return x;
}
//右旋
Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
if(h.left!=null){
h.left.parent = h;
}
x.parent = h.parent;
h.parent = x;
x.right = h;
if(x.right!=null){
x.right.parent = x;
}
if(x.parent!=null){
int cmp = x.parent.key.compareTo(x.key);
if(cmp>0) x.parent.left = x;
else x.parent.right = x;
}
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
show();
return x;
}
2.4 紅黑樹的添加
紅黑樹的添加分為以下幾種情況
2.4.1 在黑色節點下面插入
這種情況無論是插入在左還是右，都可以直接插入，紅黑樹的正確性不會受到影響
2.4.2 在紅色節點下插入且被插入節點無兄弟節點
2.4.2.1 當被插入的節點是右子節點
在右側插入
操作步驟：
- 節點1左旋
- 變色，1變色為紅色， 2變色為黑色
在左側插入
這種情況會比上面那種多一個步驟
-
節點3右旋，無需變色，這個操作主要是為了將情況轉換為上面在右側插入的情況，然後下面按照在右側的情況處理即可
-
節點1左旋
-
變色，1變色為紅色，2變色為黑色
2.4.2.2 當被插入節點是左子節點
其實這種情況和上面的處理邏輯是一樣的，只不過左右是反過來的，就不再贅述了，大家自己舉一反三即可。
2.4.3 在紅色節點下插入且被插入節點有兄弟節點
這種時候，我們需要先進行變色，再插入，如下圖（這裡，我們默認，1節點是有父節點的，1節點非根節點）
2和3節點變黑色，1節點變紅色，這個變化其實對應著2-3-4樹的4節點插入，其實就是講一個4節點拆分開來，中間的節點向上和父節點組合，左右兩邊的節點分裂為兩個單獨的節點，然後再正常插入一個新的節點。紅黑樹也是這麼個道理。
2、3節點變黑，形成單獨的節點，而1節點則變紅和父節點結合，那麼這裡我們要注意的是，1節點和父節點結合的時候，也相當於一次新的插入，相當於在1的父節點新插入一個紅色，所以這個過程是遞歸的，一直向上傳遞，直到紅黑樹的結構符合定義為止。
到這裡，紅黑樹的插入操作就結束了，以上的操作，只是單純的一步操作，這些操作只是在插入之後對被插入節點紅黑樹的一個平衡，我們在進行旋轉變色之後，很有可能上層的節點就又不符合定義了，這個時候我們就需要進行遞歸的旋轉變色， 直到最後整個紅黑樹平衡。
下面扔程式碼
程式碼
private void put(Key key, Value val) {
root = put(root, null, key, val); //進行插入，返回根節點作為查詢遍歷的起始節點保存
root.color = Black; //根節點的顏色必然是黑色
}
private Node put(Node h, Node p, Key key, Value val) {
if (h == null) {
return new Node(key, val, p, 1, Red);
}
//當插入的時候，發現路徑上有-4節點
if (isRed(h.left) && isRed(h.right)) flipColors(h);
//遞歸搜索樹，直到找到相同的key，修改，或者搜索到底層，進行插入。
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, h, key, val);
else if (cmp > 0) h.right = put(h.right, h, key, val);
else h.value = val;
//判斷紅黑，進行旋轉，調整樹的平衡
if (isRed(h.right) && isRed(h.right.right)) {
h.right.color = h.color;
h.color = Red;
h = rotateLeft(h);
}
if (isRed(h.right) && isRed(h.right.left)) {
//RL問題，先右旋,將問題轉換為RR
h.right = rotateRight(h.right);
//變色
h.right.color = h.color;
h.color = Red;
//再左旋
h = rotateLeft(h);
}
if (isRed(h.left) && isRed(h.left.left)) {
h.left.color = h.color;
h.color = Red;
h = rotateRight(h);
}
if (isRed(h.left) && isRed(h.left.right)) {
//LR問題，先左旋，將問題轉換為LL問題
h.left = rotateLeft(h.left);
//變色
h.left.color = h.color;
h.color = Red;
//再右旋
h = rotateRight(h);
}
h.N = size(h.left) + size(h.right) + 1;
return h;
}
結語
本章中我們學習了紅黑樹的起源，B樹，然後學習了紅黑樹的插入。由於紅黑樹的刪除較為複雜，我們放到下一章在進行講解
