Method insertFixup

templates/red-black-tree.cpp:176–232

1 父子节点之间不能出现两个连续的红节点 2 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等 */

    2 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
    */
    void insertFixup(RBTreeNode* z)
    {
        // 处理父节点是红色，父子同为红色冲突了
        while (z->p->color == RED) {
            // 父节点在左边
            if (z->p->isLeft()) {
                // 找到叔叔
                auto y = z->p->brother();
                // case 1
                if (y->color == RED) {
                    // 父亲和叔叔都是红色，把他们都变成黑色
                    z->p->color = BLACK;
                    y->color = BLACK;
                    // 把祖父变成红色
                    z->p->p->color = RED;
                    z = z->p->p;
                } else {
                    // case 2
                    // 父亲是红色，叔叔是黑色
                    if (z->isRight()) {
                        // z在右边就左旋，z指向父节点
                        z = z->p;
                        // 左旋父节点
                        leftRotate(z);
                    }
                    // case 3
                    // 父亲设置为黑色
                    z->p->color = BLACK;
                    // 把祖父变成红色
                    z->p->p->color = RED;
                    // 右旋祖父节点
                    rightRotate(z->p->p);
                }
            } else {
                auto y = z->p->brother();
                // case 1
                if (y->color == RED) {
                    z->p->color = BLACK;
                    y->color = BLACK;
                    z->p->p->color = RED;
                    z = z->p->p;
                } else {
                    if (z->isLeft()) {
                        // case 2
                        z = z->p;
                        rightRotate(z);
                    }

                    // case 3
                    z->p->color = BLACK;
                    z->p->p->color = RED;
                    leftRotate(z->p->p);
                }
            }
        }
        root->color = BLACK;
    }