紅黑樹——一種自平衡的二叉樹
一、紅黑樹簡介
普通二叉樹在資料不夠均勻的情況下，可能導致左右子樹高度會相差比較大，最壞情況下樹的結構相當于一個鏈表，時間復雜度為n，為了使二叉樹在最壞情況下也能有log(n)的性能，需要對二叉樹進行平衡操作，相應的演算法有很多，紅黑樹就是其中一種演算法，紅黑樹是一種自平衡的二叉搜索樹，它每一個節點有一個存盤位表示顏色，通過對路徑上的顏色約束，紅黑樹保證沒有一條路徑比其他路徑長2倍，因而是接近平衡的，相對于普通的二叉搜索樹，紅黑樹在最壞的情況下保證插入和洗掉操作的時間復雜度是log(n)
一顆紅黑樹需要滿足下列5條規則：
- 每一個節點是紅色和黑色的一種
- 根節點是黑色的
- null節點是黑色，也就是所以的葉子節點都是黑色
- 紅色節點不能相鄰（也就是紅色節點的孩子必定是黑色）
- 從任意一個節點到葉子節點（不包含這個節點），黑色節點的數量相同，這個規則也叫紅黑樹的黑高
紅黑樹的搜索與一般的搜索二叉樹沒有其他區別，主要的區別是插入和洗掉操作，因為這兩個操作會修改二叉樹結構，導致紅黑樹規則被破壞，紅黑樹通過變色、左旋、右旋來修復規則被破壞的情況，下面簡單介紹一下這三個規則，
1、變色
變色，顧名思義就是改變紅黑樹的顏色，也就是紅變黑，黑變紅，變色作用的是單個節點，一些文章把變色總結成了復合操作其實是不對的，變色規則需要結合情況具體分析，死記不利于理解紅黑樹的（說不定還記不住），實際上變色目的是改變節點路徑上黑色數量，把一個節點變成黑色，可以增加這個節點路徑上黑色節點的數量，反之則減少黑色節點的數量，
變色示意圖：
2、左旋
某個節點左旋，這個節點的右孩子不能為空，把一個節點向左旋轉，“右孩子”替換節點位置，把節點作為“右孩子”新左節點，“右孩子”的“左孩子”變成節點新的右孩子，規則有點繞，看一下示意圖就明白了：
圖中B是A的右孩子，提升B的位置，A作為B的左孩子，然后把C作為A的右孩子，左旋只會改變旋轉節點右邊的子樹，不會改變節點的左子樹，如圖D相對于A的位置還是不變的，左旋的一個特性是會把右子樹的高度變低，左子樹變高，另一個特性是可以調換左右子樹的元素，
3、右旋
某個節點右旋，這個節點的左孩子不能為空，把一個節點向右旋轉，“左孩子”替換節點位置，把節點作為“左孩子”新右節點，“左孩子”的“右孩子”變成節點新的左孩子，示意圖如下：
圖中B是A的左孩子，提升B的位置，A作為B的右孩子，然后把C作為A的左孩子，右旋只會改變旋轉節點左邊的子樹，不會改變節點的右子樹，如圖D相對于A的位置還是不變的，右旋的一個特性是會把左子樹的高度變低，右子樹變高，另一個特性是可以調換左右子樹的元素，
二、紅黑樹的插入
1、叔叔節點
首先介紹一下叔叔節點，叔叔節點顧名思義就是父親節點的兄弟，例如下面這個結構，C節點的父親為B，叔叔節點為D：
2、新節點的顏色分析
首先可以證明插入的新節點一定是紅節點，如果插入節點是黑節點，那么當插入第二個節點，規則5肯定無法滿足了（例如從根節點到左右葉節點的黑高不一樣），由于插入黑色節點必然會破壞紅黑樹的規則，所以不如一開始插入紅色節點高效，所以插入的節點需要是紅節點，
如上圖，插入的新節點0如果是黑色，會導致根節點5到葉子節點的距離不一致，此時只能把新節點0變回紅色，同理多層節點情況下如果新節點是黑色也一定要執行變色或旋轉才能修復規則
3、插入位置是根節點
如果插入的位置是根節點，則直接把這個節點變成黑色，即可滿足紅黑樹所有性質
4、插入位置的父親節點是黑色
在一個黑色節點的下方插入一個紅色節點，由于紅色節點不提供黑色數量，此時直接插入新節點即可，
如圖，在一個黑色節點（5）下方插入一個紅色節點，不會破壞紅黑樹任何規則
5、插入位置的父節點是紅色
如果插入節點的父親節點是紅色，那么很明顯此時紅黑樹不滿足規則4（紅色節點不能相鄰），此時就需要通過變色/旋轉操作來修復破壞的紅黑樹規則，由于規則4（紅色節點不能相鄰）的約束，因為插入前是滿足紅黑樹規則的，所以此時爺爺節點必定是黑色，所以此時只有兩種情況：
- 節點的叔叔節點是紅節點
- 節點的叔叔節點是黑節點
5.1、節點的叔叔節點是紅節點
已知插入前父親節點和叔叔節點是紅色，那么根據紅黑樹規則，爺爺節點必定是黑色，此時只要把爺爺節點的黑色分給父親和叔叔就行了，也就是把父親節點和叔叔節點變成黑色，爺爺節點變成紅色，如下圖所示：
如圖，插入了一個新節點15，破壞了規則4（紅色節點不能相鄰），因為叔叔節點0是紅色的，可以把爺爺節點5的顏色分給叔叔節點0和父親節點10，由于爺爺節點的左右子樹同時增加的1的黑色，所以此時規則5也可以被滿足，
但是由于我們不知道爺爺節點5的父親是什么顏色，我們需要把檢查的標記定位到爺爺節點5上，再次檢查紅黑樹是否因為此次變色操作破壞了其他規則，
5.2、節點的叔叔節點是黑節點
如果叔叔節點是黑色，所以通過拆分爺爺節點顏色來修復規則（拆分顏色后叔叔相當于有2層黑），那可不可以把新節點直接換到叔叔節點下呢？答案是不可以，因為節點的不光要滿足紅黑樹的規則，也要滿足搜索二叉樹的規則，我們不可以隨便交換節點的位置，否則搜索的時候就會出問題，雖然直接調換位置不行，但是可以通過旋轉來間接調換位置，
以節點插入的子樹是其爺爺的右子樹為例，此時插入的新節點15：
5.2.1是插入后紅黑樹情況、5.2.2是以爺爺節點5左旋后紅黑樹情況、5.2.2是變色后紅黑樹情況
因為要換一個節點到另一邊，所以對爺爺節點5進行左旋，然而左旋會使叔叔節點的子樹的黑色數量+1，父親節點的子樹黑色數量少1，雖然修復了規則4，但是又新破壞了規則5，所以這時需要一個變色操作來修復再次被破壞的規則5，很顯然旋轉后只需要之前爺爺節點5變紅，父親節點10變黑就能修復規則5，
但是假設插入的節點值是7，直接左旋會把新節點7也帶到左子樹，所以此時先要以父親節點進行一次右旋，轉換為圖5.2.1中類似的情況，
然后再以爺爺節點5進行左旋和變色即可恢復規則
同理，如果節點插入的子樹是其爺爺的左子樹也是類似的情況，這里就不多贅述，
6、插入操作偽代碼
//node的屬性color、left、right，parent分別為節點的顏色、節點的左子節點、節點的右子節點、節點的父親
//列舉RED為紅，BLACK為黑
//leftRotate為左旋函式
//rightRotate為左旋函式
//Root為根節點的指標
//fixInsertRule的node引數為新插入的節點
fixInsertRule(node){
while(node != ROOT and node.parent.color == RED){
grandparent = node.parent.parent//爺爺節點，由于父親節點是紅色，爺爺節點顏色必定是黑色
if(node.parent == grandparent.right){
uncle = grandparent.left;//叔叔節點
if(uncle.color == RED){//叔叔節點是紅色
uncle.color = BLACK;
node.parent.color = BLACK;
grandparent.color = RED;
//把檢查節點定位到爺爺節點上，繼續下一次的回圈
node = grandparent;
}else{//叔叔節點是黑色
if(node == node.parent.left){
//先要以父親進行一次右旋
//這里需要注意的是右旋后原來的父親變成孩子，原來的孩子變成父親
//所以爺爺節點和叔叔節點還是不變的
node = node.parent;
rightRotate(node);
}
//為了方便，先變顏色
node.parent.color = BLACK;
grandparent.color = RED;
//以爺爺節點左旋
leftRotate(grandparent);
}
}else{
//節點位置是爺爺節點的左子樹的情況，這里省略...
}
}
//旋轉和變色后可能會導致根節點會變紅，重新設定根節點為黑色即可
ROOT.color = BLACK;
}
三、紅黑樹的洗掉
相對于插入操作，二叉樹的節點洗掉的方式有很多種，比如下面這顆樹，需要洗掉節點20，既可以使用節點10來替換被洗掉的20節點，然后把節點30連接到左子樹最大的節點后面，也可以使用節點30來替換被洗掉節點，然后把節點10連接到右子樹最小的節點后面
但是這兩種方案都不太適合紅黑樹，紅黑樹在插入時會平衡左右子樹的高度，上面兩種方案會讓洗掉節點左右子樹變成極大的不平衡，所以紅黑樹的洗掉需要找一個影響結構最小的洗掉方案，
使用后繼節點替代被洗掉節點是一個很好的方案（前繼節點也行，本文以后繼節點進行分析），由于是后繼節點，那么后繼節點最多只會有一個右孩子，使用后繼節點替換洗掉節點，并不會影響前繼節點的子樹，所以只需要對后繼節點右子樹進行向上檢查即可修復規則，
使用后繼節點的洗掉方案，只會影響后繼節點所在的子樹，
使用后繼節點替換洗掉節點，只需要把后繼節點的顏色變成和洗掉節點一樣，然后從后繼節點的右孩子開始檢查紅黑樹是否滿足，由于洗掉前是滿足紅黑樹規則的，所以后繼節點和后繼右孩子的顏色只會有這幾種情況，
- 后繼節點是紅色，后繼右孩子是黑色，此時后繼節點的父親一定為黑
- 后繼節點是黑色，后繼右孩子是紅色，后繼節點的父親的顏色不確定
- 后繼節點是黑色，后繼右孩子是黑色，后繼節點的父親的顏色不確定
1、后繼節點是紅色
因為后繼節點是紅色，說明后繼右孩子必定是黑色，父親節點必定也是黑色，使用一個黑色節點替換紅色節點的位置，既不會破壞規則4，也不會破壞規則5，此時無需對樹的結構進行修復，
2、后繼節點是黑色，后繼右孩子是紅色
把后繼右孩子變成黑色，即可滿足規則5
3、后繼節點是黑色，后繼右孩子是黑色
因為后繼右孩子本身是黑色，無法繼續變黑，如果要滿足規則5，需要后繼右孩子具有2層的黑色屬性才行，既然一個節點不能有2層黑色，可以想辦法把多余的這層黑色移到合適的位置來修復規則5，
根據后繼右孩子的兄弟節點顏色，又可以分為這幾種情況：
- 兄弟節點是紅色
- 兄弟節點是黑色，兄弟節點的孩子都是黑色，父親節點顏色不確定
- 兄弟節點是黑色，兄弟節點的其中一個孩子是紅色，父親節點顏色不確定
3.1、后繼右孩子的兄弟節點是紅色
因為兄弟節點是紅色，那么父親節點必定為黑，此時對父親節點進行旋轉和變色操作即可把兄弟節點變成黑色，也就是情況1可以轉化成情況2和情況3，
以上圖為例，假設節點0為后繼右孩子節點，10為兄弟節點，以父親節點5進行左旋+變色可以把節點0的兄弟節點變成黑色，此時轉化為3.2或3.3的場景，這個旋轉+變色操作并不會使黑色節點數量發生變化，需要繼續執行后續場景的操作，
3.2、后繼右孩子的兄弟節點是黑色，兄弟節點的孩子都是黑色
可以把兄弟節點設定成紅色，相當于提取了兄弟和自己的一層黑色給父親，因為無法確定父親節點的顏色，需要繼續以父親節點作為檢查節點重新規則檢查，
3.2、后繼右孩子的兄弟節點是黑色，兄弟節點的其中一個孩子是紅色
加上后繼節點的顏色是父親節點的左孩子，兄弟節點的右孩子是紅色，此時以父親節點進行左旋，把父親節點和兄弟節點的右孩子的顏色也變成黑色，此時相當于后繼節點這邊的子樹多了一個黑色節點，且兄弟節點這邊的黑色節點數量不變，規則5被修復，
旋轉后把原來的父親節點5染黑，兄弟節點10的顏色改成和原父親節點5一樣的顏色，白色的節點表示顏色不確定
如果兄弟節點的左孩子是紅色，可以先以兄弟節點進行右旋，這樣就轉換成上面的“兄弟節點的右孩子是紅色”的情況了，
旋轉兄弟節點，把情況轉換“兄弟節點的右孩子是紅色”，白色的節點表示顏色不確定
4、洗掉操作的偽代碼
//node的屬性color、left、right，parent分別為節點的顏色、節點的左子節點、節點的右子節點、節點的父親
//列舉RED為紅，BLACK為黑
//leftRotate為左旋函式
//rightRotate為左旋函式
//Root為根節點的指標
//nodeParent為后繼右節點的父節點，因為后繼右節點可能為空，需要傳入它的新父節點
//nodeParent為后繼右節點
//呼叫fixDeleteRule前已經確認后繼節點是黑色了
fixDeleteRule(nodeParent,node){
while(node != ROOT and node.color == BLACK){
if(node == nodeParent.left){
//如果節點是父親節點的左孩子
borther = nodeParent.right;//兄弟節點
if(borther.color == RED){
borther.color = black;
nodeParent.color = RED;
leftRotate(nodeParent);
borther = nodeParent.left;
}
if(borther == null or (borther.left.color == BLACK and borther.right.color == BLACK)){
borther.color = RED;
//顏色被提取到父親節點上了，設定新的檢查節點為父親節點
node = nodeParent;
nodeParent = node.parent;
}else{
if(borther.left.color == RED){
borther.color = RED;
borther.left.color = BLACK;
rightRotate(borther);
}
//剩下的情況必定是兄弟節點的右孩子為紅色
borther.color = nodeParent.color;
nodeParent.color = BLACK;
borther.right.color = BLACK;
leftRotate(nodeParent);
//規則已經修復，設定為根指標
node = Root;
}
}else{
//node是nodeParent的右孩子的情況，代碼略...
}
}
//有可能node變成了根節點，需要修復一下顏色
node.color = BLACK;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544081.html
標籤：Java