红黑树实现

1、五个性质

(1）根节点黑色

(2) 只有红色和黑色节点

(3) 红色节点相邻节点黑色

(4) 每个节点到任意子树叶子节点黑色节点个数相同

(5) 叶子节点黑色

2、插入

插入节点颜色为红色

(1) 根节点为null 直接赋值

(2) 插入节点父亲节点为黑色结束

(3) 插入节点父亲节点颜色为红色

1、叔叔节点颜色为红色

                 b               r           
                / \             / \
               r   r    ->     b   b
              /               / 
            (r)             (r)      

2、叔叔节点为黑色

                    b             b
                   / \           / \
                  r   b  ->   (r)   r
                 /                   \
               (r)                    b
or
                       b             b
                      / \           / \
                     r   b  ->    (r)  b
                      \           /
                      (r)        r
                

我的实现

if (rt->color == RED && par->color == RED) {
        Node *grand = par->parent;
        bool fc = (grand->ch[1] == par);
        Node *uncle = grand->ch[fc ^ 1];

        /*
         *        b               r
         *       / \             / \
         *      r   r    ->     b   b
          *    /               /
         *   (r)             (r)
         *
         */

        if (uncle->color == RED) {
            uncle->color = par->color = BLACK;
            grand->color = RED;
        } else {
            bool c = (par->ch[1] == rt);

            /**
             *       b             b
             *      / \           / \
             *     r   b  ->   (r)   r
             *    /                   \
             *  (r)                    b
             */
            if (c == fc) {
                par->color = BLACK;
                grand->color = RED;
                rotate(par);
            } else {
                /**
                 *      b             b
                 *     / \           / \
                 *    r   b  ->    (r)  b
                 *     \           /
                 *     (r)        r
                 */
                rotate(rt);
                pushUp(rt->ch[c ^ 1]);
            }
        }
    } 

3、删除

找到前继节点或者后继节点，颜色不变，值互换下，然后开始删前继或者后继节点，这个时候删除其实有9种情况

(1) 根节点直接删

(2) 红色节点直接删

(3) 删除节点父亲节点为红色，父亲变黑

(4) 子节为红色的，变黑

然后就是红黑树里面最蛋疼的地方了一共五种情况，我们已经删除了节点，要开始平衡红黑树，看代码

/**
 * delete balance
 * @param rt
 */
void RedBlackTree::balance(Node *rt) {
    if (rt == root) {
        return;
    }


    Node *par = rt->parent;
    bool c = par->isRightChild();
    Node *brother = par->ch[c ^ 1];



    /**
     *
     *    B                 (B)
     *   / \                / \
     * (B)  B     ----->   B   R
     *     / \                / \
     *    B   B              B   B
     */
    if (par->color == BLACK && brother->color == BLACK && brother->ch[c] == BLACK
        && brother->ch[c ^ 1] == BLACK) {
        brother->color = RED;
        balance(par);
        return;
    }



    /**
     *        B1            B3
     *       / \   ---->   /
     *    (B)2  R3        R1
     *                    /
     *                  (B)2
     *
     *   grantee that brother is not red in the following
     */
    if (brother->color == RED) {
        std::swap(brother->color, par->color);
        rotate(brother);
    }



    /**
     *     R                 (B)
     *    / \                / \
     *  (B)  B    ----->    B   R
     *      / \                / \
     *     B   B              B   B
     */
    assert(brother->color == BLACK);
    brother = par->ch[c ^ 1];
    if (par->color == RED && brother->color == BLACK && brother->ch[c] == BLACK
        && brother->ch[c ^ 1] == BLACK) {
        std::swap(par->color, brother->color);
        balance(par);
        return;
    }

    /**
     *      X              X
     *     / \            / \
     *   (B)  B2   -->  (B)  B1
     *       / \              \
     *      R1  B3             R2
     *                          \
     *                           B3
     */

    Node *left = brother->ch[c];
    if (left->color == RED) {
        std::swap(brother->color, left->color);
        rotate(left);
    }


    /**
     *       X1                     X2
     *      / \                    /  \
     *    (B)  B2     ----->      B1   B4
     *        / \                / \
     *       X3  R4            (B)  X3
     */
    Node *right = brother->ch[c ^ 1];
    if (right->color == RED) {
        std::swap(brother->color, par->color);
        right->color = BLACK;
        rotate(brother);
    }

}

我的旋转代码 当前节点往父亲节点旋，这个可以根据自己的喜好来

void RedBlackTree::rotate(Node *rt) {

    Node *father = rt->parent;
    Node *grand = father->parent;


    bool c = (father->ch[1] == rt);
    bool fc = (grand->ch[1] == father);

    Node *&ch = rt->ch[c ^ 1];
    father->ch[c] = ch;
    if (ch != nullNode) {
        ch->parent = father;
    }
    ch = father;
    ch->parent = rt;


    rt->parent = grand;
    grand->ch[fc] = rt;

    if (father == root) {
        root = rt;
    }

    maintain(father);
    maintain(rt);

}