C语言实现手写红黑树的示例代码

第C语言实现手写红黑树的示例代码RBNode*searchRbTree(RBTree*pTree,char*key){

returnsearchRbTree_(pTree-root,key);

//判断节点是否存在

booleanisExistRbTree(RBTree*pTree,char*key){

RBNode*node=searchRbTree(pTree,key);

if(node==NULL){

returnFALSE;

}else{

returnTRUE;

*(非递归实现)查找"红黑树x"中键值为key的节点

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;

*红黑树删除修正函数

*在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；

*目的是将它重新塑造成一颗红黑树。

*参数说明：

*node待修正的节点

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的俩个孩子也都是黑色的

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的俩个孩子也都是黑色的

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