1.定義
紅黑樹是特殊的二叉查找樹，又名R-B樹(RED-BLACK-TREE)，由于紅黑樹是特殊的二叉查找樹，即紅黑樹具有了二叉查找樹的特性，而且紅黑樹還具有以下特性：
1.每個節(jié)點要么是黑色要么是紅色
2.根節(jié)點是黑色
3.每個葉子節(jié)點是黑色圈膏，并且為空節(jié)點(還有另外一種說法就是，每個葉子結點都帶有兩個空的黑色結點（被稱為黑哨兵）浆熔，如果一個結點n的只有一個左孩子本辐，那么n的右孩子是一個黑哨兵；如果結點n只有一個右孩子医增，那么n的左孩子是一個黑哨兵慎皱。)
4.如果一個節(jié)點是紅色，則它的子節(jié)點必須是黑色
5.從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點叶骨。
有幾點需要注意的是：
1.特性3中指定紅黑樹的每個葉子節(jié)點都是空節(jié)點茫多，但是在Java實現(xiàn)中紅黑樹將使用null代表空節(jié)點，因此遍歷紅黑樹時看不到黑色的葉子節(jié)點忽刽，反而見到的葉子節(jié)點是紅色的
2.特性4保證了從根節(jié)點到葉子節(jié)點的最長路徑的長度不會超過任何其他路徑的兩倍天揖，例如黑色高度為3的紅黑樹夺欲，其最短路徑(路徑指的是根節(jié)點到葉子節(jié)點)是2(黑節(jié)點-黑節(jié)點-黑節(jié)點)，其最長路徑為4(黑節(jié)點-紅節(jié)點-黑節(jié)點-紅節(jié)點-黑節(jié)點)今膊。
2.實踐
2.1 紅黑樹操作
2.1.1 插入操作
首先紅黑樹在插入節(jié)點的時些阅，我們設定插入節(jié)點的顏色為紅色,如果插入的是黑色節(jié)點，必然會違背特性5斑唬，即改變了紅黑樹的黑高度市埋，如下插入紅色結點又存在著幾種情況：
1.黑父
如圖所示，這種情況不會破壞紅黑樹的特性恕刘，即不需要任何處理
2.紅父
當其父親為紅色時又會存在以下的情況
- 紅叔
紅叔的情況缤谎，其實相對來說比較簡單的，如下圖所示褐着，只需要通過修改父坷澡、叔的顏色為黑色，祖的顏色為紅色含蓉，而且回去遞歸的檢查祖節(jié)點即可
- 黑叔
黑叔的情況有如下幾種频敛，這幾種情況下是不能夠通過修改顏色達到平衡的效果，因此會通過旋轉的操作谴餐，紅黑樹種有兩種旋轉操作姻政，左旋和右旋(現(xiàn)在存在的疑問，什么時候使用到左旋岂嗓，什么時候使用到右旋)
-
Case 1:[先右旋，在改變顏色(根節(jié)點必須為黑色鹊碍，其兩個子節(jié)點為紅色厌殉，叔節(jié)點不用改變)],如下圖所示，注意省略黑哨兵節(jié)點
image -
Case 2:[先左旋變成Case1中的情況侈咕，再右旋公罕，最后改變顏色(根節(jié)點必須為黑色，其兩個子節(jié)點為紅色耀销，叔節(jié)點不用改變)],如下圖所示楼眷，注意省略黑哨兵節(jié)點
image -
Case 3:[先左旋，最后改變顏色(根節(jié)點必須為黑色熊尉，其兩個子節(jié)點為紅色罐柳，叔節(jié)點不用改變)],如下圖所示，注意省略黑哨兵節(jié)點
image -
Case 4:[先右旋變成Case 3的情況狰住，再左旋张吉，最后改變顏色(根節(jié)點必須為黑色，其兩個子節(jié)點為紅色催植，叔節(jié)點不用改變)],如下圖所示肮蛹，注意省略黑哨兵節(jié)點
image
以上就是紅黑樹新增節(jié)點所有可能的操作勺择，下面會介紹紅黑樹中的刪除操作
2.1.2 刪除操作
刪除操作相比于插入操作情況更加復雜，刪除一個節(jié)點可以大致分為三種情況：
1.刪除的節(jié)點沒有孩子節(jié)點伦忠，即當前節(jié)點為葉子節(jié)點省核，這種可以直接刪除
2.刪除的節(jié)點有一個孩子節(jié)點，這種需要刪除當前節(jié)點昆码，并使用其孩子節(jié)點頂替上來
3.刪除的節(jié)點有兩個孩子節(jié)點气忠，這種需要先找到其后繼節(jié)點(樹中大于節(jié)點的最小的元素);然后將其后繼節(jié)點的內容復制到該節(jié)點上，其后繼節(jié)點就相當于該節(jié)點的替身未桥， 需要注意的是其后繼節(jié)點一定不會有兩個孩子節(jié)點(這點應該很好理解笔刹，如果后繼節(jié)點有左孩子節(jié)點，那么當前的后繼節(jié)點肯定不是最小的冬耿，說明后繼節(jié)點只能存在沒有孩子節(jié)點或者只有一個右孩子節(jié)點)舌菜，即這樣就將問題轉換成為1,2中的方式。
在講述修復操作之前亦镶，首先需要明白幾點日月，
1.對于紅黑樹而言，單支節(jié)點的情況只有如下圖所示的一種情況缤骨，即為當前節(jié)點為黑色爱咬，其孩子節(jié)點為紅色,(1.假設當前節(jié)點為紅色，其兩個孩子節(jié)點必須為黑色绊起，2.若有孫子節(jié)點精拟，則必為黑色，導致黑子數(shù)量不等虱歪，而紅黑樹不平衡)
2.由于紅黑樹是特殊的二叉查找樹蜂绎，它的刪除和二叉查找樹類型，真正的刪除點即為刪除點A的中序遍歷的后繼(前繼也可以)笋鄙，通過紅黑樹的特性可知這個后繼必然最多只能有一個孩子师枣，其這個孩子節(jié)點必然是右孩子節(jié)點，從而為單支情況(即這個后繼節(jié)點只能有一個紅色孩子或沒有孩子)
下面將詳細介紹萧落，在執(zhí)行刪除節(jié)點操作之后践美，將通過修復操作使得紅黑樹達到平衡的情況。
- Case 1:被刪除的節(jié)點為紅色找岖，則這節(jié)點必定為葉子節(jié)點(首先這里的被刪除的節(jié)點指的是真正刪除的節(jié)點陨倡，通過上文得知的真正刪除的節(jié)點要么是節(jié)點本身，要么是其后繼節(jié)點宣增，若是節(jié)點本身則必須為葉子節(jié)點玫膀，不為葉子節(jié)點的話其會有左右孩子，則真正刪除的是其右孩子樹上的最小值爹脾，若是后繼節(jié)點帖旨，也必須為葉子節(jié)點箕昭，若不是則其也會有左右孩子，從而和2中相違背)解阅，這種情況下刪除紅色葉節(jié)點就可以了落竹，不用進行其他的操作了。
- Case 2:被刪除的節(jié)點是黑色货抄，其子節(jié)點是紅色述召，將其子節(jié)點頂替上來并改變其顏色為黑色，如下圖所示
-
Case 3:被刪除的節(jié)點是黑色蟹地，其子節(jié)點也是黑色积暖，將其子節(jié)點頂替上來，變成了雙黑的問題怪与，此時有以下情況
- Case 1:新節(jié)點的兄弟節(jié)點為紅色夺刑，此時若新節(jié)點在左邊則做左旋操作，否則做右旋操作分别，之后再將其父節(jié)點顏色改變?yōu)榧t色遍愿，兄弟節(jié)點
image
image從圖中可以看出，操作之后紅黑樹并未達到平衡狀態(tài)耘斩，而是變成的黑兄的情況
-
Case 2:新節(jié)點的兄弟節(jié)點為黑色,此時可能有如下情況
- 紅父二黑侄：將父節(jié)點變成黑色沼填，兄弟節(jié)點變成紅色，新節(jié)點變成黑色即可,如下圖所示
imageimage-
黑父二黑侄：將父節(jié)點變成新節(jié)點的顏色括授，新節(jié)點變成黑色坞笙，兄弟節(jié)點染成紅色，還需要繼續(xù)以父節(jié)點為判定點繼續(xù)判斷,如下圖所示
image
image- 紅侄：
情況一:新節(jié)點在右子樹荚虚，紅侄在兄弟節(jié)點左子樹羞海，此時的操作為右旋，并將兄弟節(jié)點變?yōu)楦赣H的顏色曲管，父親節(jié)點變?yōu)楹谏豆?jié)點變?yōu)楹谏逗缦聢D所示
image情況二:新節(jié)點在右子樹院水，紅侄在兄弟節(jié)點右子樹，此時的操作為先左旋简十，后右旋并將侄節(jié)點變?yōu)楦赣H的顏色檬某，父節(jié)點變?yōu)楹谏缦聢D所示
image情況三：新節(jié)點在左子樹螟蝙，紅侄在兄弟節(jié)點左子樹,此時的操作為先右旋在左旋并將侄節(jié)點變?yōu)楦赣H的顏色恢恼，父親節(jié)點變?yōu)楹谏缦聢D所示
image情況四：新節(jié)點在右子樹胰默，紅侄在兄弟節(jié)點右子樹,此時的操作為左旋场斑，并將兄弟節(jié)點變?yōu)楦腹?jié)點的顏色漓踢，父親節(jié)點變?yōu)楹谏豆?jié)點變?yōu)楹谏┮缦聢D所示
image
- Case 1:新節(jié)點的兄弟節(jié)點為紅色夺刑，此時若新節(jié)點在左邊則做左旋操作，否則做右旋操作分别，之后再將其父節(jié)點顏色改變?yōu)榧t色遍愿，兄弟節(jié)點
2.2 紅黑樹實現(xiàn)
如下是使用JAVA代碼實現(xiàn)紅黑樹的過程喧半，主要包括了插入、刪除青责、左旋挺据、右旋、遍歷等操作
2.2.1 插入
/* 插入一個節(jié)點
* @param node
*/
private void insert(RBTreeNode<T> node){
int cmp;
RBTreeNode<T> root = this.rootNode;
RBTreeNode<T> parent = null;
//定位節(jié)點添加到哪個父節(jié)點下
while(null != root){
parent = root;
cmp = node.key.compareTo(root.key);
if (cmp < 0){
root = root.left;
} else {
root = root.right;
}
}
node.parent = parent;
//表示當前沒一個節(jié)點脖隶，那么就當新增的節(jié)點為根節(jié)點
if (null == parent){
this.rootNode = node;
} else {
//找出在當前父節(jié)點下新增節(jié)點的位置
cmp = node.key.compareTo(parent.key);
if (cmp < 0){
parent.left = node;
} else {
parent.right = node;
}
}
//設置插入節(jié)點的顏色為紅色
node.color = COLOR_RED;
//修正為紅黑樹
insertFixUp(node);
}
/**
* 紅黑樹插入修正
* @param node
*/
private void insertFixUp(RBTreeNode<T> node){
RBTreeNode<T> parent,gparent;
//節(jié)點的父節(jié)點存在并且為紅色
while( ((parent = getParent(node)) != null) && isRed(parent)){
gparent = getParent(parent);
//如果其祖父節(jié)點是空怎么處理
// 若父節(jié)點是祖父節(jié)點的左孩子
if(parent == gparent.left){
RBTreeNode<T> uncle = gparent.right;
if ((null != uncle) && isRed(uncle)){
setColorBlack(uncle);
setColorBlack(parent);
setColorRed(gparent);
node = gparent;
continue;
}
if (parent.right == node){
RBTreeNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
setColorBlack(parent);
setColorRed(gparent);
rightRotate(gparent);
} else {
RBTreeNode<T> uncle = gparent.left;
if ((null != uncle) && isRed(uncle)){
setColorBlack(uncle);
setColorBlack(parent);
setColorRed(gparent);
node = gparent;
continue;
}
if (parent.left == node){
RBTreeNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
setColorBlack(parent);
setColorRed(gparent);
leftRotate(gparent);
}
}
setColorBlack(this.rootNode);
}
插入節(jié)點的操作主要分為以下幾步：
1.定位：即遍歷整理紅黑樹扁耐，確定添加的位置，如上代碼中insert方法中就是在找到添加的位置
2.修復：這也就是前面介紹的产阱，添加元素后可能會使得紅黑樹不在滿足其特性婉称，這時候需要通過變色、旋轉來調整紅黑樹心墅，也就是如上代碼中insertFixUp方法
2.2.2 刪除節(jié)點
如下為刪除節(jié)點的代碼
private void remove(RBTreeNode<T> node){
RBTreeNode<T> child,parent;
boolean color;
//被刪除節(jié)點左右孩子都不為空的情況
if ((null != node.left) && (null != node.right)){
//獲取到被刪除節(jié)點的后繼節(jié)點
RBTreeNode<T> replace = node;
replace = replace.right;
while(null != replace.left){
replace = replace.left;
}
//node節(jié)點不是根節(jié)點
if (null != getParent(node)){
//node是左節(jié)點
if (getParent(node).left == node){
getParent(node).left = replace;
} else {
getParent(node).right = replace;
}
} else {
this.rootNode = replace;
}
child = replace.right;
parent = getParent(replace);
color = getColor(replace);
if (parent == node){
parent = replace;
} else {
if (null != child){
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 == COLOR_BLACK){
removeFixUp(child,parent);
}
node = null;
return;
}
if (null != node.left){
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
color = node.color;
if (null != child){
child.parent = parent;
}
if (null != parent){
if (parent.left == node){
parent.left = child;
} else {
parent.right = child;
}
} else {
this.rootNode = child;
}
if (color == COLOR_BLACK){
removeFixUp(child, parent);
}
node = null;
}
/**
* 刪除修復
* @param node
* @param parent
*/
private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent){
RBTreeNode<T> other;
//node不為空且為黑色酿矢，并且不為根節(jié)點
while ((null == node || isBlack(node)) && (node != this.rootNode) ){
//node是父節(jié)點的左孩子
if (node == parent.left){
//獲取到其右孩子
other = parent.right;
//node節(jié)點的兄弟節(jié)點是紅色
if (isRed(other)){
setColorBlack(other);
setColorRed(parent);
leftRotate(parent);
other = parent.right;
}
//node節(jié)點的兄弟節(jié)點是黑色，且兄弟節(jié)點的兩個孩子節(jié)點也是黑色
if ((other.left == null || isBlack(other.left)) &&
(other.right == null || isBlack(other.right))){
setColorRed(other);
node = parent;
parent = getParent(node);
} else {
//node節(jié)點的兄弟節(jié)點是黑色怎燥，且兄弟節(jié)點的右孩子是紅色
if (null == other.right || isBlack(other.right)){
setColorBlack(other.left);
setColorRed(other);
rightRotate(other);
other = parent.right;
}
//node節(jié)點的兄弟節(jié)點是黑色瘫筐，且兄弟節(jié)點的右孩子是紅色，左孩子是任意顏色
setColor(other, getColor(parent));
setColorBlack(parent);
setColorBlack(other.right);
leftRotate(parent);
node = this.rootNode;
break;
}
} else {
other = parent.left;
if (isRed(other)){
setColorBlack(other);
setColorRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((null == other.left || isBlack(other.left)) &&
(null == other.right || isBlack(other.right))){
setColorRed(other);
node = parent;
parent = getParent(node);
} else {
if (null == other.left || isBlack(other.left)){
setColorBlack(other.right);
setColorRed(other);
leftRotate(other);
other = parent.left;
}
setColor(other,getColor(parent));
setColorBlack(parent);
setColorBlack(other.left);
rightRotate(parent);
node = this.rootNode;
break;
}
}
}
if (node!=null)
setColorBlack(node);
}
刪除節(jié)點主要分為幾種情況去做對應的處理：
- 1.刪除節(jié)點,按照如下三種情況去刪除節(jié)點
- 1.真正刪除的節(jié)點沒有子節(jié)點
- 2.真正刪除的節(jié)點有一個子節(jié)點
- 3.正在刪除的節(jié)點有兩個子節(jié)點
- 2.修復紅黑樹的特性铐姚，如代碼中調用removeFixUp方法修復紅黑樹的特性策肝。
3.總結
以上主要介紹了紅黑樹的一些特性，包括一些操作詳細的解析了里面的過程隐绵，寫的時間比較長之众，感覺確實比較難理清楚。后面會持續(xù)的理解更深入依许，若有存在問題的地方棺禾，請指正，另紅黑樹實現(xiàn)代碼
本人主要的參考鏈接如下：
1.紅黑樹(五)之 Java的實現(xiàn)
2.通過分析 JDK 源代碼研究 TreeMap 紅黑樹算法實現(xiàn)
3.紅黑樹
4.（圖解）紅黑樹的插入和刪除
5.紅黑樹深入剖析及Java實現(xiàn)
