紅黑樹原理
首先說在前面的一點，平衡二叉樹的查找性能比紅黑樹要高，但卻沒有紅黑樹用的普遍。主要是因為平衡二叉樹追求絕對平衡，導(dǎo)致插入時出現(xiàn)不平衡就要旋轉(zhuǎn)，而旋轉(zhuǎn)的代價太大。紅黑樹只是追求大致平衡，但是插入時調(diào)整的效率更高，因而普遍使用。
紅黑樹（Red-Black Tree，簡稱R-B Tree），它是一種特殊的二叉查找樹。首先它滿足二叉查找樹的特征：任意結(jié)點結(jié)點包含的鍵值，大于左孩子的鍵值，小于右孩子的鍵值。
除此之外，紅黑樹的每個結(jié)點都有存儲位來表示結(jié)點的顏色，不是紅（Red）就是 黑（Black）。
紅黑樹的特性：
- 1.每個結(jié)點或是紅色的，或是黑色的。
- 2.根結(jié)點是黑色的。
- 3.每個葉結(jié)點（NIL）是黑色的。（最后的葉結(jié)點就是空的，或者用一個哨兵替換掉所有的空結(jié)點）
- 4.如果一個結(jié)點是紅色的，那么它的兩個子結(jié)點都是黑色的。
- 5.對每個結(jié)點，從該結(jié)點到其所有后代葉結(jié)點的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點。
關(guān)于它的特性，需要注意：
第一，特性 3 中的葉子結(jié)點，是為空（NIL或null）的結(jié)點
第二，特性 5 ，確保沒有一條路徑會比其他路徑長出2倍，因而是近似平衡的。
紅黑樹的圖如下（直接借用算法導(dǎo)論中的圖，其中淺色的為紅色，深色的為黑色）：
紅黑樹的java代碼實現(xiàn)
紅黑樹的基本操作是查找，選擇，添加，刪除。查找就省略了，和二叉樹的查找區(qū)別不大。在添加和刪除后，都會用到紅黑樹的旋轉(zhuǎn)。因為修改紅黑樹之后，會破壞紅黑樹的性質(zhì)，所以需要旋轉(zhuǎn)滿足這幾條性質(zhì)。
旋轉(zhuǎn)包括兩種：左旋和右旋
1.基本定義
public class RBTree<T extends Comparable<T>>{
private RBTNode<T> mRoot; //根結(jié)點
private static final boolean RED = false;
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>>{
boolean color; //顏色
T key; //關(guān)鍵字（鍵值）
RBTNode<T> left; //左孩子
RBTNode<T> right; //右孩子
RBTNode<T> parent; //父節(jié)點
public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
}
...
}
說明：RBTree是紅黑樹對應(yīng)的類，RBTNode是紅黑樹的結(jié)點類。在RBTree中包含了根節(jié)點mRoot和紅黑樹的相關(guān)API。
2.左旋
對x進(jìn)行左旋，意味著將x變成一個左結(jié)點。
左旋代碼
/*
* 對紅黑樹的節(jié)點(x)進(jìn)行左旋轉(zhuǎn)
*
* 左旋示意圖(對節(jié)點x進(jìn)行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-. / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
private void leftRotate(RBTNode<T> x){
//設(shè)置x的右孩子為y
RBTNode<T> y = x.right;
//將 "y的左孩子" 設(shè)為 "x的右孩子"
//如果y的左孩子非空，將 "x" 設(shè)為 "y的左孩子的父親"
x.right = y.left;
if(y.left != null){
y.left.parent = x;
}
//將 "x的父親" 設(shè)為 "y的父親"
y.parent = x.parent;
if(x.parent == null){
this.mRoot = y; //如果 "x的父親" 是空結(jié)點，則將y設(shè)為根結(jié)點
}else{
if(x.parent.left == x){
x.parent.left = y; //如果 x是它父節(jié)點的左孩子，則將y設(shè)置為 "x的父節(jié)點的左孩子"
}else{
x.parent.right = y; //如果 x是它父節(jié)點的右孩子，則將y設(shè)置為 "x的父節(jié)點的右孩子"
}
}
// 將 “x” 設(shè)為 “y的左孩子”
y.left = x;
// 將 “x的父節(jié)點” 設(shè)為 “y”
x.parent = y;
}
3.右旋
對y進(jìn)行左旋，意味著"將y變成一個右節(jié)點"。
右旋代碼：
/*
* 對紅黑樹的節(jié)點(y)進(jìn)行右旋轉(zhuǎn)
*
* 右旋示意圖(對節(jié)點y進(jìn)行左旋)：
* py py
* / /
* y x
* / \ --(右旋)-. / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
private void rightRotate(RBTNode<T> y) {
// 設(shè)置x是當(dāng)前節(jié)點的左孩子。
RBTNode<T> x = y.left;
// 將 “x的右孩子” 設(shè)為 “y的左孩子”；
// 如果"x的右孩子"不為空的話，將 “y” 設(shè)為 “x的右孩子的父親”
y.left = x.right;
if (x.right != null)
x.right.parent = y;
// 將 “y的父親” 設(shè)為 “x的父親”
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x; // 如果 “y的父親” 是空節(jié)點，則將x設(shè)為根節(jié)點
} else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父節(jié)點的右孩子，則將x設(shè)為“y的父節(jié)點的右孩子”
else
y.parent.left = x; // (y是它父節(jié)點的左孩子) 將x設(shè)為“x的父節(jié)點的左孩子”
}
// 將 “y” 設(shè)為 “x的右孩子”
x.right = y;
// 將 “y的父節(jié)點” 設(shè)為 “x”
y.parent = x;
}
4.添加
將結(jié)點插入紅黑樹時，首先將紅黑樹當(dāng)作一棵二叉查找樹，然后將結(jié)點插入；然后將結(jié)點著色為紅色，再通過“旋轉(zhuǎn)和重新著色”等操作修正該樹，使其成為一棵紅黑樹。詳細(xì)步驟如下：
第一步：將紅黑樹當(dāng)作一棵二叉查找樹，將結(jié)點插入（這個簡單，不展開）。
第二步：將插入的結(jié)點著色為“紅色”
為什么著色為紅色，而不是黑色？可以觀測紅黑樹的5個特性，發(fā)現(xiàn)不會違背“特性（5）”，當(dāng)然有可能違背其他特性，但只是可能，不一定會，所以遵循著違背的越少越好的原則，將插入的結(jié)點著色為紅色。
第三步：通過一系列的選擇或者著色等操作，使其重新成為紅黑樹
第二步中，將插入節(jié)點著色為"紅色"之后，不會違背"特性(5)"。那它到底會違背哪些特性呢？
對于"特性(1)"，顯然不會違背了。因為我們已經(jīng)將它涂成紅色了。
對于"特性(2)"，顯然也不會違背。在第一步中，我們是將紅黑樹當(dāng)作二叉查找樹，然后執(zhí)行的插入操作。而根據(jù)二叉查找數(shù)的特點，插入操作不會改變根節(jié)點。所以，根節(jié)點仍然是黑色。
對于"特性(3)"，顯然不會違背了。這里的葉子節(jié)點是指的空葉子節(jié)點，插入非空節(jié)點并不會對它們造成影響。
對于"特性(4)"，是有可能違背的！
那接下來，想辦法使之"滿足特性(4)"，就可以將樹重新構(gòu)造成紅黑樹了。
添加操作的實現(xiàn)代碼
/*
* 將結(jié)點插入到紅黑樹中
*
* 參數(shù)說明：
* node 插入的結(jié)點 // 對應(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é)點添加到二叉查找樹中。
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é)點的顏色為紅色
node.color = RED;
// 3. 將它重新修正為一顆二叉查找樹
insertFixUp(node);
}
/*
* 新建結(jié)點(key)，并將其插入到紅黑樹中
*
* 參數(shù)說明：
* key 插入結(jié)點的鍵值
*/
public void insert(T key) {
RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
// 如果新建結(jié)點失敗，則返回。
if (node != null)
insert(node);
}
內(nèi)部接口 -- insert(node)的作用是將"node"節(jié)點插入到紅黑樹中。
外部接口 -- insert(key)的作用是將"key"添加到紅黑樹中。
添加修正操作的實現(xiàn)代碼
/*
* 紅黑樹插入修正函數(shù)
*
* 在向紅黑樹中插入節(jié)點之后(失去平衡)，再調(diào)用該函數(shù)；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 插入的結(jié)點 // 對應(yīng)《算法導(dǎo)論》中的z
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父節(jié)點存在，并且父節(jié)點的顏色是紅色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節(jié)點”是“祖父節(jié)點的左孩子”
if (parent == gparent.left) {
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.right;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子
if (parent.right == node) {
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父節(jié)點”是“z的祖父節(jié)點的右孩子”
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.left;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子
if (parent.left == node) {
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 將根節(jié)點設(shè)為黑色
setBlack(this.mRoot);
}
insertFixUp(node)的作用是對應(yīng)"上面所講的第三步"。它是一個內(nèi)部接口。
5.刪除操作
將紅黑樹內(nèi)的某一個節(jié)點刪除。需要執(zhí)行的操作依次是：首先，將紅黑樹當(dāng)作一顆二叉查找樹，將該節(jié)點從二叉查找樹中刪除；然后，通過"旋轉(zhuǎn)和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹。詳細(xì)描述如下：
第一步：將紅黑樹當(dāng)作一棵二叉查找樹，將結(jié)點刪除
這和"刪除常規(guī)二叉查找樹中刪除節(jié)點的方法是一樣的"。分3種情況：
① 被刪除節(jié)點沒有兒子，即為葉節(jié)點。那么，直接將該節(jié)點刪除就OK了。
② 被刪除節(jié)點只有一個兒子。那么，直接刪除該節(jié)點，并用該節(jié)點的唯一子節(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é)點不可能是雙子非空。既然"的后繼節(jié)點"不可能雙子都非空，就意味著"該節(jié)點的后繼節(jié)點"要么沒有兒子，要么只有一個兒子。若沒有兒子，則按"情況① "進(jìn)行處理；若只有一個兒子，則按"情況② "進(jìn)行處理。
第二步：通過“旋轉(zhuǎn)和重新著色”等一系列操作修正該樹，使其重新成為一棵紅黑樹。
因為"第一步"中刪除節(jié)點之后，可能會違背紅黑樹的特性。所以需要通過"旋轉(zhuǎn)和重新著色"來修正該樹，使之重新成為一棵紅黑樹。
/*
* 刪除結(jié)點(node)，并返回被刪除的結(jié)點
*
* 參數(shù)說明：
* node 刪除的結(jié)點
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被刪除節(jié)點的"左右孩子都不為空"的情況。
if ( (node.left!=null) && (node.right!=null) ) {
// 被刪節(jié)點的后繼節(jié)點。(稱為"取代節(jié)點")
// 用它來取代"被刪節(jié)點"的位置，然后再將"被刪節(jié)點"去掉。
RBTNode<T> replace = node;
// 獲取后繼節(jié)點
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// "node節(jié)點"不是根節(jié)點(只有根節(jié)點不存在父節(jié)點)
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else {
// "node節(jié)點"是根節(jié)點，更新根節(jié)點。
this.mRoot = replace;
}
// child是"取代節(jié)點"的右孩子，也是需要"調(diào)整的節(jié)點"。
// "取代節(jié)點"肯定不存在左孩子！因為它是一個后繼節(jié)點。
child = replace.right;
parent = parentOf(replace);
// 保存"取代節(jié)點"的顏色
color = colorOf(replace);
// "被刪除節(jié)點"是"它的后繼節(jié)點的父節(jié)點"
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é)點"的顏色
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 {
this.mRoot = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
/*
* 刪除結(jié)點(z)，并返回被刪除的結(jié)點
*
* 參數(shù)說明：
* tree 紅黑樹的根結(jié)點
* z 刪除的結(jié)點
*/
public void remove(T key) {
RBTNode<T> node;
if ((node = search(mRoot, key)) != null)
remove(node);
}
內(nèi)部接口 -- remove(node)的作用是將"node"節(jié)點插入到紅黑樹中。
外部接口 -- remove(key)刪除紅黑樹中鍵值為key的節(jié)點。
刪除修正操作的實現(xiàn)代碼
/*
* 紅黑樹刪除修正函數(shù)
*
* 在從紅黑樹中刪除插入節(jié)點之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 待修正的節(jié)點
*/
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的倆個孩子也都是黑色的
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的倆個孩子也都是黑色的
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);
}
removeFixup(node, parent)是對應(yīng)"上面所講的第三步"。它是一個內(nèi)部接口。
紅黑樹的完整源碼
下面是紅黑樹實現(xiàn)的完整代碼和相應(yīng)的測試程序。
(1) 除了上面所說的"左旋"、"右旋"、"添加"、"刪除"等基本操作之后，還實現(xiàn)了"遍歷"、"查找"、"打印"、"最小值"、"最大值"、"創(chuàng)建"、"銷毀"等接口。
(2) 函數(shù)接口大多分為內(nèi)部接口和外部接口。內(nèi)部接口是private函數(shù)，外部接口則是public函數(shù)。
(3) 測試代碼中提供了"插入"和"刪除"動作的檢測開關(guān)。默認(rèn)是關(guān)閉的，打開方法可以參考"代碼中的說明"。建議在打開開關(guān)后，在草稿上自己動手繪制一下紅黑樹。
紅黑樹的實現(xiàn)文件(RBTree.java)
/**
* Java 語言: 紅黑樹
*
* @author skywang
* @date 2013/11/07
*/
public class RBTree<T extends Comparable<T>> {
private RBTNode<T> mRoot; // 根結(jié)點
private static final boolean RED = false;
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>> {
boolean color; // 顏色
T key; // 關(guān)鍵字(鍵值)
RBTNode<T> left; // 左孩子
RBTNode<T> right; // 右孩子
RBTNode<T> parent; // 父結(jié)點
public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
public String toString() {
return ""+key+(this.color==RED?"(R)":"B");
}
}
public RBTree() {
mRoot=null;
}
private RBTNode<T> parentOf(RBTNode<T> node) {
return node!=null ? node.parent : null;
}
private boolean colorOf(RBTNode<T> node) {
return node!=null ? node.color : BLACK;
}
private boolean isRed(RBTNode<T> node) {
return ((node!=null)&&(node.color==RED)) ? true : false;
}
private boolean isBlack(RBTNode<T> node) {
return !isRed(node);
}
private void setBlack(RBTNode<T> node) {
if (node!=null)
node.color = BLACK;
}
private void setRed(RBTNode<T> node) {
if (node!=null)
node.color = RED;
}
private void setParent(RBTNode<T> node, RBTNode<T> parent) {
if (node!=null)
node.parent = parent;
}
private void setColor(RBTNode<T> node, boolean color) {
if (node!=null)
node.color = color;
}
/*
* 前序遍歷"紅黑樹"
*/
private void preOrder(RBTNode<T> tree) {
if(tree != null) {
System.out.print(tree.key+" ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
* 中序遍歷"紅黑樹"
*/
private void inOrder(RBTNode<T> tree) {
if(tree != null) {
inOrder(tree.left);
System.out.print(tree.key+" ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
* 后序遍歷"紅黑樹"
*/
private void postOrder(RBTNode<T> tree) {
if(tree != null)
{
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+" ");
}
}
public void postOrder() {
postOrder(mRoot);
}
/*
* (遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點
*/
private RBTNode<T> search(RBTNode<T> x, T key) {
if (x==null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search(x.left, key);
else if (cmp > 0)
return search(x.right, key);
else
return x;
}
public RBTNode<T> search(T key) {
return search(mRoot, key);
}
/*
* (非遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點
*/
private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {
while (x!=null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
public RBTNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
/*
* 查找最小結(jié)點：返回tree為根結(jié)點的紅黑樹的最小結(jié)點。
*/
private RBTNode<T> minimum(RBTNode<T> tree) {
if (tree == null)
return null;
while(tree.left != null)
tree = tree.left;
return tree;
}
public T minimum() {
RBTNode<T> p = minimum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 查找最大結(jié)點：返回tree為根結(jié)點的紅黑樹的最大結(jié)點。
*/
private RBTNode<T> maximum(RBTNode<T> tree) {
if (tree == null)
return null;
while(tree.right != null)
tree = tree.right;
return tree;
}
public T maximum() {
RBTNode<T> p = maximum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 找結(jié)點(x)的后繼結(jié)點。即，查找"紅黑樹中數(shù)據(jù)值大于該結(jié)點"的"最小結(jié)點"。
*/
public RBTNode<T> successor(RBTNode<T> x) {
// 如果x存在右孩子，則"x的后繼結(jié)點"為 "以其右孩子為根的子樹的最小結(jié)點"。
if (x.right != null)
return minimum(x.right);
// 如果x沒有右孩子。則x有以下兩種可能：
// (01) x是"一個左孩子"，則"x的后繼結(jié)點"為 "它的父結(jié)點"。
// (02) x是"一個右孩子"，則查找"x的最低的父結(jié)點，并且該父結(jié)點要具有左孩子"，找到的這個"最低的父結(jié)點"就是"x的后繼結(jié)點"。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.right)) {
x = y;
y = y.parent;
}
return y;
}
/*
* 找結(jié)點(x)的前驅(qū)結(jié)點。即，查找"紅黑樹中數(shù)據(jù)值小于該結(jié)點"的"最大結(jié)點"。
*/
public RBTNode<T> predecessor(RBTNode<T> x) {
// 如果x存在左孩子，則"x的前驅(qū)結(jié)點"為 "以其左孩子為根的子樹的最大結(jié)點"。
if (x.left != null)
return maximum(x.left);
// 如果x沒有左孩子。則x有以下兩種可能：
// (01) x是"一個右孩子"，則"x的前驅(qū)結(jié)點"為 "它的父結(jié)點"。
// (01) x是"一個左孩子"，則查找"x的最低的父結(jié)點，并且該父結(jié)點要具有右孩子"，找到的這個"最低的父結(jié)點"就是"x的前驅(qū)結(jié)點"。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.left)) {
x = y;
y = y.parent;
}
return y;
}
/*
* 對紅黑樹的節(jié)點(x)進(jìn)行左旋轉(zhuǎn)
*
* 左旋示意圖(對節(jié)點x進(jìn)行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-. / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
private void leftRotate(RBTNode<T> x) {
// 設(shè)置x的右孩子為y
RBTNode<T> y = x.right;
// 將 “y的左孩子” 設(shè)為 “x的右孩子”；
// 如果y的左孩子非空，將 “x” 設(shè)為 “y的左孩子的父親”
x.right = y.left;
if (y.left != null)
y.left.parent = x;
// 將 “x的父親” 設(shè)為 “y的父親”
y.parent = x.parent;
if (x.parent == null) {
this.mRoot = y; // 如果 “x的父親” 是空節(jié)點，則將y設(shè)為根節(jié)點
} else {
if (x.parent.left == x)
x.parent.left = y; // 如果 x是它父節(jié)點的左孩子，則將y設(shè)為“x的父節(jié)點的左孩子”
else
x.parent.right = y; // 如果 x是它父節(jié)點的左孩子，則將y設(shè)為“x的父節(jié)點的左孩子”
}
// 將 “x” 設(shè)為 “y的左孩子”
y.left = x;
// 將 “x的父節(jié)點” 設(shè)為 “y”
x.parent = y;
}
/*
* 對紅黑樹的節(jié)點(y)進(jìn)行右旋轉(zhuǎn)
*
* 右旋示意圖(對節(jié)點y進(jìn)行左旋)：
* py py
* / /
* y x
* / \ --(右旋)-. / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
private void rightRotate(RBTNode<T> y) {
// 設(shè)置x是當(dāng)前節(jié)點的左孩子。
RBTNode<T> x = y.left;
// 將 “x的右孩子” 設(shè)為 “y的左孩子”；
// 如果"x的右孩子"不為空的話，將 “y” 設(shè)為 “x的右孩子的父親”
y.left = x.right;
if (x.right != null)
x.right.parent = y;
// 將 “y的父親” 設(shè)為 “x的父親”
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x; // 如果 “y的父親” 是空節(jié)點，則將x設(shè)為根節(jié)點
} else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父節(jié)點的右孩子，則將x設(shè)為“y的父節(jié)點的右孩子”
else
y.parent.left = x; // (y是它父節(jié)點的左孩子) 將x設(shè)為“x的父節(jié)點的左孩子”
}
// 將 “y” 設(shè)為 “x的右孩子”
x.right = y;
// 將 “y的父節(jié)點” 設(shè)為 “x”
y.parent = x;
}
/*
* 紅黑樹插入修正函數(shù)
*
* 在向紅黑樹中插入節(jié)點之后(失去平衡)，再調(diào)用該函數(shù)；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 插入的結(jié)點 // 對應(yīng)《算法導(dǎo)論》中的z
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父節(jié)點存在，并且父節(jié)點的顏色是紅色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節(jié)點”是“祖父節(jié)點的左孩子”
if (parent == gparent.left) {
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.right;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子
if (parent.right == node) {
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父節(jié)點”是“z的祖父節(jié)點的右孩子”
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.left;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子
if (parent.left == node) {
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 將根節(jié)點設(shè)為黑色
setBlack(this.mRoot);
}
/*
* 將結(jié)點插入到紅黑樹中
*
* 參數(shù)說明：
* node 插入的結(jié)點 // 對應(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é)點添加到二叉查找樹中。
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é)點的顏色為紅色
node.color = RED;
// 3. 將它重新修正為一顆二叉查找樹
insertFixUp(node);
}
/*
* 新建結(jié)點(key)，并將其插入到紅黑樹中
*
* 參數(shù)說明：
* key 插入結(jié)點的鍵值
*/
public void insert(T key) {
RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
// 如果新建結(jié)點失敗，則返回。
if (node != null)
insert(node);
}
/*
* 紅黑樹刪除修正函數(shù)
*
* 在從紅黑樹中刪除插入節(jié)點之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 待修正的節(jié)點
*/
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的倆個孩子也都是黑色的
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的倆個孩子也都是黑色的
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);
}
/*
* 刪除結(jié)點(node)，并返回被刪除的結(jié)點
*
* 參數(shù)說明：
* node 刪除的結(jié)點
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被刪除節(jié)點的"左右孩子都不為空"的情況。
if ( (node.left!=null) && (node.right!=null) ) {
// 被刪節(jié)點的后繼節(jié)點。(稱為"取代節(jié)點")
// 用它來取代"被刪節(jié)點"的位置，然后再將"被刪節(jié)點"去掉。
RBTNode<T> replace = node;
// 獲取后繼節(jié)點
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// "node節(jié)點"不是根節(jié)點(只有根節(jié)點不存在父節(jié)點)
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else {
// "node節(jié)點"是根節(jié)點，更新根節(jié)點。
this.mRoot = replace;
}
// child是"取代節(jié)點"的右孩子，也是需要"調(diào)整的節(jié)點"。
// "取代節(jié)點"肯定不存在左孩子！因為它是一個后繼節(jié)點。
child = replace.right;
parent = parentOf(replace);
// 保存"取代節(jié)點"的顏色
color = colorOf(replace);
// "被刪除節(jié)點"是"它的后繼節(jié)點的父節(jié)點"
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é)點"的顏色
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 {
this.mRoot = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
/*
* 刪除結(jié)點(z)，并返回被刪除的結(jié)點
*
* 參數(shù)說明：
* tree 紅黑樹的根結(jié)點
* z 刪除的結(jié)點
*/
public void remove(T key) {
RBTNode<T> node;
if ((node = search(mRoot, key)) != null)
remove(node);
}
/*
* 銷毀紅黑樹
*/
private void destroy(RBTNode<T> tree) {
if (tree==null)
return ;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree=null;
}
public void clear() {
destroy(mRoot);
mRoot = null;
}
/*
* 打印"紅黑樹"
*
* key -- 節(jié)點的鍵值
* direction -- 0，表示該節(jié)點是根節(jié)點;
* -1，表示該節(jié)點是它的父結(jié)點的左孩子;
* 1，表示該節(jié)點是它的父結(jié)點的右孩子。
*/
private void print(RBTNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0) // tree是根節(jié)點
System.out.printf("%2d(B) is root\n", tree.key);
else // tree是分支節(jié)點
System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left");
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
}
}
紅黑樹的測試文件(RBTreeTest.java)
/**
* Java 語言: 二叉查找樹
*
* @author skywang
* @date 2013/11/07
*/
public class RBTreeTest {
private static final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
private static final boolean mDebugInsert = false; // "插入"動作的檢測開關(guān)(false，關(guān)閉；true，打開)
private static final boolean mDebugDelete = false; // "刪除"動作的檢測開關(guān)(false，關(guān)閉；true，打開)
public static void main(String[] args) {
int i, ilen = a.length;
RBTree<Integer> tree=new RBTree<Integer>();
System.out.printf("== 原始數(shù)據(jù): ");
for(i=0; i<ilen; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
for(i=0; i<ilen; i++) {
tree.insert(a[i]);
// 設(shè)置mDebugInsert=true,測試"添加函數(shù)"
if (mDebugInsert) {
System.out.printf("== 添加節(jié)點: %d\n", a[i]);
System.out.printf("== 樹的詳細(xì)信息: \n");
tree.print();
System.out.printf("\n");
}
}
System.out.printf("== 前序遍歷: ");
tree.preOrder();
System.out.printf("\n== 中序遍歷: ");
tree.inOrder();
System.out.printf("\n== 后序遍歷: ");
tree.postOrder();
System.out.printf("\n");
System.out.printf("== 最小值: %s\n", tree.minimum());
System.out.printf("== 最大值: %s\n", tree.maximum());
System.out.printf("== 樹的詳細(xì)信息: \n");
tree.print();
System.out.printf("\n");
// 設(shè)置mDebugDelete=true,測試"刪除函數(shù)"
if (mDebugDelete) {
for(i=0; i<ilen; i++)
{
tree.remove(a[i]);
System.out.printf("== 刪除節(jié)點: %d\n", a[i]);
System.out.printf("== 樹的詳細(xì)信息: \n");
tree.print();
System.out.printf("\n");
}
}
// 銷毀二叉樹
tree.clear();
}
}
參考資料
真的很感謝這位博主的解析，讓我等也能窺探紅黑樹的代碼魅力。
1.http://www.cnblogs.com/skywang12345/p/3624343.htmle
