第Java數(shù)據(jù)結構之紅黑樹的原理及實現(xiàn)*在從紅黑樹中刪除插入節(jié)點之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)；

*目的是將它重新塑造成一顆紅黑樹。

*參數(shù)說明：

*node待修正的節(jié)點

privatevoidremoveFixUp(RBTNodeTnode,RBTNodeTparent){

RBTNodeTother;

while((node==null||isBlack(node))(node!=this.mRoot)){

if(parent.left==node){

other=parent.right;

if(isRed(other)){

//Case1:x的兄弟w是紅色的

setBlack(other);

setRed(parent);

leftRotate(parent);

other=parent.right;

if((other.left==null||isBlack(other.left))

(other.right==null||isBlack(other.right))){

//Case2:x的兄弟w是黑色，且w的倆個孩子也都是黑色的

setRed(other);

node=parent;

parent=parentOf(node);

}else{

if(other.right==null||isBlack(other.right)){

//Case3:x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。

setBlack(other.left);

setRed(other);

rightRotate(other);

other=parent.right;

//Case4: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)){

//Case1:x的兄弟w是紅色的

setBlack(other);

setRed(parent);

rightRotate(parent);

other=parent.left;

if((other.left==null||isBlack(other.left))

(other.right==null||isBlack(other.right))){

//Case2:x的兄弟w是黑色，且w的倆個孩子也都是黑色的

setRed(other);

node=parent;

parent=parentOf(node);

}else{

if(other.left==null||isBlack(other.left)){

//Case3:x的兄弟w是黑色的，并且w的左孩子是紅色，右孩子為黑色。

setBlack(other.right);

setRed(other);

leftRotate(other);

other=parent.left;

//Case4:x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顏色。

setColor(other,colorOf(parent));

setBlack(parent);

setBlack(other.left);

rightRotate(parent);

node=this.mRoot;

break;

if(node!=null){

setBlack(node);

*刪除結點(node)，并返回被刪除的結點

*參數(shù)說明：

*node刪除的結點

privatevoid

remove(RBTNodeTnode){

RBTNodeTchild,parent;

booleancolor;

//被刪除節(jié)點的"左右孩子都不為空"的情況。

if((node.left!=null)(node.right!=null)){

//被刪節(jié)點的后繼節(jié)點。(稱為"取代節(jié)點")

//用它來取代"被刪節(jié)點"的位置，然后再將"被刪節(jié)點"去掉。

RBTNodeTreplace=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;

*刪除結點(z)，并返回被刪除的結點

*參數(shù)說明：

*tree紅黑樹的根結點

*z刪除的結點

publicvoidremove(Tkey){

RBTNodeTnode;

if((node=search(mRoot,key))!=null){

remove(node);

*銷毀紅黑樹

privatevoiddestroy(RBTNodeTtree){

if(tree==null){

return;

if(tree.left!=null){

destroy(tree.left);

if(tree.right!=null){

destroy(tree.right);

tree=null;

publicvoidclear(){

destroy(mRoot);

mRoot=null;

*打印"紅黑樹"

*key--節(jié)點的鍵值

*direction--0，表示該節(jié)點是根節(jié)點;

*-1，表示該節(jié)點是它的父結點的左孩子;

*1，表示該節(jié)點是它的父結點的右孩子。

privatevoidprint(RBTNodeTtree,Tkey,intdirection){

if(tree!=null){

if(direction==0)//tree是根節(jié)點

System.out.printf("%2d(B)isroot\n",tree.key);

}else//tree是分支節(jié)點

System.out.printf("%2d(%s)is%2d's%6schild\n",tree.key,isRed(tree)"R":"B",key,directio