nginx笔记：红黑树(四)
e_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ root = (ngx_rbtree_node_t **) &tree->root;//获取红黑树容器的根节点 sentinel = tree->sentinel;//获取红黑树容器的哨兵节点(NIL叶节点) if (node->left == sentinel) {//二叉查找树的删除操作都可以归结为删除一个只有只有儿子节点的情况，因为假设删除的节点node有两个儿子， //会从node的左子树找一个最大或者右子树找一个最小的(这两种情形找到的节点假设为m)替代node的位置，然后node在原来m的位置上从而至多只有一个儿子 temp = node->right; subst = node; } else if (node->right == sentinel) {//这一else 和前面的if说明node只有一个儿子 temp = node->left; subst = node; } else {//node有两个儿子需要转换为只有一个儿子的情形 subst = ngx_rbtree_min(node->right, sentinel);//遍历到node->right的最左 //找到node右子树最小(左子树最大也可以，但是nginx实现了ngx_rbtree_min直接调用更加方便)的节点m，交换node和m的位置 if (subst->left != sentinel) {//找到那个非NIL的儿子记为temp temp = subst->left; } else { temp = subst->right; } } //subst是转换后只有一个儿子的节点(若node有两个儿子则subst是node右子树上最小的节点，若node至多只有一个儿子subst==node) if (subst == *root) {//简单情形1: 待删除的节点为根节点且该根节点至多只有一个儿子，只用用根节点的儿子替代根节点并重绘新根为黑色即可,if里面只能是subst==node *root = temp; ngx_rbt_black(temp); /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; return; } red = ngx_rbt_is_red(subst);//是subst为红色则red为1，否则red为0 if (subst == subst->parent->left) {//将subst和其父节点断开连接(subst是最终要删除的节点) subst->parent->left = temp; } else { subst->parent->right = temp; } if (subst == node) {//这是最开始要删除的节点node本身至多只有一个儿子那么subst == node temp->parent = subst->parent;//重连subst的儿子(也是node的儿子)到subst的父节点 } else {//node有两个儿子，那么subst是node右子树最小的节点(右子树最左) if (subst->parent == node) { temp->parent = subst;//该语句感觉没必要，此处空语句即可 } else { temp->parent = subst->parent; } //将subst替换到node的位置上 subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node);//拷贝数据 if (node == *root) {//简单情形2:和简单情形1不同的是，简单情形是node至多只有一个儿子，简单情形2的node有两个儿子，所以执行到了此处 *root = subst;//直接将新根置为subst } else { if (node == node->
parent->left) { node->parent->left = subst; } else { node->parent->right = subst; } } if (subst->left != sentinel) { subst->left->parent = subst; } if (subst->right != sentinel) { subst->right->parent = subst; } } /* DEBUG stuff */ node->left = NULL;//删除node node->right = NULL; node->parent = NULL; node->key = 0; if (red) {//简单情形3：如果subst颜色为红色，删除一个红色节点不会破坏任何性质(注意node和subst位置交换了后删除操作相当于考察的是原来subst所在位置) return; } /* a delete fixup */ //注意此后都是针对temp操作，因为是temp所在路径删除了一个黑色节点(这里是将subst黑色提到了原来node的位置故少了一个黑色节点)，需要对temp重新平衡 while (temp != *root && ngx_rbt_is_black(temp)) {//简单情形4：若temp为红色或者temp是新根，则直接将temp重绘为黑色就行了不用进入循环体 //此后的情形就比前面的几种情形复杂多了，将用case来替代此后出现的情形，现在的问题是temp所在路径少了一个黑色 if (temp == temp->parent->left) {//temp为左二子(右儿子是对称情形) w = temp->parent->right;//找到temp的兄弟w if (ngx_rbt_is_red(w)) {//case2:(注:这里删除操作没有case1直接采用case2是为了和wikipedia保持一致)，对temp父节点左旋转 ngx_rbt_black(w);//左旋后满足w->left == temp->parent, temp->parent->left == node且w为黑色，temp->parent为红色 ngx_rbt_red(temp->parent); ngx_rbtree_left_rotate(root, sentinel, temp->parent); w = temp->parent->right;//temp有了新的兄弟w } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {//case3:temp的兄弟w为黑色，且w的两个儿子都是黑色，将w置为黑色后temp和w的黑色节点数相同了，但是temp->parent可能违反了性质4和5，从而转入temp->parent重新平衡 ngx_rbt_red(w); temp = temp->parent;//注意这里已经包括了wikipedia上的case4，即temp->parent红色的话退出while循环直接将其重绘为黑色 } else {//w的左儿子和右儿子颜色不同 if (ngx_rbt_is_black(w->right)) {//case5:w的右儿子为黑色，w的左儿子必为红色，重绘w->right为黑色，并对w进行右旋然后进入case6 ngx_r