红黑树删除时的情况 由于红黑数是有序树，当删除红黑色的一个结点时，用它的后继结点(也可以是前驱结点)来代替它，然后去删除它的后继结点(或者前驱结点)。后继结点是右子树中值最小的结点(前驱结点是左子树中值最大的结点)。可以知道，后继结点一定没有左子树(前驱结点一定没有右子树)，所以，当在红黑树中删除一个结点时，只会有以下两种情况： 1.删除的结点只有一个孩子 2.删除的是叶子结点
情况1 此时，要删除的结点(N)只有一个孩子(可以是左孩子(NL)，也可以是右孩子(NR))，由红黑树的性质，可以知道，N一定是黑色，这个唯一的孩子一定是红色。直接将N删除，然后用N的唯一的孩子结点去代替N，再将N染黑既可。 情况2 此时，删除的结点(N)是叶子结点，如果N是红色，直接删除既可。 如果N是黑色，由红黑树的性质，它一定存在一个兄弟结点B，在删除N后，需要调节树，使其重新成为一个红黑树，在调节过程中，需要关注N的兄弟结点B的颜色。 情况如下： N为黑，N一定有兄弟结点B @ ——N为左孩子 ———— B红 —————— B是红的，此时N和B的父亲结点§一定是黑的，且B一定存在两个黑色的孩子结点。将B染黑、P染红，以P左旋，然后更新B(B=P->right)，此时B为黑 ———— B黑 —————— B没有红色孩子结点 ———————— P红 —————————— 此时，将B染红、P染黑，即完成 ———————— P黑 —————————— 将B染红，使N=P，P=N->parent，此时N为黑，回到@的地方继续判断 —————— B的左孩子(BL)红 ———————— B染红、BL染黑，以B右旋，更新B(B=P->right) —————— B的右孩子(BR)红 ———————— B染成P的颜色、P染黑、BR染黑，以P左旋，此时完成 ——N为右孩子 ———— B红 —————— B是红的，此时N和B的父亲结点§一定是黑的，且B一定存在两个黑色的孩子结点。将B染黑、P染红，以P右旋，然后更新B(B=P->left)，此时B为黑 ———— B黑 —————— B没有红色孩子结点 ———————— P红 —————————— 此时，将B染红、P染黑，即完成 ———————— P黑 —————————— 将B染红，使N=P，P=N->parent，此时N为黑，回到@的地方继续判断 —————— B的右孩子(BR)红 ———————— B染红、BR染黑，以B左旋，更新B(B=P->left) —————— B的左孩子(BL)红 ———————— B染成P的颜色、P染黑、BL染黑，以P右旋，此时完成
代码
//node路径上少了一个黑色节点 node是parent的左或者右，函数开始调用的时候node=NULL void rbtree_delete_repair(RBTree *ptree,RBNode *node,RBNode *parent){ while((node==NULL||node->col==BLACK)&&node!=*ptree){ //node为NULL是因为调用函数开始之前，node为黑色叶结点且已被删除；node不为NULL且为黑是在调整平衡的过程中产生的情况；如果node是根节点，那么就不需要调整了 if(node == parent->left){ //node节点在左边 RBNode *brother = parent->right; if(brother->col == RED){ //兄弟节点为红 brother->col = BLACK; parent->col = RED; left_rotation(ptree,parent); //旋转的代码在之前的博客中(红黑树的插入操作) } brother = parent->right; //更新兄弟节点 //兄弟节点为黑，兄弟节点不存在红色子节点 if(!((brother->left!=NULL&&brother->left->col==RED)||(brother->right!=NULL&&brother->right->col==RED))){ brother->col = RED; if(parent->col == RED){ //父亲为红 parent->col = BLACK; return; //完成了 } //父亲为黑 node = parent; parent = node->parent; continue; } //兄弟节点有红色子节点 brother = parent->right; if(brother->right == NULL || brother->right->col==BLACK){ //这里兄弟左孩子为红，右孩子不存在或为黑 brother->col = RED; brother->left->col = BLACK; right_rotation(ptree,brother); } brother = parent->right; //兄弟的右节点为红色 brother->col = parent->col; parent->col = BLACK; brother->right->col = BLACK; left_rotation(ptree,parent); }else{//node节点在右边 RBNode *brother = parent->left; if(brother->col == RED){ //兄弟红 brother->col = BLACK; parent->col = RED; right_rotation(ptree,parent); } brother = parent->left; //兄弟为黑色，且兄弟结点没有红色的子节点 if(!((brother->left!=NULL&&brother->left->col==RED)||(brother->right!=NULL&&brother->right->col==RED))){ brother->col = RED; if(parent->col == RED){ //父亲红 parent->col = BLACK; return; } //父亲黑 node = parent; parent = node->parent; continue; } //兄弟有红色的右节点 brother = parent->left; if(brother->left==NULL || brother->left->col==BLACK){ brother->col = RED; brother->right->col = BLACK; left_rotation(ptree,brother); } brother = parent->left; //兄弟节点的左节点为红色 brother->col = parent->col; parent->col = BLACK; brother->left->col = BLACK; right_rotation(ptree,parent); break; } } (*ptree)->col = BLACK; //红黑树根节点必须是黑色 } //在查找到需要删除的节点node后，将其删除 void rbtree_delete_rbnode(RBTree *ptree,RBNode *node){ RBNode *left = node->left; RBNode *right = node->right; if(left == NULL && right == NULL){//叶子结点 if(node == *ptree){//删除的是根节点 *ptree = NULL; free(node); return; } //node为叶子节点 删除 RBNode *parent = node->parent; if(node == node->parent->left){ node->parent->left = NULL; }else{ node->parent->right = NULL; } char col = node->col; free(node); if(col == BLACK){//叶子节点是一个黑色节点，删除后需要平衡 rbtree_delete_repair(ptree,NULL,parent); } }else if(left != NULL && right != NULL){//左右都在 //转化成删除左子树最大节点 或者 右子树最小节点 while(right->left != NULL){ right = right->left; } node->data= right->data; rbtree_delete_rbnode(ptree,right); }else{//要删除的节点只有一个孩子 RBNode *tree = left!=NULL?left:right; tree->col = BLACK; if(node->parent == NULL){//删除的是根节点 *ptree = tree; }else{ if(node == node->parent->left){ node->parent->left = tree; }else{ node->parent->right = tree; } } free(node); } } //按值删除节点 int rbtree_delete(RBTree *ptree,T data,int (*compar)(T,T)){ RBTree *proot = ptree; while(*ptree != NULL){ int ret = compar(data,(*ptree)->data); if(ret == 0){ rbtree_delete_rbnode(proot,*ptree); return 0; }else if(ret < 0){ ptree = &(*ptree)->left; }else{ ptree = &(*ptree)->right; } } return -1; }