//by svking//2012.5#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAXSIZE 1000typedef int ElemType;#define RED 0#define BLACK 1typedef struct RBTNode{char color;ElemType data;struct RBTNode * p;struct RBTNode * left;struct RBTNode * right;}RBTNode, * PRBTNode;typedef struct RBTree{PRBTNode root;PRBTNode nil; //统一的空节点，该节点是黑的}RBTree, * PRBTree;int leftRotate (PRBTree tree, PRBTNode t);int rightRotate (PRBTree tree, PRBTNode t);PRBTNode insertRB (PRBTree tree, ElemType d);int insertRB_fixup (PRBTree tree, PRBTNode t);int createRBTree (PRBTree tree, ElemType d[], int n); int initRB (PRBTree tree);PRBTNode maximum (PRBTree tree, PRBTNode t); PRBTNode minimum (PRBTree tree, PRBTNode t); PRBTNode next (PRBTree tree, PRBTNode t);PRBTNode precursor (PRBTree tree, PRBTNode t);int walkNext (PRBTree tree);int inOrderWalk (PRBTree tree, PRBTNode t);int deleteRB_fixup (PRBTree tree, PRBTNode c); PRBTNode deleteRB (PRBTree tree, PRBTNode t);int main (){PRBTNode p;int d[MAXSIZE];int n = 0;int i;RBTree tree;initRB(&tree);/*insertRB(&tree, 11);insertRB(&tree, 2);insertRB(&tree, 14);insertRB(&tree, 1);insertRB(&tree, 7);insertRB(&tree, 15);insertRB(&tree, 5);insertRB(&tree, 8);insertRB(&tree, 4);*/p= insertRB(&tree, 26);insertRB(&tree, 17);insertRB(&tree, 41);insertRB(&tree, 14);insertRB(&tree, 21);insertRB(&tree, 30);insertRB(&tree, 47);insertRB(&tree, 10);insertRB(&tree, 16);insertRB(&tree, 19);insertRB(&tree, 23);insertRB(&tree, 28);insertRB(&tree, 38);insertRB(&tree, 7);insertRB(&tree, 12);insertRB(&tree, 15);insertRB(&tree, 20);insertRB(&tree, 3);insertRB(&tree, 35);insertRB(&tree, 39);srand(time(NULL));/*puts("请输入数据的个数：");scanf("%d",&n);printf("随机生成的%d个数据是：\n",n); for (i = 0; i < n; i++){d[i] = rand()%1000;printf("%d ",d[i]);}puts("");puts("建树开始");createRBTree(&tree, d, n);*/inOrderWalk(&tree,tree.root);puts("");printf("根是%d \n",tree.root->data);printf("删除%d后：",p->data);deleteRB(&tree, p);inOrderWalk(&tree,tree.root);puts("");printf("根是%d \n",tree.root->data);return0;}PRBTNode insertRB (PRBTree tree, ElemType d){//插入元素//!!!记得插入的元素的初始化，p指向为父母节点，left和right赋值为NULL。

PRBTNode t = NULL;PRBTNode p = NULL;int flag = 0; //用来表示插入在左边的树还是右边的树t = tree->root;//插入的节点是root,并做相应的初始化if (tree->root == tree->nil){tree->root = (PRBTNode)malloc(sizeof(RBTNode));tree->root->data = d;tree->root->color = BLACK;tree->root->p = tree->root->left =tree->root->right = tree->nil;return tree->root;}while (t != tree->nil){p = t;if (d < t->data){flag = 0;t = t->left;}else{if (d > t->data){flag = 1;t = t->right;}else{if ( (flag=rand()%2) == 0)t = t->left;elset = t->right;}}}//while//将t指向带插入节点的地址，并初始化t = (PRBTNode)malloc(sizeof(RBTNode));t->data = d;t->color = RED;t->p = p;t->left = t->right = tree->nil;if (!flag)p->left = t;elsep->right = t;insertRB_fixup(tree, t);return t;}int insertRB_fixup (PRBTree tree, PRBTNode t){//插入的节点可能破坏红黑树的性质。

该函数检测插入的节点是否破坏了红黑树的性质。

如果破坏了，就对树进行调整，使其满足红黑树的性质while (t->p->color == RED) //只有插入节点的父亲是红色的才会破坏红黑树的性质（4.如果一个结点是红的，那么它的俩个儿子都是黑的）{if (t->p->p->left == t->p) //插入节点的父节点本身是left{if (t->p->p->right->color == RED) //case 1{t = t->p->p;t->left->color = t->right->color = BLACK;t->color = RED;}else{if (t->p->right == t) //case 2{//将case 2转换为了case 3t = t->p; //这步赋值是为了在转换为case 3时，t指向的是下面的红节点，和case 3的情况相一致leftRotate(tree, t);}//case 3t->p->color = BLACK;t->p->p->color = RED;rightRotate(tree, t->p->p);}}//ifelse//插入节点的父节点本身是right{if (t->p->p->left->color == RED) //case 1{t = t->p->p;t->left->color = t->right->color = BLACK;t->color = RED;}else{if (t->p->left == t) //case 2{//将case 2转换为了case 3t = t->p; //这步赋值是为了在转换为case 3时，t指向的是下面的红节点，和case 3的情况相一致rightRotate(tree, t);}//case 3t->p->color = BLACK;t->p->p->color = RED;leftRotate(tree, t->p->p);}}//else}//whiletree->root->color = BLACK;return0;}int leftRotate (PRBTree tree, PRBTNode t){PRBTNode c; //左旋，c指向t的rightc = t->right;if (t->right == tree->nil) //左旋，t的right不能为空return1;//这个if-else用于将t的父亲节点的left或right点指向c，如果t的父节点为不存在，则树的root指向cif (t->p != tree->nil) //判断t是否为root{if (t->p->left == t) //判断t是t的父节点的left还是rightt->p->left = c;elset->p->right = c;}elsetree->root = c;c->p = t->p; //更新c的父节点t->right = c->left;if (c->left != tree->nil)c->left->p = t;c->left = t;t->p = c;return0;}int rightRotate (PRBTree tree, PRBTNode t){PRBTNode c; //右旋，c指向t的leftc = t->left;if (t->left == tree->nil) //右旋，t的left不能为空return1;//这个if-else用于将t的父亲节点的left或right点指向c，如果t的父节点为不存在，则树的root指向cif (t->p != tree->nil) //判断t是否为root{if (t->p->left == t) //判断t是t的父节点的left还是rightt->p->left = c;elset->p->right = c;}elsetree->root = c;c->p = t->p; //更新c的父节点t->left = c->right;if (c->right != tree->nil)c->right->p = t;c->right = t;t->p = c;return0;}int createRBTree (PRBTree tree, ElemType d[], int n) {//用元素的插入建树int index = -1;int tmp = -1;srand(time(NULL));while (n--){index =(int) rand()%(n+1);//此时共有n+1个数据tmp = d[index];d[index] = d[n];d[n] = tmp;insertRB(tree, d[n]);printf("插入%d\t",d[n]);}puts("");return0;}//createRBTreeint initRB (PRBTree tree){//红黑树的初始化if (tree == NULL)return0;tree->nil = (PRBTNode)malloc(sizeof(RBTNode));tree->nil->color = BLACK;tree->root = tree->nil;return0;}//initRBPRBTNode minimum (PRBTree tree, PRBTNode t){//返回最小值，如果t是NULL返回NULLif (t == tree->nil)return NULL;while (t->left != tree->nil)t = t->left;return t;}//minimumPRBTNode maximum (PRBTree tree, PRBTNode t){//返回最大值，如果t是NULL返回NULLif (t == tree->nil)return NULL;while (t->right != tree->nil)t = t->right;return t;}//maximumPRBTNode next (PRBTree tree, PRBTNode t){//给出t的后继的节点。