算法导论：c++实现红黑树

不念不忘少年蓝@ 2022-06-03 06:45 200阅读 0赞

### 数据结构 ###

**性质**  
![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]  
这里定义一个结构体保存颜色

enum colorRB
    {
        black = 0,
        red,
    };
    struct TreeNode_RB {
        int val;
        colorRB color;
        TreeNode_RB *left;
        TreeNode_RB *right;
        TreeNode_RB *parent;
        TreeNode_RB(int x, colorRB c) : val(x), left(NULL), right(NULL), parent(NULL),color(c) {}
    };

### 旋转 ###

![这里写图片描述][SouthEast 2]

#### 左旋 ####

![这里写图片描述][SouthEast 3]

/*红黑树左旋*/
    void left_roate(TreeNode_RB *root,TreeNode_RB *x) //x称为y的左子树，y的左子树成为x的右子树
    {
        TreeNode_RB *y = x->right;  //右子树左旋
        x->right = y->left;
        if (y->left != NULL) {
            y->left->parent = x;    //y左子树非空
        }
        y->parent = x->parent;  //置y的父节点
        if (x->parent == NULL) {
            root = y;
        }
        else if(x->parent->left==x)
        {
            x->parent->left = y;
        }
        else
        {
            x->parent->right = y;
        }
        y->left = x;    //y成为x左子树
        x->parent = y;  //y称为x的父节点
    }

#### 右旋 ####

void right_roate(TreeNode_RB *root, TreeNode_RB *y) //y成为x的右子树，x的右子树成为y的左子树
    {
        TreeNode_RB *x = y->left;   //左子树右旋
        y->left = x->right;
        if (x->right != NULL) {
            x->right->parent = y;   //x右子树非空
        }
        x->parent = y->parent;  //置x的父节点
        if (y->parent == NULL) {
            root = x;
        }
        else if (y->parent->left == y)
        {
            y->parent->left = x;
        }
        else
        {
            y->parent->right = x;
        }
        x->right = y;   //x成为y右子树
        y->parent = x;  //x成为y的父节点
    }

#### 测试 ####

int main()
    {
        TreeNode_RB *r1 = new TreeNode_RB(15,black);
        TreeNode_RB *r2 = new TreeNode_RB(6,red);
        TreeNode_RB *r3 = new TreeNode_RB(18,black);
        TreeNode_RB *r4 = new TreeNode_RB(3,black);
        TreeNode_RB *r5 = new TreeNode_RB(7,black);
    
        r1->left = r2;
        r1->right = r3;
        r2->parent = r1;
        r2->left = r4;
        r2->right = r5;
        r3->parent = r1;
    
        r4->parent = r2;
        r5->parent = r2;
        right_roate(r1, r2);
    
    }

### 插入 ###

插入就比较复杂了，涉及红黑树性质的调整，插入节点一致置颜色为红色，后再调整  
![这里写图片描述][SouthEast 4]

![这里写图片描述][SouthEast 5]

![这里写图片描述][SouthEast 6]

![这里写图片描述][SouthEast 7]

![这里写图片描述][SouthEast 8]

void RB_insert_fixup(TreeNode_RB *root, TreeNode_RB *z) {
        while (z->parent->color==red)
        {
            if (z->parent->parent->left==z->parent) //z的父节点是左子树
            {
                TreeNode_RB *y = z->parent->parent->right;  //叔叔节点
                if (y->color == red) //叔叔节点是红色，case 1
                {
                    z->color = black;   //重新着色
                    z->parent->color = black;
                    z->parent->parent->color = red;
                    z = z->parent->parent;  //指针上移
                }
                else if(z->parent->right==z)// 叔叔节点是黑色，且z是右子树，case 2
                {
                    z = z->parent;
                    left_roate(root, z);    //左旋
                }
                // 叔叔节点是黑色，且z是左子树，case 3
                z->parent->color = black;
                z->parent->parent->color = red;
                right_roate(root, z->parent->parent);
            }
            else
            {
                TreeNode_RB *y = z->parent->parent->left;   //叔叔节点
                if (y->color == red) //叔叔节点是红色，case 1
                {
                    z->color = black;   //重新着色
                    z->parent->color = black;
                    z->parent->parent->color = red;
                    z = z->parent->parent;  //指针上移
                }
                else if (z->parent->right == z)// 叔叔节点是黑色，且z是右子树，case 2
                {
                    z = z->parent;
                    right_roate(root, z);   //左旋
                }
                // 叔叔节点是黑色，且z是左子树，case 3
                z->parent->color = black;
                z->parent->parent->color = red;
                left_roate(root, z->parent->parent);
            }
        }
    }
    
    /*红黑树插入*/
    void RB_insert(TreeNode_RB *root, TreeNode_RB *z) {
        TreeNode_RB *y = NULL;  //y标记node的父指针
        TreeNode_RB *x = root;  //x用于向下探测
        z->color = red; //将待插入节点颜色置为红色
        while (x != NULL)
        {
            y = x;
            if (root->val < x->val) {
                x = x->left;
            }
            else
            {
                x = x->right;
            }
        }
        z->parent = y;
        if (y == NULL) {
            root = z;
        }
        else if (z->val<y->val)
        {
            y->left = z;
        }
        else
        {
            y->right = z;
        }
    }

[SouthEast]: /images/20220603/4e5c676f630e420faaa54c09b55fe554.png
[SouthEast 1]: /images/20220603/37af5c20bc154f4788295df0c6d77823.png
[SouthEast 2]: /images/20220603/a4f54fb2e48a47549ff603da5fbc8d7a.png
[SouthEast 3]: /images/20220603/063382d5c40b4917977a477e6dc73bc9.png
[SouthEast 4]: /images/20220603/5989a10b3eae4b728f0b3dfea22eb663.png
[SouthEast 5]: /images/20220603/0946256d3e3147e2acb506e686efba06.png
[SouthEast 6]: /images/20220603/265e6ab4e30a4d738c81759bb4442a3f.png
[SouthEast 7]: /images/20220603/0de5373b0a694b6ba8c159d9fec7c723.png
[SouthEast 8]: /images/20220603/0cf4933887fb4b67b628acea5c6bb5e6.png