第C語言實(shí)現(xiàn)手寫紅黑樹的示例代碼RBNode*searchRbTree(RBTree*pTree,char*key){

returnsearchRbTree_(pTree-root,key);

//判斷節(jié)點(diǎn)是否存在

booleanisExistRbTree(RBTree*pTree,char*key){

RBNode*node=searchRbTree(pTree,key);

if(node==NULL){

returnFALSE;

}else{

returnTRUE;

*(非遞歸實(shí)現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點(diǎn)

RBNode*iterativeSearchRbTree_(RBNode*x,char*key){

while(x!=NULL){

intcmp=strcmp(key,x-key);

if(cmp0){

x=x-left;

}elseif(cmp0){

x=x-right;

}else{

returnx;

returnx;

RBNode*iterativeSearchRbTree(RBTree*pTree,char*key){

returniterativeSearchRbTree_(pTree-root,key);

//獲取所有的key和value

voidgetAllKeyAndValueRbTree_(CharKvLinked*pLinked,RBNode*node){

if(node!=NULL){

insertCharKvLinkedHeadNode(pLinked,createCharKvLinkedNode(node-key,node-value));

getAllKeyAndValueRbTree_(pLinked,node-left);

getAllKeyAndValueRbTree_(pLinked,node-right);

//獲取所有的key和value

CharKvLinked*getAllKeyAndValueRbTree(RBTree*tree){

CharKvLinked*pLinked=createCharKvLinked();

getAllKeyAndValueRbTree_(pLinked,tree-root);

returnpLinked;

*紅黑樹刪除修正函數(shù)

*在從紅黑樹中刪除插入節(jié)點(diǎn)之后(紅黑樹失去平衡)，再調(diào)用該函數(shù)；

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

*參數(shù)說明：

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

staticvoidremoveRbTreeFixUp(RBTree*tree,RBNode*node,RBNode*parent){

RBNode*other;

while((node==NULL||isBlack(node))(node!=tree-root)){

if(parent-left==node){

other=parent-right;

if(isRed(other)){

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

setBlack(other);

setRed(parent);

leftRotateRbTree(tree,parent);

other=parent-right;

if((other-left==NULL||isBlack(other-left))

(other-right==NULL||isBlack(other-right))){

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

setRed(other);

node=parent;

parent=parentOf(node);

}else{

if(other-right==NULL||isBlack(other-right)){

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

setBlack(other-left);

setRed(other);

rightRotateRbTree(tree,other);

other=parent-right;

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

setColor(other,parent);

setBlack(parent);

setBlack(other-right);

leftRotateRbTree(tree,parent);

node=tree-root;

break;

}else{

other=parent-left;

if(isRed(other)){

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

setBlack(other);

setRed(parent);

rightRotateRbTree(tree,parent);

other=parent-left;

if((other-left==NULL||isBlack(other-left))

(other-right==NULL||isBlack(other-right))){

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

setRed(other);

node=parent;

parent=parentOf(node);

}else{

if(other-left==NULL||isBlack(other-left)){

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

setBlack(other-right);

setRed(other);

leftRotateRbTree(tree,other);

other=parent-left;

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

setColor(other,parent);

s