NGINX下红黑树的删除(终章)附GIF（1）：https://developer.aliyun.com/article/1414760
恢复的代码(代码篇)(复杂部分完整版,包含左右旋)
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节点进行处理 ，若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 } //左旋 就是以一个节点p和他的右孩子y为支轴进行，让y成为新的根，p成为y的左孩子，y的左孩子变成p的右孩子。 //右旋类似。 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) //红黑树的左旋 { ngx_rbtree_node_t *temp; //定义一个临时变量 temp = node->right; //获取当前右节点 此时temp就是当前节点的右节点了 node->right = temp->left; ///node的右节点设置为他原来右节点的左节点 if (temp->left != sentinel) { //如果右子结点的左结点不为哨兵 temp->left->parent = node; //右子结点的左子结点挂在左旋结点上 } temp->parent = node->parent; //右节点将会变成原来node的父节点。 if (node == *root) { //是不是根节点的判断 *root = temp; } else if (node == node->parent->left) { //然后把右节点的信息和原来node的parent进行维护 node->parent->left = temp; } else { node->parent->right = temp; } temp->left = node; //现在node变回他原来右节点的子节点了 node->parent = temp; //所以他的parent变成temp } static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) //红黑树的右旋 { ngx_rbtree_node_t *temp; temp = node->left; node->left = temp->right; //左子结点指向原左子结点的右结点 if (temp->right != sentinel) { //如果左子结点的右结点不为哨兵 temp->right->parent = node; //左子结点的右子结点挂在右旋结点上 } temp->parent = node->parent; //左子结点挂在右旋结点的父结点上 if (node == *root) { //如果右旋结点为根节点 *root = temp; //根节点赋为左子结点 } else if (node == node->parent->right) { //如果右旋结点为右子结点 node->parent->right = temp; //左子结点挂父结点右边 } else { //否则左子结点挂父结点左边 node->parent->left = temp; } temp->right = node; //现在node变回他原来左节点的子节点了 node->parent = temp; //所以他的parent变成temp }
gif(太大了,上传不了博主只能上传最次的,要看较好的请点击我的百度网盘进行观看
图片:
博主举得例子也是比较复杂的了，希望大家好好理解，那么相信再去看懂NGINX红黑树部分的源码应该不会在感到无从下手了。
