尋找紅黑樹的操作手冊
前言
二叉樹知識點回憶以及整理這篇文章中我們說過“二叉樹是一個簡單的二分查找泊藕，但其性能取決于二叉樹的層數(shù)”。
- 最好的情況是O(logn),存在于完全二叉樹情況下，其訪問性能近似于折半查找娃圆；
- 最差的情況是O(n),比如插入的元素所有節(jié)點都沒有左子樹（右子樹）玫锋，這種情況需要將二叉樹的全部節(jié)點遍歷一次。
紅黑樹本質(zhì)上是一種二叉查找樹讼呢，在節(jié)點類中添加類一個用來標(biāo)識顏色的字段撩鹿，同時具有一定的規(guī)則。同時具備這亮點使得紅黑樹的性能達(dá)到理想中的均衡狀態(tài)（插入悦屏、刪除节沦、查找的最壞時間負(fù)責(zé)度為O(logn)）。
在Java1.8中HashMap使用的就是鏈表和紅黑樹础爬，遲到一年HashMap解讀甫贯。Java集合中的TreeSet和TreeMap，C++ STL中的set看蚜、map叫搁，以及Linux虛擬內(nèi)存的管理，都是通過紅黑樹去實現(xiàn)的供炎。
簡介
紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹渴逻，是在計算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組音诫。它是在1972年由魯?shù)婪颉へ悹柊l(fā)明的惨奕，他稱之為"對稱二叉B樹"，它現(xiàn)代的名字是在Leo J. Guibas和Robert Sedgewick于1978年寫的一篇論文中獲得的竭钝。它是復(fù)雜的墓贿，但它的操作有著良好的最壞情況運(yùn)行時間，并且在實踐中是高效的：它可以在 O(logn)時間內(nèi)做查找蜓氨，插入和刪除聋袋，這里的n是樹中元素的數(shù)目，摘自：維基百科-紅黑樹穴吹。
public class RBTree<T extends Comparable<T>> {
public RBNode<T> mRoot = null; // 根結(jié)點
public static boolean RED = true;
public static boolean BLACK = false;
class RBNode <T extends Comparable<T>> {
//顏色
boolean color;
//關(guān)鍵字（鍵值）
T key;
//左子節(jié)點
RBNode<T> left;
//右子節(jié)點
RBNode<T> right;
//父節(jié)點
RBNode<T> parent;
public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
@Override
public String toString() {
return "" + key + (this.color == RED ? "RED" : "BLACK");
}
}
}
紅黑樹特點
- 1幽勒、每個節(jié)點不是紅色就是黑色的；
- 2港令、根節(jié)點總是黑色的啥容；
- 3、所有的葉節(jié)點都是是黑色的（紅黑樹的葉子節(jié)點都是空節(jié)點（NIL或者NULL））顷霹；
- 4咪惠、如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）淋淀；
- 5遥昧、從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）。
需要注意：
特性3中的葉子節(jié)點炭臭，是只為空(NIL或null)的節(jié)點永脓。
特性5，確保沒有一條路徑會比其他路徑長出倆倍鞋仍。因而常摧，紅黑樹是相對是接近平衡的二叉樹。
紅黑樹的修正
變色威创、左旋落午、右旋是紅黑樹在二叉樹上的擴(kuò)展操作，同時也是基于這三個操作才能遵守紅黑樹的五個特性肚豺。所以熟悉二叉樹操作的同學(xué)只要掌握這紅黑樹這三個操作那么就能更加容易的理解進(jìn)行紅黑樹的添加和刪除之后怎么保證其平衡性板甘，不熟悉二叉樹的也可以先看看《二叉樹知識點回憶以及整理》這片文章。
變色
變色僅僅指的是紅黑樹節(jié)點的變色详炬。因為紅黑樹節(jié)點必須是【紅】或者【黑】這兩中顏色盐类，所以變色只是將當(dāng)前的節(jié)點顏色進(jìn)行變化，以滿足特性（2呛谜，3在跳，4，5）隐岛。
左旋
通常左旋操作用于將一個向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接猫妙。示意圖如下：
左旋操作動畫（更加容易理解和記憶）：
/*************對紅黑樹節(jié)點x進(jìn)行左旋操作 ******************/
/*
* 左旋示意圖：對節(jié)點x進(jìn)行左旋
* p p
* / /
* x y
* / \ / \
* lx y -----> x ry
* / \ / \
* ly ry lx ly
* 左旋做了三件事：
* 1. 將y的左子節(jié)點賦給x的右子節(jié)點,并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)
* 2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點，同時更新p的子節(jié)點為y(左或右)
* 3. 將y的左子節(jié)點設(shè)為x聚凹，將x的父節(jié)點設(shè)為y
*/
public void leftRotate(RBNode<T> x) {
if (x == null) return;
//1. 將y的左子節(jié)點賦給x的右子節(jié)點,并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)
RBNode<T> y = x.right;
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
//2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點割坠，同時更新p的子節(jié)點為y(左或右)
y.parent = x.parent;
if (x.parent == null) {
//mRoot是RBTree的根節(jié)點
this.mRoot = y;
} else {
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
//3. 將y的左子節(jié)點設(shè)為x，將x的父節(jié)點設(shè)為y
y.left = x;
x.parent = y;
}
右旋
右旋可左旋剛好相反妒牙，這里不再贅述彼哼，直接看示意圖：
右旋操作動畫（更加容易理解和記憶）：
/*************對紅黑樹節(jié)點y進(jìn)行右旋操作 ******************/
/*
* 右旋示意圖：對節(jié)點y進(jìn)行右旋
* p p
* / /
* y x
* / \ / \
* x ry -----> lx y
* / \ / \
* lx rx rx ry
* 右旋做了三件事：
* 1. 將x的右子節(jié)點賦給y的左子節(jié)點,并將y賦給x右子節(jié)點的父節(jié)點(x右子節(jié)點非空時)
* 2. 將y的父節(jié)點p(非空時)賦給x的父節(jié)點，同時更新p的子節(jié)點為x(左或右)
* 3. 將x的右子節(jié)點設(shè)為y湘今，將y的父節(jié)點設(shè)為x
*/
public void rightRotate(RBNode<T> y) {
if (y == null) return;
//1. 將x的右子節(jié)點賦給y的左子節(jié)點,并將y賦給x右子節(jié)點的父節(jié)點(x右子節(jié)點非空時)
RBNode<T> x = y.left;
y.left = x.right;
if (x.right != null) {
x.right.parent = y;
}
//2. 將y的父節(jié)點p(非空時)賦給x的父節(jié)點敢朱，同時更新p的子節(jié)點為x(左或右)
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x;
} else {
if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
}
//3. 將x的右子節(jié)點設(shè)為y，將y的父節(jié)點設(shè)為x
x.right = y;
y.parent = x;
}
紅黑樹節(jié)點的添加
紅黑樹是在二叉樹的基礎(chǔ)上進(jìn)行擴(kuò)展的摩瞎，其添加節(jié)點也是像二叉樹一樣進(jìn)行添加拴签，然后再做調(diào)整。二叉樹知識點回憶以及整理#創(chuàng)建二叉樹 這部分講述了二叉樹節(jié)點的添加旗们。所以這里我們重點講述二叉樹的添加完后的調(diào)整蚓哩。
- 紅黑樹的第 5 條特征規(guī)定，任一節(jié)點到它子樹的每個葉子節(jié)點的路徑中都包含同樣數(shù)量的黑節(jié)點上渴。也就是說當(dāng)我們往紅黑樹中插入一個黑色節(jié)點時岸梨，會違背這條特征喜颁。
- 同時第 4 條特征規(guī)定紅色節(jié)點的左右孩子一定都是黑色節(jié)點，當(dāng)我們給一個紅色節(jié)點下插入一個紅色節(jié)點時盛嘿，會違背這條特征洛巢。
因此我們需要在插入黑色節(jié)點后進(jìn)行結(jié)構(gòu)調(diào)整括袒，保證紅黑樹始終滿足這 5 條特征次兆。
紅黑樹插入后節(jié)點的調(diào)整思想
數(shù)學(xué)里最常用的一個解題技巧就是把多個未知數(shù)化解成一個未知數(shù)。
我們插入黑色節(jié)點的時候擔(dān)心違背第5條锹锰，插入紅色節(jié)點時擔(dān)心違背第4條芥炭，所以我們將將插入的節(jié)點改為紅色，然后判斷插入的節(jié)點的父親是不是紅色恃慧，是的話進(jìn)行修改調(diào)整（變色园蝠、左旋、右旋）痢士。同時在調(diào)整的過程中我們需要遵守5條特性彪薛。
因為左右子樹的操作是對稱的，我們下邊講述需要添加的節(jié)點的父節(jié)點是祖父節(jié)點的左孩子的情況怠蹂，右子樹添加與其相反善延。
- 1、如果我們添加的【紅色節(jié)點】的【父節(jié)點】是黑色城侧，那么樹不需要做調(diào)整易遣。
- 2、如果我們添加的【紅色節(jié)點】的【父節(jié)點】是紅色嫌佑，那么樹需要做調(diào)整豆茫。
- 1）、父節(jié)點是紅色屋摇，叔叔節(jié)點（父節(jié)點的兄弟節(jié)點）是紅色的揩魂。
- 2）、父節(jié)點是紅色炮温，叔叔節(jié)點是黑色肤京，添加的節(jié)點是父節(jié)點的左孩子。
- 3）茅特、父節(jié)點是紅色忘分，叔叔節(jié)點是黑色，添加的節(jié)點是父節(jié)點的右孩子白修。
父節(jié)點是黑色妒峦，祖父節(jié)點一定是黑色的，因為紅色節(jié)點的父節(jié)點不可能是紅色（特性4:每個紅色節(jié)點的兩個子節(jié)點一定都是黑色）兵睛。
調(diào)整-情況（1）：父節(jié)點是紅色肯骇，叔叔節(jié)點（父節(jié)點的兄弟節(jié)點）是紅色的窥浪。
下圖是這樣情況的紅黑樹的修改過程（上邊是目標(biāo)節(jié)點為左孩子，下邊是目標(biāo)節(jié)點是右孩子）：
為了新添加的節(jié)點也滿足特性4:
- 將父節(jié)點和叔叔節(jié)點全部染成黑色（節(jié)點T滿足了特性四）笛丙，但是這樣父親和叔叔節(jié)點的分支都多了一個黑色漾脂；
- 將祖父節(jié)點染成紅色，這樣祖父節(jié)點的兩個分支滿足了所有特性胚鸯，但是我們需要檢驗祖父節(jié)點是否符合紅黑樹的特性骨稿；
- 將祖父節(jié)點當(dāng)前插入節(jié)點，繼續(xù)向樹根方向進(jìn)行修改姜钳；
這樣我們一直向上循環(huán)坦冠，直到父節(jié)點變?yōu)楹谏蛘哌_(dá)到樹根為止哥桥。
調(diào)整-情況（2）：父節(jié)點是紅色辙浑，叔叔節(jié)點是黑色，添加的節(jié)點是父節(jié)點的左孩子拟糕。
下圖是這樣情況的紅黑樹的修改過程:
我們通過將祖父節(jié)點的左孩子分支上的連續(xù)兩個紅色節(jié)點判呕，轉(zhuǎn)移一個插入到祖父節(jié)點和他的右孩子之間（保證左邊沒有兩個連續(xù)紅點、右邊插入的紅點滿足所有特性）送滞。
- 先將父節(jié)點染成黑色侠草；
- 將祖父節(jié)點染成紅色；
- 將父節(jié)點進(jìn)行右旋累澡；
我們僅僅通過以上3個步驟就調(diào)整完使整個紅黑樹的節(jié)點滿足5個特性梦抢。
調(diào)整-情況（3）：父節(jié)點是紅色，叔叔節(jié)點是黑色愧哟，添加的節(jié)點是父節(jié)點的右孩子奥吩。
下圖是這樣情況的紅黑樹的修改過程:
我們父節(jié)點進(jìn)行左旋操作，這樣就變成了調(diào)整-情況（2）的狀態(tài)蕊梧，然后再按照其調(diào)整操作繼續(xù)進(jìn)行調(diào)整霞赫。
通過以上三個情況對紅黑樹的調(diào)整，我們可以解決紅黑樹插入紅色節(jié)點中的所有問題肥矢。
紅黑樹插入代碼實現(xiàn)：
/*********************** 向紅黑樹中插入節(jié)點 **********************/
public void insert(T key) {
RBNode<T> node = new RBNode<>(key, BLACK, null, null, null);
insert(node);
}
/**
* 1端衰、將節(jié)點插入到紅黑樹中，這個過程與二叉搜索樹是一樣的
* 2甘改、將插入的節(jié)點著色為"紅色"旅东；將插入的節(jié)點著色為紅色，不會違背"特性5"十艾！
* 少違背了一條特性抵代，意味著我們需要處理的情況越少。
* 3忘嫉、通過一系列的旋轉(zhuǎn)或者著色等操作荤牍，使之重新成為一顆紅黑樹案腺。
* @param node 插入的節(jié)點
*/
public void insert(RBNode<T> node) {
//node的父節(jié)點
RBNode<T> current = null;
RBNode<T> x = mRoot;
while (x != null) {
current = x;
int cmp = node.key.compareTo(x.key);
if (cmp < 0) {
x = x.left;
} else {
x = x.right;
}
}
//找到位置，將當(dāng)前current作為node的父節(jié)點
node.parent = current;
//2. 接下來判斷node是插在左子節(jié)點還是右子節(jié)點
if (current != null) {
int cmp = node.key.compareTo(current.key);
if (cmp < 0) {
current.left = node;
} else {
current.right = node;
}
node.color = RED;
insertFixUp(node);
} else {
this.mRoot = node;
}
}
/**
* 修改整插入node節(jié)點之后的紅黑樹
* @param node
*/
public void insertFixUp(RBNode<T> node) {
//定義父節(jié)點和祖父節(jié)點
RBNode<T> parent, gparent;
//需要修整的條件：父節(jié)點存在康吵，且父節(jié)點的顏色是紅色
while (((parent = node.parent) != null) && isRed(parent)) {
//祖父節(jié)點
gparent = parent.parent;
//若父節(jié)點是祖父節(jié)點的左子節(jié)點
if (parent == gparent.left) {
//獲取叔叔點點
RBNode<T> uncle = gparent.right;
//case1:叔叔節(jié)點是紅色
if (uncle != null && isRed(uncle)) {
//把父親和叔叔節(jié)點涂黑色
parent.color = BLACK;
uncle.color = BLACK;
//把祖父節(jié)點圖紅色
gparent.color = RED;
//將位置放到祖父節(jié)點
node = gparent;
//繼續(xù)往上循環(huán)判斷
continue;
}
//case2：叔叔節(jié)點是黑色劈榨，且當(dāng)前節(jié)點是右子節(jié)點
if (node == parent.right) {
//從父親即誒單處左旋
leftRotate(parent);
//將父節(jié)點和自己調(diào)換一下，為右旋左準(zhǔn)備
RBNode<T> tmp = parent;
parent = node;
node = tmp;
}
//case3：叔叔節(jié)點是黑色晦嵌，且當(dāng)前節(jié)點是左子節(jié)點
parent.color = BLACK;
gparent.color = RED;
rightRotate(gparent);
} else {
//若父親節(jié)點是祖父節(jié)點的右子節(jié)點同辣，與上面的完全相反，本質(zhì)一樣的
RBNode<T> uncle = gparent.left;
//case1:叔叔節(jié)點也是紅色
if (uncle != null & isRed(uncle)) {
parent.color = BLACK;
uncle.color = BLACK;
gparent.color = RED;
node = gparent;
continue;
}
//case2: 叔叔節(jié)點是黑色的耍铜，且當(dāng)前節(jié)點是左子節(jié)點
if (node == parent.left) {
rightRotate(parent);
RBNode<T> tmp = parent;
parent = node;
node = tmp;
}
//case3: 叔叔節(jié)點是黑色的邑闺，且當(dāng)前節(jié)點是右子節(jié)點
parent.color = BLACK;
gparent.color = RED;
leftRotate(gparent);
}
}
//將根節(jié)點設(shè)置為黑色
this.mRoot.color = BLACK;
}
紅黑樹節(jié)點的刪除
上面部分討論了紅黑樹添加新節(jié)點跌前，接下來的部分講述紅黑樹的刪除棕兼。紅黑樹的刪除是紅黑樹操作中最重要的部分（為什么說最重要呢？因為它最難理解）抵乓。
同樣紅黑樹的刪除是在二叉樹進(jìn)行刪除操作的基礎(chǔ)上進(jìn)行調(diào)整的伴挚，使之滿足紅黑樹的所有特性。
二叉樹知識點回憶以及整理#二叉樹節(jié)點刪除 這部分講述了二叉樹節(jié)點的添加灾炭，所以這里我們重點講述二叉樹的添加完后的調(diào)整茎芋。
二叉樹節(jié)點刪除的思路
- 如果要刪除的節(jié)點正好是葉子節(jié)點，直接刪除就 Ok 了蜈出；
- 如果要刪除的節(jié)點還有子節(jié)點田弥，就需要建立父節(jié)點和子節(jié)點的關(guān)系：
- 如果只有左孩子或者右孩子，直接把這個孩子上移放到要刪除的位置就好了铡原；
- 如果有兩個孩子偷厦，就需要選一個合適的孩子節(jié)點作為新的根節(jié)點，該節(jié)點稱為 繼承節(jié)點燕刻。（新節(jié)點要求比所有左子樹要大只泼、比右子樹要小，我們可以選擇左子樹中的最大節(jié)點卵洗，或者選擇右子樹中的最小的節(jié)點请唱。）
紅黑樹刪除總綱
我們需要在二叉樹刪除的思路上，再考慮對刪除完后的樹進(jìn)行調(diào)整过蹂。還記得文章說過
數(shù)學(xué)里最常用的一個解題技巧就是把多個未知數(shù)化解成一個未知數(shù)十绑。這句話么？二叉樹的刪除分為兩個大case或者三個小case酷勺。我們首先把這些case合并為一個case本橙，再進(jìn)行調(diào)整是不是就更加簡單來？
紅黑樹刪除之三派合并
上述將刪除的步驟總結(jié)在一下就是：
- 1鸥印、如果刪除節(jié)點的左孩子和右孩子不同時為null勋功，那么只需要讓其子樹繼承刪除該節(jié)點的位置坦报；
- 2、如果刪除的節(jié)點是葉子節(jié)點狂鞋，我們直接進(jìn)行調(diào)整片择；
- 假如刪除節(jié)點的左右孩子都不是null，需要
后繼節(jié)點替換被刪除的節(jié)點和值和顏色骚揍，這樣才不會引起紅黑樹平衡的破壞字管，只需要對后繼節(jié)點刪除后進(jìn)行調(diào)整，這樣我們就回歸處理情況 1 和 2 的狀態(tài)信不；-
后繼節(jié)點為左子樹最右邊的子葉節(jié)點 -
后繼節(jié)點為右子樹最左邊的葉子節(jié)點嘲叔；
-
如果需要刪除的節(jié)點顏色為
紅色，那么紅黑樹的結(jié)構(gòu)不被破壞抽活，也就不需要進(jìn)行調(diào)整硫戈。如果我們判斷刪除節(jié)點的顏色為黑色，那么就進(jìn)行調(diào)整下硕；
代碼以及解析：
/*********************** 刪除紅黑樹中的節(jié)點 **********************/
public void remove(T key) {
RBNode<T> node;
if ((node = search(mRoot, key)) != null) {
remove(node);
}
}
/**
* 1丁逝、被刪除的節(jié)點沒有兒子，即刪除的是葉子節(jié)點梭姓。那么霜幼，直接刪除該節(jié)點。
* 2誉尖、被刪除的節(jié)點只有一個兒子罪既。那么直接刪除該節(jié)點，并用該節(jié)點的唯一子節(jié)點頂替它的初始位置铡恕。
* 3琢感、被刪除的節(jié)點有兩個兒子。那么先找出它的后繼節(jié)點（右孩子中的最小的没咙，該孩子沒有子節(jié)點或者只有一右孩子）猩谊。
* 然后把"它的后繼節(jié)點的內(nèi)容"復(fù)制給"該節(jié)點的內(nèi)容"；之后祭刚，刪除"它的后繼節(jié)點"牌捷。
* 在這里后繼節(jié)點相當(dāng)與替身，在將后繼節(jié)點的內(nèi)容復(fù)制給"被刪除節(jié)點"之后涡驮，再將后繼節(jié)點刪除暗甥。
* ------這樣問題就轉(zhuǎn)化為怎么刪除后繼即節(jié)點的問題？
* 在"被刪除節(jié)點"有兩個非空子節(jié)點的情況下捉捅，它的后繼節(jié)點不可能是雙子都非空撤防。
* 注：后繼節(jié)點為補(bǔ)充被刪除的節(jié)點；
* 即：意味著"要么沒有兒子棒口，要么只有一個兒子"寄月。
* 若沒有兒子辜膝，則回歸到（1）。
* 若只有一個兒子漾肮，則回歸到（2）厂抖。
*
* @param node 需要刪除的節(jié)點
*/
public void remove(RBNode<T> node) {
RBNode<T> child, parent;
boolean color;
//1、刪除的節(jié)點的左右孩子都不為空
if ((node.left != null) && (node.right != null)) {
//先找到被刪除節(jié)點的后繼節(jié)點克懊，用它來取代被刪除節(jié)點的位置
RBNode<T> replace = node;
//1).獲取后繼節(jié)點[右孩子中的最小]
replace = replace.right;
while (replace.left != null) {
replace = replace.left;
}
//2).處理【后繼節(jié)點的子節(jié)點】和【被刪除節(jié)點的子節(jié)點】之間的關(guān)系
if (node.parent != null) {
//要刪除的節(jié)點不是根節(jié)點
if (node == node.parent.left) {
node.parent.left = replace;
} else {
node.parent.right = replace;
}
} else {
mRoot = replace;
}
//3).處理【后繼節(jié)點的子節(jié)點】和【被刪除節(jié)點的子節(jié)點】之間的關(guān)系
//后繼節(jié)點肯定不存在左子節(jié)點
child = replace.right;
parent = replace.parent;
//保存后繼節(jié)點的顏色
color = replace.color;
//后繼節(jié)點是被刪除的節(jié)點
if (parent == node) {
parent =replace;
} else {
if (child != null) {
child.parent = parent;
}
parent.left = child;
replace.right = node.right;
node.right.parent = replace;
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
//4忱辅。如果移走的后繼節(jié)點顏色是黑色，重新修正紅黑樹
if (color == BLACK) {
removeFixUp(child, parent);
}
node = null;
} else {
//被刪除的節(jié)點是葉子節(jié)點谭溉，或者只有一個孩子墙懂。
if (node.left != null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
//保存"取代節(jié)點"的顏色
color = node.color;
if (child != null) {
child.parent = parent;
}
//"node節(jié)點"不是根節(jié)點
if (parent != null) {
if (parent.left == node) {
parent.left = child;
} else {
parent.right = child;
}
} else {
mRoot = child;
}
if (color == BLACK) {
removeFixUp(child, parent);
}
node = null;
}
}
完成刪除操作后接下來進(jìn)行我們的調(diào)整操作，看完上面代碼后我們知道調(diào)整時需要傳遞的參數(shù)是后繼節(jié)點和刪除的父節(jié)點扮念。
紅黑樹刪除之節(jié)點調(diào)整
刪除后那么后繼節(jié)點就成才刪除節(jié)點的孩子损搬，那么接下的過程中我們將后繼節(jié)點定義目標(biāo)節(jié)點。
下邊我們討論一下節(jié)點的顏色情況：因為當(dāng)前節(jié)點的顏色一定是黑色的扔亥，我們只根據(jù)兄弟節(jié)點的顏色做討論场躯。
- 1谈为、當(dāng)前節(jié)點是黑色的旅挤，且兄弟節(jié)點是紅色的（那么父節(jié)點和兄弟節(jié)點的子節(jié)點肯定是黑色的）；
- 2伞鲫、當(dāng)前節(jié)點是黑色的粘茄，且兄弟節(jié)點是黑色的，
- 1）秕脓、兄弟節(jié)點的兩個子節(jié)點均為黑色的柒瓣；
- 2）、兄弟節(jié)點的左子節(jié)點是紅色吠架，右子節(jié)點時黑色的芙贫；
- 3）、兄弟節(jié)點的右子節(jié)點是紅色傍药，左子節(jié)點任意顏色磺平；
調(diào)整情況（1）:當(dāng)前節(jié)點是黑色的，且兄弟節(jié)點是紅色的
下圖是這樣情況的紅黑樹的修改過程：
- 將父節(jié)點涂紅拐辽，將兄弟節(jié)點涂黑拣挪，然后將當(dāng)前節(jié)點的父節(jié)點進(jìn)行支點左旋。這樣就會轉(zhuǎn)化為情況2中的某種狀態(tài)俱诸。
調(diào)整情況（2）:當(dāng)前節(jié)點是黑色的菠劝，且兄弟節(jié)點是黑色的
2.1、兄弟節(jié)點的左子節(jié)點是紅色睁搭，右子節(jié)點時黑色的赶诊；
下圖是這樣情況的紅黑樹的修改過程：
- 將兄弟節(jié)點涂紅笼平，將當(dāng)前節(jié)點指向其父節(jié)點，將其父節(jié)點指向當(dāng)前節(jié)點的祖父節(jié)點舔痪，繼續(xù)往樹根遞歸判斷以及調(diào)整出吹；
2.2、兄弟節(jié)點的兩個子節(jié)點均為黑色的辙喂；
下圖是這樣情況的紅黑樹的修改過程：
- 把當(dāng)前節(jié)點的兄弟節(jié)點涂紅捶牢，把兄弟節(jié)點的左子節(jié)點涂黑，然后以兄弟節(jié)點作為支點做右旋操作巍耗。
2.3秋麸、兄弟節(jié)點的右子節(jié)點是紅色，左子節(jié)點任意顏色炬太；
下圖是這樣情況的紅黑樹的修改過程：
- 把兄弟節(jié)點涂成父節(jié)點的顏色灸蟆，再把父節(jié)點涂黑，把兄弟節(jié)點的右子節(jié)點涂黑亲族，然后以當(dāng)前節(jié)點的父節(jié)點為支點做左旋操作炒考。
紅黑樹刪除調(diào)整case總結(jié)&代碼實現(xiàn)
如果是從case:1開始發(fā)生的，可能case:2霎迫，3斋枢，4中的一種：如果是case:2，就不可能再出現(xiàn)case:3和4知给；如果是case:3瓤帚，必然會導(dǎo)致case:4的出現(xiàn)；如果case:2和3都不是涩赢，那必然是case:4戈次。
/**
* 紅黑樹刪除修正函數(shù)
*
* 在從紅黑樹中刪除插入節(jié)點之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)筒扒；
* 目的是將它重新塑造成一顆紅黑樹怯邪。
* 如果當(dāng)前待刪除節(jié)點是紅色的，它被刪除之后對當(dāng)前樹的特性不會造成任何破壞影響花墩。
* 而如果被刪除的節(jié)點是黑色的悬秉，這就需要進(jìn)行進(jìn)一步的調(diào)整來保證后續(xù)的樹結(jié)構(gòu)滿足要求。
* 這里我們只修正刪除的節(jié)點是黑色的情況：
*
* 調(diào)整思想：
* 為了保證刪除節(jié)點的父節(jié)點左右兩邊黑色節(jié)點數(shù)一致观游，需要重點關(guān)注父節(jié)點沒刪除的那一邊節(jié)點是不是黑色搂捧。
* 如果刪除后父親節(jié)點另一邊比刪除的一邊黑色多，就要想辦法搞到平衡懂缕。
* 1允跑、把父親節(jié)點另一邊（即刪除節(jié)點的兄弟樹）其中一個節(jié)點弄成紅色，也少了一個黑色。
* 2聋丝、或者把另一邊多的節(jié)點（染成黑色）轉(zhuǎn)過來一個
*
* 1）索烹、當(dāng)前節(jié)點是黑色的，且兄弟節(jié)點是紅色的（那么父節(jié)點和兄弟節(jié)點的子節(jié)點肯定是黑色的）弱睦；
* 2）百姓、當(dāng)前節(jié)點是黑色的，且兄弟節(jié)點是黑色的况木，且兄弟節(jié)點的兩個子節(jié)點均為黑色的垒拢；
* 3）、當(dāng)前節(jié)點是黑色的火惊，且兄弟節(jié)點是黑色的求类，且兄弟節(jié)點的左子節(jié)點是紅色，右子節(jié)點時黑色的屹耐；
* 4）尸疆、當(dāng)前節(jié)點是黑色的，且兄弟節(jié)點是黑色的惶岭，且兄弟節(jié)點的右子節(jié)點是紅色寿弱，左子節(jié)點任意顏色。
*
* 以上四種情況中按灶，2症革，3，4都是（當(dāng)前節(jié)點是黑色的兆衅，且兄弟節(jié)點是黑色的）的子集地沮。
*
* 參數(shù)說明：
* @param node 刪除之后代替的節(jié)點（后序節(jié)點）
* @param parent 后序節(jié)點的父節(jié)點
*/
private void removeFixUp(RBNode<T> node, RBNode<T> parent) {
RBNode<T> other;
RBNode<T> root = mRoot;
while ((node == null || node.color == BLACK) && node != root) {
if (parent.left == node) {
other = parent.right;
if (other.color == RED) {
//case 1：x的兄弟w是紅色的【對應(yīng)狀態(tài)1，將其轉(zhuǎn)化為2羡亩，3，4】
other.color = BLACK;
parent.color = RED;
leftRotate(parent);
other = parent.right;
}
if ((other.left == null || other.left.color == BLACK)
&& (other.right == null || other.right.color == BLACK)) {
//case 2：x的兄弟w是黑色危融，且w的兩個孩子都是黑色的【對應(yīng)狀態(tài)2畏铆，利用調(diào)整思想1網(wǎng)樹的根部做遞歸】
other.color = RED;
node = parent;
parent = node.parent;
} else {
if (other.right == null || other.right.color == BLACK) {
//case 3:x的兄弟w是黑色的，并且w的左孩子是紅色的吉殃，右孩子是黑色的【對應(yīng)狀態(tài)3辞居，調(diào)整到狀態(tài)4】
other.left.color = BLACK;
other.color = RED;
rightRotate(other);
other = parent.right;
}
//case 4:x的兄弟w是黑色的；并且w的右孩子是紅色的蛋勺，左孩子任意顏色【對應(yīng)狀態(tài)4瓦灶，利用調(diào)整思想2做調(diào)整】
other.color = parent.color;
parent.color = BLACK;
other.right.color = BLACK;
leftRotate(parent);
node = root;
break;
}
} else {
other = parent.left;
if (other.color == RED) {
//case 1:x的兄弟w是紅色的
other.color = BLACK;
parent.color = RED;
rightRotate(parent);
other = parent.left;
}
if ((other.left == null || other.left.color == BLACK)
&& (other.right == null || other.right.color == BLACK)) {
//case 2:x兄弟w是黑色，且w的兩個孩子也都是黑色的
other.color = RED;
node = parent;
parent = node.parent;
} else {
if (other.left == null || other.left.color == BLACK) {
//case 3:x的兄弟w是黑色的抱完，并且w的左孩子是紅色贼陶，右孩子為黑色。
other.right.color = BLACK;
other.color = RED;
leftRotate(other);
other = parent.left;
}
//case 4:x的兄弟w是黑色的；并且w的右孩子是紅色的碉怔，左孩子任意顏色烘贴。
other.color = parent.color;
parent.color = BLACK;
other.left.color = BLACK;
rightRotate(parent);
node = root;
break;
}
}
}
if (node != null) {
node.color = BLACK;
}
}
總結(jié)
紅黑樹查找的最壞時間復(fù)雜度也是O(logN)。為了它這么高的性能撮胧，我感覺自己費(fèi)了這么多腦細(xì)胞和時間來學(xué)習(xí)也是值得的(自己前前后后看了好多次)桨踪。這篇文章和插入圖也是我自己用心根據(jù)自己的理解來做，希望大家能在學(xué)習(xí)紅黑樹的時候提高效率芹啥，不走彎路锻离。
參考文章
紅黑樹的文章有好多，仔細(xì)閱讀幾篇之后感覺這三篇講的不錯墓怀。第一篇的紅黑樹插入纳账，第二篇的紅黑樹左旋和右旋（動畫做的非常好）和紅黑樹的刪除，最后一篇的代碼寫的很棒并且提供的測試的case捺疼。文章的主要內(nèi)容都是以下三篇文章的總結(jié)疏虫。
重溫數(shù)據(jù)結(jié)構(gòu)：深入理解紅黑樹
【數(shù)據(jù)結(jié)構(gòu)和算法05】 紅-黑樹（看完包懂~）
紅黑樹(五)之 Java的實現(xiàn)
源碼：紅黑樹操作&代碼注釋
文章到這里就全部講述完啦，若有其他需要交流的可以留言哦~啤呼！~灶壶！
