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

/* a sentinel must be black */

#define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)

左旋转和右旋转

//左旋转
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;     //要旋转节点的右孩子p
    node->right = temp->left; //当前节点的右孩子指向改变p的左孩子

    if (temp->left != sentinel) {  //不是NIL节点时
        temp->left->parent = node; //修改父亲的指向
    }

    temp->parent = node->parent;  //p指向要旋转节点的父亲

    if (node == *root) {   //如果当前旋转节点的是根结点，那么根指向要改变
        *root = temp;

    } else if (node == node->parent->left) {  //左孩子时
        node->parent->left = temp;  //新的左孩子

    } else {
        node->parent->right = temp; //新的右孩子
    }

    temp->left = node;   //p的左孩子指向
    node->parent = temp; //父亲改变
}

//右旋转，与上述左边旋转对称
static ngx_inline void
ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,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->parent = temp;
}

红黑树节点插入

void
ngx_rbtree_insert_value(ngx_rbtree_node_t *temp,ngx_rbtree_node_t *sentinel)
{
    //temp为初始时为指向根节点
    
    ngx_rbtree_node_t  **p;

    for ( ;; ) {

        p = (node->key < temp->key) ? &temp->left : &temp->right;  //目标节点的值小于当前节点的值时，向左走即走向左节点，否则向右

        if (*p == sentinel) {   //一直找到该节点的孩子指向的是NIL节点，直接break
            break;
        }

        temp = *p;      //改变方向
    }

    //注意使用地址的地址，才能改变某节点的孩子的指向，否则改变不了
    *p = node;        //该处指向新的节点，*p（某节点的孩子）本来指向sentinel，现在指向node了
    node->parent = temp;
    node->left = sentinel;  //指向NIL
    node->right = sentinel;
    ngx_rbt_red(node);  //插入的节点均为红色
}

void
ngx_rbtree_insert(ngx_rbtree_t *tree,ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  **root,*temp,*sentinel;

    /* a binary tree insert */

    root = (ngx_rbtree_node_t **) &tree->root;  //指向根节点指针的指针，可改变指向根节点指针的指向
    sentinel = tree->sentinel;        //取出NIL节点

    if (*root == sentinel) {         //说明此时红黑树为空
        node->parent = NULL;
        node->left = sentinel;      //指向NIL
        node->right = sentinel;
        ngx_rbt_black(node);        //node节点直接置为黑
        *root = node;               //根节点直接指向该节点

        return;
    }

    tree->insert(*root,node,sentinel);   
    //插入节点，如ngx_rbtree_insert_value(ngx_rbtree_node_t *temp,ngx_rbtree_node_t *sentinel)
    
    /* re-balance tree */

    //红黑树平衡
    
    //当前节点不为根节点，而且当前节点的父亲为红色时
    while (node != *root && ngx_rbt_is_red(node->parent)) {

        if (node->parent == node->parent->parent->left) {   //当前节点的父亲是左节点时
            temp = node->parent->parent->right;    //当前节点的父亲的右兄弟

            //向上转移
            if (ngx_rbt_is_red(temp)) {  
                //对应算法导论第三版P179的情况1
                         
                ngx_rbt_black(node->parent);      //当前节点的父亲变黑
                ngx_rbt_black(temp);              //当前节点的父亲的右兄弟变黑
                ngx_rbt_red(node->parent->parent);//当前节点的父亲的父亲变红
                node = node->parent->parent;      //当前节点变为该当前节点的父亲的父亲

            } else {  //当前节点的父亲的右兄弟为黑色时
            
                //对应算法导论第三版P179的情况2
                
                //当前节点是右节点时，先左旋转
                if (node == node->parent->right) {
                    node = node->parent;   //当节点变为父节点
                    ngx_rbtree_left_rotate(root,sentinel,node);  //当前节点左旋转
                }

                //对应算法导论第三版P179的情况3
                ngx_rbt_black(node->parent);  //当前节点的父亲变为黑色
                ngx_rbt_red(node->parent->parent); //当前节点的父亲的父亲变为黑色
                ngx_rbtree_right_rotate(root,node->parent->parent);  //当前节点父亲的父亲右旋转
            }

        } else {   //相反，对称操作
            temp = node->parent->parent->left;

            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;

            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    ngx_rbtree_right_rotate(root,node);
                }

                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_left_rotate(root,node->parent->parent);
            }
        }
    }

    ngx_rbt_black(*root);  //最后始终着色根结点为黑色
}

（编辑：ASP站长网）