#define RBTREE_RED 0 #define RBTREE_BLACK 1 typedef int dataType; typedef struct treeNode{ dataType key; int color; //red:0 black:1 struct treeNode *left; struct treeNode *right; struct treeNode *parent; }RBTree, *PRBTree; static PRBTree RBT_Search(dataType key, PRBTree root, PRBTree* save) { PRBTree node = root, parent = NULL; while (node) parent = node; if (node->key > key) node = node->left; else if (node->key < key) node = node->right; else return node; } if (save) *save = parent; return NULL;

// 左旋函数 static PRBTree leftRotate(PRBTree x , PRBTree root) { // x 为旋转点 PRBTree y = x->right; // 令y为旋转点的右子节点 x->right = y->left; if(y->left) y->left->parent = x; // 别忘了设定父节点 y->parent = x->parent; // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来） if(x == root) // x为根节点 root = y; else if(x == x->parent->left) // x为其父节点的左子节点 x->parent->left = y; else // x为其父节点的右子节点 x->parent->right = y; y->left = x; x->parent = y; return root; }

// 右旋函数 static PRBTree rightRotate(PRBTree x , PRBTree root) { // x 为旋转点 PRBTree y = x->left; // 令y为旋转点的左子节点 x->left = y->right; if(y->right) y->right->parent = x; // 别忘了设定父节点 y->parent = x->parent; // 令y完全顶替x的地位（必须将x对其父节点的关系完全接收过来） if(x == root) root = y; else if(x == x->parent->right) // x为其父节点的右子节点 x->parent->right = y; else // x为其父节点的左子节点 x->parent->left = y; y->right = x; x->parent = y; return root; }

//红黑树的插入结点 PRBTree RBInsert(dataType key, PRBTree root) { PRBTree parent = NULL, node; if ((node = RBT_Search(key, root, &parent))) //找到插入结点的地方 return root; node = (PRBTree)malloc(sizeof(RBTree)); //分配结点 node->parent = parent; node->left = node->right = NULL; node->color = RBTREE_RED; node->key = key; if (parent) if (parent->key > key) parent->left = node; else parent->right = node; } else root = node; return RBInsert_Rebalance(node, root); //插入结点后，修复红黑树的性质

static PRBTree RBInsert_Rebalance(PRBTree x, PRBTree root) { x->color = RBTREE_RED; //新节点必为红 while(x != root && x->parent->color == RBTREE_RED) // 父节点为红 if(x->parent == x->parent->parent->left) // 父节点为祖父节点之左子节点 PRBTree y = x->parent->parent->right; // 令y为伯父节点 if(y && y->color == RBTREE_RED) // 伯父节点存在，且为红 x->parent->color = RBTREE_BLACK; // 更改父节点为黑色 y->color = RBTREE_BLACK; // 更改伯父节点为黑色 x->parent->parent->color = RBTREE_RED; x = x->parent->parent; } else // 无伯父节点，或伯父节点为黑色 if(x == x->parent->right) // 新节点为父节点之右子节点 x = x->parent; root = leftRotate(x , root); // 左旋 x->parent->color = RBTREE_BLACK; // 改变颜色 root = rightRotate(x->parent->parent , root); // 右旋点

else // 父节点为祖父节点之右子节点 { PRBTree y = x->parent->parent->left; // 令y为伯父节点 if(y && y->color == RBTREE_RED) // 有伯父节点，且为红 x->parent->color = RBTREE_BLACK; // 父节点为黑色 y->color = RBTREE_BLACK; // 更改伯父节点为黑色 x->parent->parent->color = RBTREE_RED x = x->parent->parent; // 准备继续往上层检查 } else // 无伯父节点，或伯父节点为黑色 if(x == x->parent->left) //新节点为父节点之左子节点 x = x->parent; root = rightRotate(x , root); // 右旋点 x->parent->color = RBTREE_BLACK; // 改变颜色 x->parent->parent->color = RBTREE_RED; root = leftRotate(x->parent->parent , root); // 左旋点 }//while root->color = RBTREE_BLACK; // 根节点永远为黑色 return root;

PRBTree RBErase(dataType key, PRBTree root) //红黑树的删除结点 { PRBTree child, parent, old, left, node; int color; if (!(node = RBT_Search(key, root, NULL))) 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) {//将node结点断链，node结点的父节点的左右儿子指针指向其右儿子 if (parent->left == node) //如果要删除的结点是父节点的左儿子 parent->left = child; else parent->right = child; //如果要删除的结点是父节点的左儿子 } else root = child; if (node->parent == old) parent = node; //将node结点取代old结点 node->parent = old->parent; node->color = old->color; node->right = old->right; node->left = old->left;

if (old->parent)//将old结点断链 { 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 == RBTREE_BLACK) root = RBErase_Rebalance(child, parent, root); //恢复红黑树 return root;

//红黑树修复删除的4种情况 PRBTree RBErase_Rebalance(PRBTree node, PRBTree parent, PRBTree root) { //x表示要删除的结点，other、w表示兄弟结点， PRBTree other, o_left, o_right; //x的兄弟other，兄弟左孩子o_left,o_right while ((!node || node->color == RBTREE_BLACK) && node != root) if (parent->left == node) { other = parent->right; if (other->color == RBTREE_RED) { //情况1：x的兄弟w是红色的 other->color = RBTREE_BLACK; parent->color = RBTREE_RED; //w->黑、p[x]->红。 root = leftRotate(parent, root); //再对p[x]做一次左旋 other = parent->right; //x的新兄弟new w 是旋转之前w的某个孩子。其实就是左旋后的效果。 } if ((!other->left || other->left->color == RBTREE_BLACK) && (!other->right || other->right->color == RBTREE_BLACK)) { //情况2：x的兄弟w是黑色，且w的俩个孩子也都是黑色的 other->color = RBTREE_RED; //于是，兄弟w变为红色。 node = parent; //p[x]为新结点x parent = node->parent; //x<-p[x] else { //情况3：x的兄弟w是黑色的，且w的左孩子是红色，右孩子为黑色。 if (!other->right || other->right->color == RBTREE_BLACK){ if ((o_left = other->left)) o_left->color = RBTREE_BLACK; //w和其左孩子，颜色交换。 other->color = RBTREE_RED; //w由黑->红 root = rightRotate(other, root); //再对w进行右旋，从而红黑性质恢复。 other = parent->right; //变化后的，父结点的右孩子，作为新的兄弟结点w。

//情况4：x的兄弟w是黑色的 other->color = parent->color; //把兄弟节点染成当前节点父节点的颜色。 parent->color = RBTREE_BLACK; //把当前节点父节点染成黑色 if (other->right) //且w的右孩子是红 other->right->color = RBTREE_BLACK; //兄弟节点w右孩子染成黑色 root = leftRotate(parent, root); //并再做一次左旋 node = root; //并把x置为根。 break; } else{//下述情况与上述情况，原理一致。 other = parent->left; if (other->color == RBTREE_RED) { other->color = RBTREE_BLACK; parent->color = RBTREE_RED; root = rightRotate(parent, root); if ((!other->left || other->left->color == RBTREE_BLACK) && (!other->right || other->right->color == RBTREE_BLACK)) { other->color = RBTREE_RED; node = parent; parent = node->parent;

else { if (!other->left || other->left->color == RBTREE_BLACK) if ((o_right = other->right)) o_right->color = RBTREE_BLACK; other->color = RBTREE_RED; root = leftRotate(other, root); other = parent->left; } other->color = parent->color; parent->color = RBTREE_BLACK; if (other->left) other->left->color = RBTREE_BLACK; root = rightRotate(parent, root); node = root; break; if (node) node->color = RBTREE_BLACK; //最后将node[上述步骤置为了根结点]，改为黑色。 return root; //返回root