接着上一篇我们就只剩下了红黑树的删除了,这也是较为复杂的操作(原理一套gif(只是简单部分),代码两套gif(困难部分博主会从头讲到尾)),因为删除操作比较复杂,所以博主打算简单一套,复杂一套,希望大家看了博主的博客以后不要在惧怕红黑树了!!!
由于GIF大小有限制所以想要看比较清楚的可以点击下面的连接进行观看。
博主为了让大家认识更清楚所以在每套GIF都会给出代码(虽然会显得比较冗长,但是你能坚持看下来的效果一定是非常好的!)
其实删除的话我们是分为两个部分
(1)删除
(2)恢复
删除:
当你要删除一个点的时候又分为下面的情况 删除时候的情况： 1. 如果要被删除的节点没有孩子，那么就直接删除。 2. 如果删除的节点有一个孩子，删除之后，用它的孩子还代替他。 3. 如果有两个孩子，这个时候你可以选择左孩子那条路径里最大的值，或者右孩子最小的值来进行删除，然后这个孩子去替代原来节点的位置 (NGINX是选择用右孩子的最小值来进行删除)。以这个结点的键与值（key与value/data）替换待删结点的键与值，然后删除这个替身
删除操作总体来说很简单，就是要保证被删除的节点只有一个或者没有孩子就行了。
恢复
恢复主要分为几种情况（如果是红色，就直接返回，因为没有影响到红黑树的性质 删除后，被删除的节点的孩子会顶替到删除节点的位置，孩子节点我们记为temp因为恢复操作就是围绕着temp来进行的）咱们只讨论左孩子，右孩子镜像。
1.如果temp的兄弟节点w为红色。那么他们的父亲节点为黑色
处理办法：把w弄成黑色，把parent弄成红色进行一次左旋，然后将情况转换为后面一种已知的情况 然后将temp指向temp的兄弟。
2.如果temp的兄弟w为黑色，这个时候他们的父亲节点就可红可黑了，因为temp这条路径是比他兄弟那条路径少一个黑色的节点，
如果这个时候他兄弟节点w的两个孩子都是黑色的，那么咱们就直接把w节点设置为红色，这个时候两个兄弟节点的黑色数量一样，但是w parent这条路劲上的黑色节点少一个所以指向w的parent继续循环。
3.如果temp的兄弟节点w为黑色，并且他的右孩子也是黑色，左孩子为红色，那么我们就将w的左孩子设置为黑色，把设置为红色，并且以w进行一次右旋，转换为情况4.
4.如果temp的兄弟节点w为黑色，并且他的左孩子为黑色，右孩子为红色，这时候就把w的颜色设置为parent的颜色，parent设置为黑色，w的右孩子设置为黑色，然后以parent为节点进行右旋，恢复红黑树的性质。
下面我们就只给出删除的代码:
//红黑树的删除!!!!! //据说红黑树和AVL树的区别主要体现在删除节点时，我们就来看一看。 void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_uint_t red; ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ root = &tree->root; //树根指针的指针赋给了root sentinel = tree->sentinel; //哨兵指针赋给了哨兵指针 /* 下面是获取temp节点值，temp保存的节点是准备替换节点node ； * subst是保存要被替换的节点的后继节点； */ /* case1：若node节点没有左孩子（这里包含了存在或不存在右孩子的情况）*/ if (node->left == sentinel) { //如果左子结点是哨兵或左右子结点都是哨兵 temp = node->right; //获得右子结点，后面让它接替node位置 subst = node; //node赋给subst } /* case2：node节点存在左孩子，但是不存在右孩子 */ else if (node->right == sentinel) { //如果右子结点是哨兵 temp = node->left; //获得左子结点，后面让它接替node位置 subst = node; //node赋给subst /* case3：node节点既有左孩子，又有右孩子 */ } else { //如果左右子结点都不是哨兵 /* 获取node节点的后续节点 */ subst = ngx_rbtree_min(node->right, sentinel); //获得右子树中最小的结点---->头结点里面有一个内联函数来着 if (subst->left != sentinel) { //如果右子树的最小结点的左子结点不是哨兵,基本上会不执行这条语句 temp = subst->left; //获得右子树的最小结点的左子结点 } else { //否则获得右子树最小结点的右子结点 temp = subst->right; //看起来subst将被从原位置删掉然后接替node的位置 } } //下面我们来看看temp和subst要干什么用： /* 若被替换的节点subst是根节点，则temp直接替换subst成为根节点 */ if (subst == *root) { //如果subst是根 --->//真正删除的节点是根节点 *root = temp; //temp接替根 ngx_rbt_black(temp); //染黑temp /* DEBUG stuff */ node->left = NULL; //清空了待删结点 node->right = NULL; node->parent = NULL; node->key = 0; return; } //将我们的后继节点从书上脱离出来 /* red记录subst节点的颜色 */ red = ngx_rbt_is_red(subst); //获得subst是否是红色 /* temp节点替换subst 节点 */ if (subst == subst->parent->left) { //如果subst是左子结点 subst->parent->left = temp; //把接替结点挂到subst位置 } else { //如果subst是右子结点 subst->parent->right = temp; //把接替结点挂到subst位置 } /* 根据subst是否为node节点进行处理 */ if (subst == node) { //如果subst是待删结点--->//需要删除的节点是本身 temp->parent = subst->parent; //接替结点直接接替，删除完成 } else { //如果subst不是待删结点 if (subst->parent == node) { //如果subst的父结点就是待删结点 temp->parent = subst; //接替结点挂在subst上 } else { {//如果待删结点比subst的父结点更高 temp->parent = subst->parent; //把接替结点挂在subst的父结点上 -->//常规情况 } /* 复制node节点属性 */ //subst接替待删结点node的位置，复制待删结点跟周围结点的关系 --->把node的信息拷贝到subst里面去 subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node); if (node == *root) { //如果是root节点 //如果待删结点是根 *root = subst; //subst接替根 } else { //如果待删结点不是根，subst接替它 -->维护父子信息 if (node == node->parent->left) { node->parent->left = subst; } else { node->parent->right = subst; } } //这里就是将node完全脱离我们的红黑树了 if (subst->left != sentinel) { //如果subst左子结点不是哨兵 subst->left->parent = subst; //subst的左子结点放弃node，挂上来 } if (subst->right != sentinel) { //如果subst右子结点不是哨兵 subst->right->parent = subst; //subst右子结点放弃node，挂上来 } } //清空待删结点node /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; //如果subst是红色，红黑树约束依然被遵守，删除工作就可以结束了 if (red) { return; } /* 下面开始是调整红黑树的性质 */ //看起来结点的删除过程已经顺利完成了，但是如果subst是黑色，我们需要修复红黑树的约束。 //下面这一段代码的主角是接替subst位置的temp结点： /* a delete fixup */ //当subst的接替结点不是根且为黑色，循环 /* 根据temp节点进行处理 ，若temp不是根节点且为黑色 */ while (temp != *root && ngx_rbt_is_black(temp)) { /* 若temp是其父亲节点的左孩子 */ if (temp == temp->parent->left) { //如果temp是左子结点 w = temp->parent->right; //获得其右兄弟 /* w为temp的兄弟节点 */ /* case A：temp兄弟节点为红色 */ /* 解决办法： * 1、改变w节点及temp父亲节点的颜色； * 2、对temp父亲节的做一次左旋转，此时，temp的兄弟节点是旋转之前w的某个子节点，该子节点颜色为黑色； * 3、此时，case A已经转换为case B、case C 或 case D； */ if (ngx_rbt_is_red(w)) { //如果temp的右兄弟是红色 ngx_rbt_black(w); //染黑temp的右兄弟 ngx_rbt_red(temp->parent); //染红temp的父结点 ngx_rbtree_left_rotate(root, sentinel, temp->parent); //temp的父结点左旋 w = temp->parent->right; //获得temp的新右兄弟 } /* case B：temp的兄弟节点w是黑色，且w的两个子节点都是黑色 */ /* 解决办法： * 1、改变w节点的颜色； * 2、把temp的父亲节点作为新的temp节点； */ if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { //如果temp右兄弟的左右子结点都是黑的 ngx_rbt_red(w); //染红temp的右兄弟 temp = temp->parent; //获得temp的父结点为新temp } else { //如果temp右兄弟的子结点不全为黑 /* case C：temp的兄弟节点是黑色，且w的左孩子是红色，右孩子是黑色 */ /* 解决办法： * 1、将改变w及其左孩子的颜色； * 2、对w节点进行一次右旋转； * 3、此时，temp新的兄弟节点w有着一个红色右孩子的黑色节点，转为case D； */ if (ngx_rbt_is_black(w->right)) { //如果其右子结点是黑色 ngx_rbt_black(w->left); //染黑左子结点 ngx_rbt_red(w); //染红temp的右兄弟 ngx_rbtree_right_rotate(root, sentinel, w); //右兄弟右旋 w = temp->parent->right; //获得temp的新右兄弟 } /* case D：temp的兄弟节点w为黑色，且w的右孩子为红色 */ /* 解决办法： * 1、将w节点设置为temp父亲节点的颜色，temp父亲节点设置为黑色； * 2、w的右孩子设置为黑色； * 3、对temp的父亲节点做一次左旋转； * 4、最后把根节点root设置为temp节点；*/ ngx_rbt_copy_color(w, temp->parent); //temp右兄弟复制temp父结点颜色 ngx_rbt_black(temp->parent); //染黑temp父结点 ngx_rbt_black(w->right); //染黑temp右兄弟的右子结点 ngx_rbtree_left_rotate(root, sentinel, temp->parent); //temp父结点左旋 temp = *root; //获得根 } /* 这里针对的是temp节点为其父亲节点的左孩子的情况 */ } else{//如果temp是右子结点，做对称的事 w = temp->parent->left; if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); ngx_rbtree_right_rotate(root, sentinel, temp->parent); w = temp->parent->left; } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { ngx_rbt_red(w); temp = temp->parent; } else { if (ngx_rbt_is_black(w->left)) { ngx_rbt_black(w->right); ngx_rbt_red(w); ngx_rbtree_left_rotate(root, sentinel, w); w = temp->parent->left; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->left); ngx_rbtree_right_rotate(root, sentinel, temp->parent); temp = *root; } } } ngx_rbt_black(temp); //染黑当前temp }
如果大家感觉文字解释依然不好理解的话,博主依然给大家做了 NGINX红黑树的删除gif(分为两个部分,比较简单的,和复杂的情况)
下面我们还是将删除分为我们之前所说的两个部分吧。
删除部分的代码(原理篇)简单部分(删除红色节点,不需要恢复)
//红黑树的删除!!!!! //据说红黑树和AVL树的区别主要体现在删除节点时，我们就来看一看。 void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_uint_t red; ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ root = &tree->root; //树根指针的指针赋给了root sentinel = tree->sentinel; //哨兵指针赋给了哨兵指针 /* 下面是获取temp节点值，temp保存的节点是准备替换节点node ； * subst是保存要被替换的节点的后继节点； */ /* case1：若node节点没有左孩子（这里包含了存在或不存在右孩子的情况）*/ if (node->left == sentinel) { //如果左子结点是哨兵或左右子结点都是哨兵 temp = node->right; //获得右子结点，后面让它接替node位置 subst = node; //node赋给subst } /* case2：node节点存在左孩子，但是不存在右孩子 */ else if (node->right == sentinel) { //如果右子结点是哨兵 temp = node->left; //获得左子结点，后面让它接替node位置 subst = node; //node赋给subst /* case3：node节点既有左孩子，又有右孩子 */ } else { //如果左右子结点都不是哨兵 /* 获取node节点的后续节点 */ subst = ngx_rbtree_min(node->right, sentinel); //获得右子树中最小的结点---->头结点里面有一个内联函数来着 if (subst->left != sentinel) { //如果右子树的最小结点的左子结点不是哨兵,基本上会不执行这条语句 temp = subst->left; //获得右子树的最小结点的左子结点 } else { //否则获得右子树最小结点的右子结点 temp = subst->right; //看起来subst将被从原位置删掉然后接替node的位置 } } //下面我们来看看temp和subst要干什么用： /* 若被替换的节点subst是根节点，则temp直接替换subst成为根节点 */ if (subst == *root) { //如果subst是根 --->//真正删除的节点是根节点 *root = temp; //temp接替根 ngx_rbt_black(temp); //染黑temp /* DEBUG stuff */ node->left = NULL; //清空了待删结点 node->right = NULL; node->parent = NULL; node->key = 0; return; } //将我们的后继节点从书上脱离出来 /* red记录subst节点的颜色 */ red = ngx_rbt_is_red(subst); //获得subst是否是红色 /* temp节点替换subst 节点 */ if (subst == subst->parent->left) { //如果subst是左子结点 subst->parent->left = temp; //把接替结点挂到subst位置 } else { //如果subst是右子结点 subst->parent->right = temp; //把接替结点挂到subst位置 } /* 根据subst是否为node节点进行处理 */ if (subst == node) { //如果subst是待删结点--->//需要删除的节点是本身 temp->parent = subst->parent; //接替结点直接接替，删除完成 } else { //如果subst不是待删结点 if (subst->parent == node) { //如果subst的父结点就是待删结点 temp->parent = subst; //接替结点挂在subst上 } else { {//如果待删结点比subst的父结点更高 temp->parent = subst->parent; //把接替结点挂在subst的父结点上 -->//常规情况 } /* 复制node节点属性 */ //subst接替待删结点node的位置，复制待删结点跟周围结点的关系 --->把node的信息拷贝到subst里面去 subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node); if (node == *root) { //如果是root节点 //如果待删结点是根 *root = subst; //subst接替根 } else { //如果待删结点不是根，subst接替它 -->维护父子信息 if (node == node->parent->left) { node->parent->left = subst; } else { node->parent->right = subst; } } //这里就是将node完全脱离我们的红黑树了 if (subst->left != sentinel) { //如果subst左子结点不是哨兵 subst->left->parent = subst; //subst的左子结点放弃node，挂上来 } if (subst->right != sentinel) { //如果subst右子结点不是哨兵 subst->right->parent = subst; //subst右子结点放弃node，挂上来 } } //清空待删结点node /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; //如果subst是红色，红黑树约束依然被遵守，删除工作就可以结束了 if (red) { return; }
GIF
图片
删除部分的代码(代码篇)简单部分(删除红色节点,不需要恢复)
//红黑树的删除!!!!! //据说红黑树和AVL树的区别主要体现在删除节点时，我们就来看一看。 void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { ngx_uint_t red; ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ root = &tree->root; //树根指针的指针赋给了root sentinel = tree->sentinel; //哨兵指针赋给了哨兵指针 /* 下面是获取temp节点值，temp保存的节点是准备替换节点node ； * subst是保存要被替换的节点的后继节点； */ /* case1：若node节点没有左孩子（这里包含了存在或不存在右孩子的情况）*/ if (node->left == sentinel) { //如果左子结点是哨兵或左右子结点都是哨兵 temp = node->right; //获得右子结点，后面让它接替node位置 subst = node; //node赋给subst } /* case2：node节点存在左孩子，但是不存在右孩子 */ else if (node->right == sentinel) { //如果右子结点是哨兵 temp = node->left; //获得左子结点，后面让它接替node位置 subst = node; //node赋给subst /* case3：node节点既有左孩子，又有右孩子 */ } else { //如果左右子结点都不是哨兵 /* 获取node节点的后续节点 */ subst = ngx_rbtree_min(node->right, sentinel); //获得右子树中最小的结点---->头结点里面有一个内联函数来着 if (subst->left != sentinel) { //如果右子树的最小结点的左子结点不是哨兵,基本上会不执行这条语句 temp = subst->left; //获得右子树的最小结点的左子结点 } else { //否则获得右子树最小结点的右子结点 temp = subst->right; //看起来subst将被从原位置删掉然后接替node的位置 } } //下面我们来看看temp和subst要干什么用： /* 若被替换的节点subst是根节点，则temp直接替换subst成为根节点 */ if (subst == *root) { //如果subst是根 --->//真正删除的节点是根节点 *root = temp; //temp接替根 ngx_rbt_black(temp); //染黑temp /* DEBUG stuff */ node->left = NULL; //清空了待删结点 node->right = NULL; node->parent = NULL; node->key = 0; return; } //将我们的后继节点从书上脱离出来 /* red记录subst节点的颜色 */ red = ngx_rbt_is_red(subst); //获得subst是否是红色 /* temp节点替换subst 节点 */ if (subst == subst->parent->left) { //如果subst是左子结点 subst->parent->left = temp; //把接替结点挂到subst位置 } else { //如果subst是右子结点 subst->parent->right = temp; //把接替结点挂到subst位置 } /* 根据subst是否为node节点进行处理 */ if (subst == node) { //如果subst是待删结点--->//需要删除的节点是本身 temp->parent = subst->parent; //接替结点直接接替，删除完成 } else { //如果subst不是待删结点 if (subst->parent == node) { //如果subst的父结点就是待删结点 temp->parent = subst; //接替结点挂在subst上 } else { {//如果待删结点比subst的父结点更高 temp->parent = subst->parent; //把接替结点挂在subst的父结点上 -->//常规情况 } /* 复制node节点属性 */ //subst接替待删结点node的位置，复制待删结点跟周围结点的关系 --->把node的信息拷贝到subst里面去 subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node); if (node == *root) { //如果是root节点 //如果待删结点是根 *root = subst; //subst接替根 } else { //如果待删结点不是根，subst接替它 -->维护父子信息 if (node == node->parent->left) { node->parent->left = subst; } else { node->parent->right = subst; } } //这里就是将node完全脱离我们的红黑树了 if (subst->left != sentinel) { //如果subst左子结点不是哨兵 subst->left->parent = subst; //subst的左子结点放弃node，挂上来 } if (subst->right != sentinel) { //如果subst右子结点不是哨兵 subst->right->parent = subst; //subst右子结点放弃node，挂上来 } } //清空待删结点node /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; //如果subst是红色，红黑树约束依然被遵守，删除工作就可以结束了 if (red) { return; }
GIF：（实在是不行，所以只有传小图了！！！）
图片:
虽然博主上面说的是 简单的,但是也是给大家选的有两个分支进行删除,这也是为了我们后面复杂部分而准备的,复杂部分的删除和我们之前的是一样的(复杂的删除掌握了,简单的应该是没问题的),所以我们在复杂片就给出大家恢复的策略!!!
恢复(按照小曼四步执行,即可恢复红黑树)
恢复主要分为几种情况（如果是红色，就直接返回，因为没有影响到红黑树的性质 删除后，被删除的节点的孩子会顶替到删除节点的位置(其实就是我们要后继节点(右子树的最小值))，孩子节点我们记为temp因为恢复操作就是围绕着temp来进行的）咱们只讨论左孩子，右孩子镜像。
下面是要被删除节点的结点是黑色的情况：
1.如果temp的兄弟节点w为红色。那么他们的父亲节点为黑色
处理办法：把w弄成黑色，把parent弄成红色进行一次左旋，然后将情况转换为后面一种已知的情况 然后将temp指向temp的兄弟。
2.如果temp的兄弟w为黑色，这个时候他们的父亲节点就可红可黑了，因为temp这条路径是比他兄弟那条路径少一个黑色的节点，
如果这个时候他兄弟节点w的两个孩子都是黑色的，那么咱们就直接把w节点设置为红色，这个时候两个兄弟节点的黑色数量一样，但是w parent这条路劲上的黑色节点少一个所以指向w的parent继续循环。
3.如果temp的兄弟节点w为黑色，并且他的右孩子也是黑色，左孩子为红色，那么我们就将w的左孩子设置为黑色，把设置为红色，并且以w进行一次右旋，转换为情况4.
4.如果temp的兄弟节点w为黑色，并且他的左孩子为黑色，右孩子为红色，这时候就把w的颜色设置为parent的颜色，parent设置为黑色，w的右孩子设置为黑色，然后以parent为节点进行右旋，恢复红黑树的性质。
那我们就按照复杂的情况来恢复吧。
NGINX下红黑树的删除(终章)附GIF（2）https://developer.aliyun.com/article/1414761?spm=a2c6h.13148508.setting.29.4d4d4f0erzCTC6
