红黑树的

/** 红黑树连接及插入删除操作*/#include <stdio.h>#include <stdlib.h>//定义红黑树颜色枚举常量typedefenum Color{RED = 0,BLACK = 1}Color;//定义红黑树结构类型typedefstruct RB_TREE{struct RB_TREE *left, *right, *parent;int key;Color color;}RB_TREE;//定义结构体变量RB_TREERB_TREE *nil = NULL;//函数声明区RB_TREE* RB_NewNode(int key);RB_TREE* RB_Insert(RB_TREE* root, int key);RB_TREE* RB_Search(RB_TREE* root, int key, RB_TREE** save);RB_TREE* RB_Delete(RB_TREE* root, int key);RB_TREE* RB_JoinTree(RB_TREE* root1, RB_TREE* x, RB_TREE* root2);voidRB_PreTreeWalk(RB_TREE* root);//主函数int main(){int i = 0;RB_TREE* root1 = NULL, *root2 = NULL, *node = NULL, *x = NULL, *root = NULL; int value1[6] = {5,10,15,20,25};int value2[3] = {55,60,65};x = RB_NewNode(52)//为X分配内存空间x->color = RED;//让X的颜色为红色，(*x.color) equal x->colorfor(i=0;i<5;i++){if ((root1 = RB_Insert(root1,value1[i]))){printf("%d 插入成功!\n",value1[i]);}else{printf("%d 插入失败!\n",value1[i]);exit(-1);}if((node = RB_Search(root1,value1[i],NULL))) {printf("%d 查找成功!\n",value1[i]);}else{printf("%d 查找失败!\n",value1[i]);exit(-1);}}for(i=0;i<3;i++){if ((root2 = RB_Insert(root2,value2[i]))){printf("%d 插入成功!\n",value2[i]);}else{printf("%d 插入失败!\n",value2[i]);exit(-1);}if((node = RB_Search(root2,value2[i],NULL))) {printf("%d 查找成功!\n",value2[i]);}else{printf("%d 查找失败!\n",value2[i]);exit(-1);}}printf("root1中插入的元素为：\n");RB_PreTreeWalk(root1);printf("\nroot2中插入的元素为：\n");RB_PreTreeWalk(root2);root = RB_JoinTree(root1,x,root2);printf("root1、root2和x连接后的root输出为\n");RB_PreTreeWalk(root);if ((root = RB_Insert(root,53))){printf("\nroot中插入53成功!\n");}else{printf("\nroot中插入53失败!\n");exit(-1);}if((node = RB_Search(root,53,NULL))){printf("53 查找成功!\n");}else{printf("53 查找失败!\n");exit(-1);}printf("执行插入操作后root中元素为\n");RB_PreTreeWalk(root);if((root = RB_Delete(root,5)))printf("\nroot中删除5成功!\n");else{printf("\nroot中删除5失败!\n");exit(-1);}if((node = RB_Search(root,5,NULL))){printf("5 查找成功!\n");}else{printf("5 查找失败，该关键字已不存在!\n");}printf("执行删除操作后root中元素为\n");RB_PreTreeWalk(root);return 0;}//建立新结点RB_TREE* RB_NewNode(int key){RB_TREE *node = (RB_TREE*)malloc(sizeof(struct RB_TREE));//系统申请分配指定size个字节的内存空间if (!node){printf("建立新结点失败!\n");exit(-1);}node->key = key;return node;}//前序遍历输出红黑树voidRB_PreTreeWalk(RB_TREE* root){if(root != NULL){printf("left = %8x, root = %8x, right = %8x ,key = %d ,color = %d \n",(int)root->left,(int)(root),(int)root->right,root->key,root->color);RB_PreTreeWalk(root->left);RB_PreTreeWalk(root->right);}}//左旋转RB_TREE* RB_LeftRotate(RB_TREE* root, RB_TREE* node){RB_TREE* right = node->right;if ((node->right = right->left)){right->left->parent = node;}right->left = node;if ((right->parent = node->parent)){if (node == node->parent->right){node->parent->right = right;}else{node->parent->left = right;}}else{root = right;}node->parent = right;return root;}//右旋转RB_TREE* RB_RightRotate(RB_TREE* root, RB_TREE* node) {RB_TREE* left = node->left;if ((node->left = left->right)){left->right->parent = node;}left->right = node;if ((left->parent = node->parent)){if (node == node->parent->right){node->parent->right = left;}else{node->parent->left = left;}}else{root = left;}node->parent = left;return root;}/** 插入调整，对结点重新着色并旋转* 红黑树性质：1.每个结点或红或黑；2.根结点是黑色；3.叶子结点为黑；* 4.若一个结点为红，则其两个儿子都为黑；5.每条路径具有相同数目的黒结点*/RB_TREE* RB_InsertFixup(RB_TREE *root, RB_TREE *node){RB_TREE *parent = NULL, *gparent = NULL, *uncle = NULL;while ((parent = node->parent) && parent->color == RED){gparent = parent->parent;if (parent == gparent->left){uncle = gparent->right;if (uncle && uncle->color == RED){uncle->color = BLACK;parent->color = BLACK;gparent->color = RED;node = gparent;}else{if (parent->right == node){root = RB_LeftRotate(root, parent);node = parent;}parent->color = BLACK;gparent->color = RED;root = RB_RightRotate(root, gparent);}}else{uncle = gparent->left;if (uncle && uncle->color == RED){uncle->color = BLACK;parent->color = BLACK;gparent->color = RED;node = gparent;}else{if (parent->left == node){root = RB_RightRotate(root, parent);node = parent;}parent->color = BLACK;gparent->color = RED;root = RB_LeftRotate(root, gparent);}}}root->color = BLACK;return root;}//删除调整RB_TREE* RB_DeleteFixup(RB_TREE *root, RB_TREE *node, RB_TREE *parent) {RB_TREE *other, *o_left, *o_right;//node为有关键字的內结点或为哨兵NILwhile ((!node || node->color == BLACK) && node != root){if (parent->left == node){other = parent->right;if (other->color == RED){other->color = BLACK;parent->color = RED;root = RB_LeftRotate(root, parent);other = parent->right;}if ((!other->left || other->left->color == BLACK) &&(!other->right || other->right->color == BLACK)){other->color = RED;node = parent;parent = node->parent;}else{if (!other->right || other->right->color == BLACK){if ((o_left = other->left)){o_left->color = BLACK;}other->color = RED;root = RB_RightRotate(root, other);other = parent->right;}other->color = parent->color;parent->color = BLACK;if (other->right){other->right->color = BLACK;}root = RB_LeftRotate(root, parent);node = root;break;}}else{other = parent->left;if (other->color == RED){other->color = BLACK;parent->color = RED;root = RB_RightRotate(root, parent);other = parent->left;}if ((!other->left || other->left->color == BLACK) && (!other->right || other->right->color == BLACK)){other->color = RED;node = parent;parent = node->parent;}else{if (!other->left || other->left->color == BLACK){if ((o_right = other->right)){o_right->color = BLACK;}other->color = RED;root = RB_LeftRotate(root, other);other = parent->left;}other->color = parent->color;parent->color = BLACK;if (other->left){other->left->color = BLACK;}root = RB_RightRotate(root, parent);node = root;break;}}}if (node){node->color = BLACK;}return root;}//插入操作RB_TREE* RB_Insert(RB_TREE* root, int key)//返回指向RB_TREE的指针{RB_TREE *parent = NULL, *node;parent = NULL;//利用查找函数找到插入点位置if ((node = RB_Search(root, key, &parent))){return root;}node = RB_NewNode(key);node->parent = parent;node->left = node->right = nil;node->color = RED;//新插入的节点为红色if (parent){if (parent->key > key){parent->left = node;}else{parent->right = node;}}else{root = node;}returnRB_InsertFixup(root, node);}//查找操作，返回找到的结点RB_TREE* RB_Search(RB_TREE* root, int key, RB_TREE** save)//双重指针{RB_TREE *node = root, *parent = NULL;while (node){parent = node;//即将插入的node的父节点if(key < node->key)node = node->left;else if(key > node->key)node = node->right;elsereturn node;}if (save){*save = parent;}return NULL;}RB_TREE* RB_Delete(RB_TREE *root, int key) {RB_TREE *child, *parent, *old, *left, *node;Color color;if (!(node = RB_Search(root, key,NULL))){printf("%d不存在!\n",key);return root;}old = node;if (node->left && node->right){node = node->right;while ((left = node->left) != NULL){node = left;}child = node->right;parent = node->parent;color = node->color;if (child){child->parent = parent;}if (parent){if (parent->left == node){parent->left = child;}else{parent->right = child;}}else{root = child;}if (node->parent == old)parent = node;}node->parent = old->parent; node->color = old->color; node->right = old->right; node->left = old->left;if (old->parent){if (old->parent->left == old){old->parent->left = node;}else{old->parent->right = node;}}else{root = node;}old->left->parent = node;if (old->right){old->right->parent = node;}}else{if (!node->left){child = node->right;}else if (!node->right){child = node->left;}parent = node->parent; color = node->color;if (child)child->parent = parent;}if (parent){if (parent->left == node){parent->left = child;}else{parent->right = child;}}else{root = child;}}free(old);if (color == BLACK){root = RB_DeleteFixup(root, child, parent);}return root;}/** 统计红黑树某一路径黑高度* 红黑树任一路径上黑高度均相同*/intRB_SearchBlackHeight(RB_TREE* root){RB_TREE *node = root;intblackheight = 0;while (node){blackheight += node->color;if (node->right != NULL) //沿右子树向下检测node = node->right;elsebreak;}returnblackheight;}/** 寻找并返回某一路径第num个黑结点* root1中所有元素关键字均小于x中关键字，root1中子树只能做x的左子树，因此从root1右子树开始寻找* root2中子树只能作x的右子树，从root2的左子树开始寻找*/RB_TREE* RB_SearchNewNode(RB_TREE* root, RB_TREE* x, intnum){RB_TREE *node = root;intblackheight = 0, tmp;if(num> 0)tmp = num;elsetmp = -num;while (node){blackheight += node->color;if(tmp == blackheight){if(num>0)node->parent->right = x;elsenode->parent->left = x;return node;}else if (num> 0 && node->right != NULL) //从root1的右边开始寻找node = node->right;else if (num< 0 && node->left != NULL) //从root2的左边开始寻找node = node->left;elsebreak;}return node;}/** 红黑树连接操作* 当num1 = num2，则将root2作为x的右子树，root1作为左子树，将父节点设为NIL，x颜色改为黑色，这样两边黑高度一样，返回x即可；* 当num1 > num2，从root1根节点开始向右寻找黑节点，从第num1 - num2 + 1个黑节点处截断，将该节点开始后面黑高度为num2的部分子树做为x的左子树，* root2做为x的右子树，然后将该节点的父节点做为x的父节点，再返回root1即可；* 当num1 < num2，从root2根节点开始向左寻找黑节点，从第num1 - num2 + 1个黑节点处截断，将该节点开始后面黑高度为num1]的部分子树做为x的右子树，* root1做为x的左子树，然后将该节点的父节点做为x的父节点，再返回root2即可。