最近和朋友聊TreeMap峦筒、HashMap筝蚕、ConcurrentHashMap的底層原理時(shí)，都知道用到了紅黑樹饺饭，但紅黑樹到底是一個(gè)什么樣子的算法渤早，我們卻并不清楚。
今天簡單總結(jié)下這個(gè)算法的原理瘫俊，因?yàn)榫W(wǎng)上相關(guān)的文章已經(jīng)很多鹊杖，本文就不再贅述了。
直接在我覺得講解的最透徹的文章上做些總結(jié)擴(kuò)展：
紅黑樹(一)之 原理和算法詳細(xì)介紹
PS：這篇文章思路和原理是講的特別清楚的扛芽，但遺憾的是骂蓖，配圖是錯(cuò)誤的；另外刪除節(jié)點(diǎn)部分個(gè)人覺得講解的不太清晰川尖。這兩個(gè)問題導(dǎo)致我思考時(shí)走了很大彎路登下。大家可以以這篇文章為主，參考我的總結(jié)來看叮喳，可能會(huì)好些
1. 紅黑樹概述
二叉查找樹
左節(jié)點(diǎn)key < 其根節(jié)點(diǎn)key < 右節(jié)點(diǎn)key平衡二叉樹
平衡二叉樹是對(duì) 二叉查找樹的一種優(yōu)化被芳，規(guī)定左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，這樣便提高了查找的效率馍悟。紅黑樹
紅黑樹是 “平衡二叉樹” 的一種實(shí)現(xiàn)算法畔濒。
紅黑樹的特性：
- 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色
- 根節(jié)點(diǎn)是黑色
- 每個(gè)葉子結(jié)點(diǎn)（NIL锣咒，這里的葉子結(jié)點(diǎn)不是傳統(tǒng)的葉子結(jié)點(diǎn)侵状，是指為空的葉子結(jié)點(diǎn)）是黑色。
- 如果一個(gè)結(jié)點(diǎn)是紅色的毅整，則它的子結(jié)點(diǎn)必須是黑色的
- 從一個(gè)結(jié)點(diǎn)到該結(jié)點(diǎn)的子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)壹将。
這些特性一眼看上去好像不知所云。不要急毛嫉，這里我們只需大致明白：紅黑樹就是利用紅诽俯、黑節(jié)點(diǎn)接近均勻分布（特性4），而每條路徑的黑節(jié)點(diǎn)數(shù)目一樣（特性5）來做到 左右兩子樹 高度差<=1
2. 算法實(shí)現(xiàn)
2.1 左右旋
紅黑樹左右旋的目的在于，在插入暴区、刪除節(jié)點(diǎn)后闯团，重新調(diào)整紅黑節(jié)點(diǎn)的位置，使其滿足紅黑樹特性仙粱。
-
左旋：
將節(jié)點(diǎn)繞其右子節(jié)點(diǎn)房交，向左進(jìn)行旋轉(zhuǎn)，使右子節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)：
-
右旋：
將節(jié)點(diǎn)繞其左子節(jié)點(diǎn)伐割，向右進(jìn)行旋轉(zhuǎn)候味，使左子節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)（注意圖的箭頭方向是相反的）：
2.2 插入
插入分為兩步
插入第一步：
將紅黑樹當(dāng)作一顆二叉查找樹隔心，將節(jié)點(diǎn)添加到二叉查找樹中。注意，節(jié)點(diǎn)為紅色，這是為了防止父節(jié)點(diǎn)為紅色，導(dǎo)致違反特性4
/*
* 將結(jié)點(diǎn)插入到紅黑樹中
*
* 參數(shù)說明：
* node 插入的結(jié)點(diǎn) // 對(duì)應(yīng)《算法導(dǎo)論》中的node
*/
private void insert(RBTNode<T> node) {
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.mRoot;
// 1. 將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點(diǎn)添加到二叉查找樹中。
while (x != null) {
y = x;
cmp = node.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y!=null) {
cmp = node.key.compareTo(y.key);
if (cmp < 0)
y.left = node;
else
y.right = node;
} else {
this.mRoot = node;
}
// 2. 設(shè)置節(jié)點(diǎn)的顏色為紅色
node.color = RED;
// 3. 將它重新修正為一顆二叉查找樹
insertFixUp(node);
}
插入第二步：
重新調(diào)整紅黑樹谤牡，使新插入的節(jié)點(diǎn)不破壞紅黑樹特性：
插入調(diào)整分三種情況：
（1. 插入的為根節(jié)點(diǎn)，直接節(jié)點(diǎn)顏色改為黑色
（2. 被插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色。不用作改變
（3. 被插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色節(jié)點(diǎn)，這種情況最復(fù)雜，分場景解決：
這三種場景的處理策略都是為了：將不合規(guī)的紅色節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn)，然后將根節(jié)點(diǎn)設(shè)為黑色。
下面將紅黑樹(一)之 原理和算法詳細(xì)介紹中的圖修正逛尚，來過一遍情況3的三種插入場景：
對(duì)已存在 [80, 40, 120, 20, 60, 50, 70, 140] 節(jié)點(diǎn)的紅黑樹插入一個(gè) 45的節(jié)點(diǎn)
-
Case 1：調(diào)整的目的為了將紅色節(jié)點(diǎn)上移吮便，上移后若新的當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)房蝉，則紅黑樹合規(guī)：
image.png -
Case 2：將父節(jié)點(diǎn)左旋的目的在于檀蹋，使當(dāng)前節(jié)點(diǎn)的紅色上移焕数。上移后若當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，則紅黑樹合規(guī)。牢記我們的處理策略：將不合規(guī)的紅色節(jié)點(diǎn)上移到根節(jié)點(diǎn)
上移成功后耀盗，再以父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的原因是舌厨，從下至上解決不合規(guī)問題。
-
Case 3：這種情況的處理邏輯是忿薇，父節(jié)點(diǎn)變黑——》分支紅色 -1裙椭，為補(bǔ)償令 祖父節(jié)點(diǎn)變紅 ——》分支紅色 +1 。
最后讓祖父節(jié)點(diǎn)右旋署浩，使得父節(jié)點(diǎn)（黑 60）變成了當(dāng)前節(jié)點(diǎn)（紅 40）和祖父節(jié)點(diǎn)（紅 80）的父節(jié)點(diǎn)揉燃，紅黑樹合規(guī)。
/*
* 紅黑樹插入修正函數(shù)
*
* 在向紅黑樹中插入節(jié)點(diǎn)之后(失去平衡)筋栋，再調(diào)用該函數(shù)你雌；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 插入的結(jié)點(diǎn) // 對(duì)應(yīng)《算法導(dǎo)論》中的z
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父節(jié)點(diǎn)存在二汛，并且父節(jié)點(diǎn)的顏色是紅色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節(jié)點(diǎn)”是“祖父節(jié)點(diǎn)的左孩子”
if (parent == gparent.left) {
// Case 1條件：叔叔節(jié)點(diǎn)是紅色
RBTNode<T> uncle = gparent.right;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色婿崭，且當(dāng)前節(jié)點(diǎn)是右孩子
if (parent.right == node) {
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子肴颊。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父節(jié)點(diǎn)”是“z的祖父節(jié)點(diǎn)的右孩子”
// Case 1條件：叔叔節(jié)點(diǎn)是紅色
RBTNode<T> uncle = gparent.left;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色氓栈，且當(dāng)前節(jié)點(diǎn)是左孩子
if (parent.left == node) {
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子婿着。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 將根節(jié)點(diǎn)設(shè)為黑色
setBlack(this.mRoot);
}
2.3 刪除
刪除也分為兩步
刪除第一步：
將紅黑樹當(dāng)作一顆二叉查找樹授瘦，將節(jié)點(diǎn)刪除：
- 若被刪節(jié)點(diǎn) 沒有子節(jié)點(diǎn)醋界，則不做處理；
- 若子節(jié)點(diǎn)有一個(gè)提完，則將子節(jié)點(diǎn)取代被刪除節(jié)點(diǎn)形纺；
- 若子節(jié)點(diǎn)有2個(gè)，則找到后繼節(jié)點(diǎn)或先驅(qū)節(jié)點(diǎn)取代該節(jié)點(diǎn)徒欣。（后繼節(jié)點(diǎn)即右子樹的最小節(jié)點(diǎn)逐样，前驅(qū)節(jié)點(diǎn)為左子樹的最大節(jié)點(diǎn)）
/*
* 刪除結(jié)點(diǎn)(node)，并返回被刪除的結(jié)點(diǎn)
*
* 參數(shù)說明：
* node 刪除的結(jié)點(diǎn)
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被刪除節(jié)點(diǎn)的"左右孩子都不為空"的情況打肝。
if ( (node.left!=null) && (node.right!=null) ) {
// 被刪節(jié)點(diǎn)的后繼節(jié)點(diǎn)脂新。(稱為"取代節(jié)點(diǎn)")
// 用它來取代"被刪節(jié)點(diǎn)"的位置，然后再將"被刪節(jié)點(diǎn)"去掉粗梭。
RBTNode<T> replace = node;
// 獲取后繼節(jié)點(diǎn)
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// "node節(jié)點(diǎn)"不是根節(jié)點(diǎn)(只有根節(jié)點(diǎn)不存在父節(jié)點(diǎn))
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else {
// "node節(jié)點(diǎn)"是根節(jié)點(diǎn)争便，更新根節(jié)點(diǎn)。
this.mRoot = replace;
}
// child是"取代節(jié)點(diǎn)"的右孩子断医，也是需要"調(diào)整的節(jié)點(diǎn)"滞乙。
// "取代節(jié)點(diǎn)"肯定不存在左孩子！因?yàn)樗且粋€(gè)后繼節(jié)點(diǎn)鉴嗤。
child = replace.right;
parent = parentOf(replace);
// 保存"取代節(jié)點(diǎn)"的顏色
color = colorOf(replace);
// "被刪除節(jié)點(diǎn)"是"它的后繼節(jié)點(diǎn)的父節(jié)點(diǎn)"
if (parent == node) {
parent = replace;
} else {
// child不為空
if (child!=null)
setParent(child, parent);
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
if (color == BLACK)
removeFixUp(child, parent);
node = null;
return ;
}
if (node.left !=null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
// 保存"取代節(jié)點(diǎn)"的顏色
color = node.color;
if (child!=null)
child.parent = parent;
// "node節(jié)點(diǎn)"不是根節(jié)點(diǎn)
if (parent!=null) {
if (parent.left == node)
parent.left = child;
else
parent.right = child;
} else {
this.mRoot = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
刪除第二步：
對(duì)于 3 的情況斩启，如果用后繼節(jié)點(diǎn)或前驅(qū)節(jié)點(diǎn)替換了刪除節(jié)點(diǎn)，則可視為刪除的節(jié)點(diǎn)為替換的后繼節(jié)點(diǎn)或前驅(qū)節(jié)點(diǎn)躬窜。
如下圖浇垦，原刪除節(jié)點(diǎn) 60 被后繼節(jié)點(diǎn) 70 “替換”炕置，可看成 “真實(shí)的刪除節(jié)點(diǎn)” 為 后繼節(jié)點(diǎn) 70
接下來討論下刪除后繼節(jié)點(diǎn)的處理：
- 后繼節(jié)點(diǎn)只會(huì)有0個(gè)子節(jié)點(diǎn)荣挨，或一個(gè)右子節(jié)點(diǎn)。
- 如果被刪除的后繼節(jié)點(diǎn)y為紅色朴摊，則不會(huì)影響到紅黑樹默垄。若后繼節(jié)點(diǎn)沒有子節(jié)點(diǎn)，則不作處理甚纲。若有右子節(jié)點(diǎn)x口锭，則直接用子節(jié)點(diǎn)x替換即可。
- 如果被刪除的后繼節(jié)點(diǎn)y為黑色介杆。若后繼節(jié)點(diǎn)沒有子節(jié)點(diǎn)鹃操，則不作處理。若有右子節(jié)點(diǎn)x春哨，則特性5可能被破壞（該分支少了一個(gè)黑色）荆隘，需要對(duì)紅黑樹進(jìn)行重新調(diào)整，使其不破壞紅黑樹特性赴背。
調(diào)整策略如下：
將被刪除的后繼節(jié)點(diǎn)的黑顏色放到其右子節(jié)點(diǎn)x中椰拒。即右子節(jié)點(diǎn)x 顏色為 “紅+黑” 或 “黑+黑” 晶渠。然后將x多余的顏色想辦法移動(dòng)到根節(jié)點(diǎn)，則紅黑樹特性不會(huì)被破壞燃观。
這種調(diào)整策略褒脯，又可以概括為3種情況：
① 情況說明：x是“紅+黑”節(jié)點(diǎn)。
處理方法：直接把x設(shè)為黑色缆毁，結(jié)束番川。此時(shí)紅黑樹性質(zhì)全部恢復(fù)。
② 情況說明：x是“黑+黑”節(jié)點(diǎn)积锅，且x是根爽彤。
處理方法：什么都不做，結(jié)束缚陷。此時(shí)紅黑樹性質(zhì)全部恢復(fù)适篙。
③ 情況說明：x是“黑+黑”節(jié)點(diǎn)，且x不是根箫爷。
處理方法：這種情況又可以劃分為4種子情況嚷节。這4種子情況如下表所示：
/*
* 紅黑樹刪除修正函數(shù)
*
* 在從紅黑樹中刪除插入節(jié)點(diǎn)之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)虎锚；
* 目的是將它重新塑造成一顆紅黑樹硫痰。
*
* 參數(shù)說明：
* node 待修正的節(jié)點(diǎn)
*/
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
RBTNode<T> other;
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的倆個(gè)孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的窜护，并且w的左孩子是紅色效斑，右孩子為黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的柱徙；并且w的右孩子是紅色的缓屠，左孩子任意顏色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色护侮，且w的倆個(gè)孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的敌完，并且w的左孩子是紅色，右孩子為黑色羊初。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的滨溉；并且w的右孩子是紅色的，左孩子任意顏色长赞。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
if (node!=null)
setBlack(node);
}
3. Java集合中的使用
Java集合中晦攒，TreeMap和TreeSet都是有序的，它們其實(shí)就是用紅黑樹實(shí)現(xiàn)得哆。
另外脯颜，HashMap和ConcurrentHashMap也使用了紅黑樹結(jié)構(gòu)進(jìn)行優(yōu)化，當(dāng)hash沖突的鏈表個(gè)數(shù)達(dá)到8時(shí)柳恐，為了查詢優(yōu)化伐脖，會(huì)將鏈表改為紅黑樹
