【数据结构】红黑树(3)

红黑树节点删除

void
ngx_rbtree_delete(ngx_rbtree_t *tree,ngx_rbtree_node_t *node)
{
    ngx_uint_t           red;
    ngx_rbtree_node_t  **root,*sentinel,*subst,*w;

    /* a binary tree delete */

    root = (ngx_rbtree_node_t **) &tree->root;
    sentinel = tree->sentinel;

    //subst为要替代的节点
    //temp为将要替代节点的孩子
    if (node->left == sentinel) {   //删除节点为左孩子为NIL节点
        temp = node->right;   
        subst = node;

    } else if (node->right == sentinel) {
        temp = node->left;
        subst = node;

    } else {
        subst = ngx_rbtree_min(node->right,sentinel);  //找到以删除节点右孩子为根的最小值节点

        if (subst->left != sentinel) {  
            temp = subst->left;
        } else {                        //通过ngx_rbtree_min找到的，该最小值节点的左孩子一定是NIL
            temp = subst->right;
        }
    }

    if (subst == *root) {  //subst为要删除的节点为根节点时
        *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);    //直接取颜色

    if (subst == subst->parent->left) {   
        subst->parent->left = temp;   //父亲的左孩子指向要删除节点的左孩子

    } else {
        subst->parent->right = temp;  //父亲的右孩子指向要删除节点的右孩子
    }

    if (subst == node) {   //要删除的节点为原始的节点时

        temp->parent = subst->parent;  //父亲节点指向的改变

    } else {

        if (subst->parent == node) {       //通过ngx_rbtree_min一开始就不成立，即node->right的left为NIL节点
            temp->parent = subst;        

        } else {
            temp->parent = subst->parent;    //通过ngx_rbtree_min找到的
        }

        subst->left = node->left;   //指向node的左孩子
        subst->right = node->right; //指向node的右孩子
        subst->parent = node->parent;
        ngx_rbt_copy_color(subst,node);  //将node节点的颜色复制给subst节点

        if (node == *root) {
            *root = subst;    //指向新的根节点

        } else {
            if (node == node->parent->left) {
                node->parent->left = subst;  //改变父亲孩子指向到subst
            } else {
                node->parent->right = subst;
            }
        }

        if (subst->left != sentinel) {    //改变subst孩子的指向
            subst->left->parent = subst;
        }

        if (subst->right != sentinel) {
            subst->right->parent = subst;
        }
    }

    /* DEBUG stuff */
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;

    if (red) {    //如果删除的节点的颜色为红色，直接返回
        return;
    }

    //平衡
    /* a delete fixup */

    //孩子节点，如果孩子节点为黑色时
    while (temp != *root && ngx_rbt_is_black(temp)) {

        if (temp == temp->parent->left) {   //temp为左孩子时
            w = temp->parent->right;    //temp的右兄弟

            //算法导论第三版P186中的情况a
            if (ngx_rbt_is_red(w)) {  //temp的右兄弟为红色时
                ngx_rbt_black(w);     //temp的右兄弟变为黑色
                ngx_rbt_red(temp->parent); //temp的父亲变为红色色
                ngx_rbtree_left_rotate(root,temp->parent);   //以temp->parent左旋转
                w = temp->parent->right;    //新的右兄弟，将会到以下几种情况
            }

            //算法导论第三版P186中的情况b
            //当temp的右兄弟的两个孩子均为黑色时
            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w); //将右兄弟变为红色
                temp = temp->parent;    //将以新的temp进行新的一次循环

            } else {
                //算法导论第三版P186中的情况c
                if (ngx_rbt_is_black(w->right)) {   //如果右兄弟的右孩子是黑色的
                    ngx_rbt_black(w->left);   //w的左孩子变黑
                    ngx_rbt_red(w);           //w变红
                    ngx_rbtree_right_rotate(root,w);   //以w右旋
                    w = temp->parent->right;  //新的右兄弟，直接执行情况c
                }

                //算法导论第三版P186中的情况d
                ngx_rbt_copy_color(w,temp->parent);  //右兄弟变成父亲的颜色
                ngx_rbt_black(temp->parent);  //temp的父亲变黑
                ngx_rbt_black(w->right);      //右兄弟的右孩子变黑
                ngx_rbtree_left_rotate(root,temp->parent);  //以temp的父亲右旋
                temp = *root;  //结束，直接指向根结点
            }

        } else {  //与上述情况相反，做对称操作
            w = temp->parent->left;

            if (ngx_rbt_is_red(w)) {
                ngx_rbt_black(w);
                ngx_rbt_red(temp->parent);
                ngx_rbtree_right_rotate(root,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,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,temp->parent);
                temp = *root;
            }
        }
    }

    //temp为红色时，直接将temp置为黑色
    ngx_rbt_black(temp);
}

（编辑：ASP站长网）