乐趣区

关于红黑树:数据结构与算法-红黑树-C语言实现

花了好几天的业余时间,看文章,总算是用 C 实现了一遍红黑树,次要还是本人 C 语言程度不够高,调试断点节约了不少工夫,闲话少说

1. 红黑树结构体

// 这里偷懒就应 0 代表彩色,1 代表红色了
typedef struct RBTreeNode {
    int data; // 数据域
    int color; // 0 彩色 1 红色
    struct RBTreeNode *parent;// 父亲结点
    struct RBTreeNode *left;  // 左子结点
    struct RBTreeNode *right; // 右子结点
} RBTreeNode;

2. 前序遍历

// 这里打印了节点的色彩和父节点
void preOrderTraverse(RBTreeNode *root)
{if (root != NULL)
    {if (root->parent != NULL)
        {printf("%d color: %d parent:%d\n", root->data, root->color, root->parent->data);
        }else{printf("%d color: %d\n", root->data, root->color);
        }        
        preOrderTraverse(root->left);
        preOrderTraverse(root->right);
    }
}

3.1 左旋

跟 AVL 树差不多,多了 parent 相干的操作

/**
 * 左旋
 *            parent                    parent
 *          8                         12
 *       4     12                  8     50  
 *           9    50      =>    4    9      70
 *                   70                      
 */
RBTreeNode *left_rotation(RBTreeNode *root)
{
    struct RBTreeNode *new_root;
    new_root         = root->right;
    root->right      = new_root->left;
    // 将 9 的父亲设置为老的 root 即 8
    if (new_root->left != NULL)
    {new_root->left->parent = root;}
    // 新 root 的 parent 即老 parent
    new_root->parent = root->parent;
    // 而后解决老 root 的 parent
    if (root->parent == NULL)
    {
        // 老 root 是根节点
        new_root->parent = NULL;
    }else{
        // 判断父亲左右
        if (new_root->parent->left == root)
        {new_root->parent->left = new_root;}else{new_root->parent->right = new_root;}
    }
    root->parent = new_root;
    new_root->left   = root;
    return new_root;
}

3.2 右旋

/**
 * 右旋
 *          8                  4
 *       4     12           2     8
 *    2    6         =>  1      6   12
 * 1                                
 */
RBTreeNode *right_rotation(RBTreeNode *root)
{
    struct RBTreeNode *new_root;
    new_root         = root->left;
    root->left      = new_root->right;
    
    // 将 6 的父亲设置为老的 root 即 8
    if (new_root->right != NULL)
    {new_root->right->parent = root;}
    // 新 root 的 parent 即老 parent
    new_root->parent = root->parent;
    
    // 而后解决老 root 的 parent
    if (root->parent == NULL)
    {
        // 老 root 是根节点
        new_root->parent = NULL;
    }else{
        // 判断父亲左右
        if (new_root->parent->left == root)
        {new_root->parent->left = new_root;}else{new_root->parent->right = new_root;}
    }
    
    new_root->right   = root;
    root->parent = new_root;
    // printf("*** 本人 right_rotation***:  \n");
    // printfNode(new_root);
    // printf("*** 左 ***:  \n");
    // printfNode(new_root->left);
    // printf("*** 右 ***:  \n");
    // printfNode(new_root->right);
    return new_root;
}

3.3 代码图解

/**
 * 1. 插入的只有一个根节点
 * 
 *         8(R)  => 8(B)
 * 
 * 2.1 父节点是彩色,啥也不必干
 *           8(B)
 *         /          =>   不变
 *      4(R)
 *
 * 2.2 父节点是红色, 祖父肯定是彩色啦,看叔叔是啥色彩
 *
 * 2.2.1 父节点是祖父节点的左节点
 *
 *     2.2.1.1 如果叔叔也是红色 
 *            将父节点, 叔节点设为彩色, 将祖父节点设为红色, 将祖父节点设为“以后节点”(红色节点);即,之后递归持续对“以后节点”进行操作
 *
 *                  8(B)              8(R)               8(B)
 *                 /    \            /    \             /    \ 
 *               4(R)   12(R)  =>  4(B)   12(B)   =>  4(B)   12(B)
 *               /                 /                   /
 *             2(R)              2(R)                2(R)
 *     
 *     2.2.1.2 如果叔叔不存在或是彩色
 *           2.2.1.2.1 新节点在左子树
 *                    父节点设为彩色, 将祖父节点设为红色,对祖父节点右旋
 *
 *                  8(B)                 8(R)                         8(B)
 *                 /    \     着色       /    \        对 4 右旋     /    \ 
 *               4(B)  12(B)   =>      4(R)   12(B)       =>      2(B)   12(B)
 *               /                     /                          /  \
 *             2(R)                  2(B)                     1(R)   4(R)
 *             /                     /
 *           1(R)                  1(R)
 *           
 *           2.2.1.2.2 新节点在右子树
 *                    root 与父节点替换 并把父节点设为新 root 的左节点, 即转化为 2.2.1.2.1,解决如上
 *
 *                  8(B)                 8(B)                  8(B)                         8(B)
 *                 /    \     替换       /    \       着色     /    \         对 4 右旋     /    \ 
 *               4(B)  12(B)   =>      4(B)   12(B)   =>    4(R)   12(B)        =>      3(B)   12(B)
 *               /                     /                    /                           /  \
 *             2(R)                  3(R)                 3(B)                        2(R)  4(R)
 *                \                  /                    /
 *                3(R)             2(R)                 2(R)
 *
 *
 *
 * 2.2.2 父节点是祖父节点的右节点
 *     2.2.2.1 如果叔叔也是红色
 *             将父节点, 叔节点设为彩色, 将祖父节点设为红色, 将祖父节点设为“以后节点”(红色节点);即,之后递归持续对“以后节点”进行操作
 *
 *                  8(B)              8(R)               8(B)
 *                 /    \            /    \             /    \ 
 *               4(R)   12(R)  =>  4(B)   12(B)   =>  4(B)   12(B)
 *                        \                 \                   \
 *                        20(R)              20(R)               20(R)
 *
 *     2.2.2.2 如果叔叔不存在或是彩色 (这里的绘图简化些,其实都一样的)
 *             2.2.2.2.1 新节点在左子树
 *                 root 与父节点替换 并把父节点设为新 root 的右节点, 即转化为 2.2.2.2.2
 *                 8(B)                  8(B)                8(R)                   10(B)
 *                    \         替换        \         着色      \        对 8 右旋     /   \ 
 *                    12(R)     =>          10(R)      =>       10(B)     =>      8(R)  12(R)
 *                    /                       \                   \
 *                  10(R)                     12(R)               12(R)
 *
 *             2.2.2.2.2 新节点在右子树
 *                 将父节点设为彩色 将祖父节点设为红色 左旋
 *                 
 *                   8(B)                     8(R)                   12(B)
 *                     \         着色           \        对 8 左旋     /    \ 
 *                     12(B)      =>           12(B)       =>      8(R)  20(R)
 *                        \                      \                         
 *                        20(R)                  20(R)                     
 *
 * 
 */

4. 自均衡

RBTreeNode *rebalance3(RBTreeNode *root, RBTreeNode *rootNode)// 返回新的根节点
{
    //1 插入根节点, 只需置黑即可
    if (root->parent == NULL)
    {root->color = 0;}
    //2 有父节点
    if (root->parent != NULL)
    {   
        //2.1 父节点是彩色,啥也不必干
        if (root->parent->color == 0)
        {//do nothing}else{
        //2.2 父节点是红色, 祖父肯定是彩色啦,看叔叔是啥色彩
            RBTreeNode *parent, *gparent, *uncle;
            parent = root->parent;
            gparent = root->parent->parent;
            int return_flag = 0;
            if (gparent == rootNode)
            {return_flag = 1;}
            // 先判断父节点是祖父节点的左节点还是右节点,即叔叔节点是啥
            //2.2.1 父节点是祖父节点的左节点
            if (parent == gparent->left)
            {
                uncle = gparent->right;
                //2.2.1.1 如果叔叔也是红色
                if (uncle != NULL && uncle->color == 1)
                {
                    //1. 将父节点设为彩色
                    parent->color = 0;
                    //2. 将叔节点设为彩色
                    uncle->color = 0;
                    //3. 将祖父节点设为红色
                    gparent->color = 1;
                    //4. 将祖父节点设为“以后节点”(红色节点);即,之后持续对“以后节点”进行操作
                    
                    return rebalance3(gparent, rootNode);
                }else{
                //2.2.1.2 如果叔叔彩色 或不存在
                    //2.2.1.2.1 root 是左节点
                    if (root == parent->left)
                    {
                        //1. 将父节点设为彩色
                        parent->color = 0;
                        //2. 将祖父节点设为红色
                        gparent->color = 1;
                        gparent = right_rotation(gparent);
                    }else{
                    //2.2.1.2.2 root 是右节点
                        //1.root 与父节点替换 并把父节点设为新 root 的左节点, 即转化为 2.2.1.2.1
                        gparent->left = root;                       

                        root->parent = gparent;
                        root->left = parent;

                        parent->parent = root;
                        parent->right = NULL;

                        return rebalance3(parent, rootNode);
                    }
                }
            }else{
            //2.2.2 父节点是祖父节点的右节点
                uncle = gparent->left;
                //2.2.2.1 如果叔叔也是红色
                if (uncle != NULL && uncle->color == 1)
                {
                    //1. 将父节点设为彩色
                    parent->color = 0;
                    //2. 将叔节点设为彩色
                    uncle->color = 0;
                    //3. 将祖父节点设为红色
                    gparent->color = 1;
                    //4. 将祖父节点设为“以后节点”(红色节点);即,之后持续对“以后节点”进行操作
                    return rebalance3(gparent, rootNode);
                }else{
                //2.2.2.2 如果叔叔彩色 或不存在
                    //2.2.2.2.1 root 是左节点
                    if (root == parent->left)
                    {
                        //1.root 与父节点替换 并把父节点设为新 root 的左节点, 即转化为 2.2.2.2.2
                        gparent->right = root;
                        root->parent = gparent;
                        root->right = parent;
                        parent->parent = root;   
                        parent->left = NULL;
                        return rebalance3(parent, rootNode);
                    }else{
                    //2.2.2.2.2 root 是右节点                        
                        //1. 将父节点设为彩色
                        parent->color = 0;
                        //2. 将祖父节点设为红色
                        gparent->color = 1;

                        gparent = left_rotation(gparent);
                    }
                }
            }
            if (return_flag == 1)
            {return gparent;}
        }
    }
    return rootNode;
}

5.1 插入(未均衡)

RBTreeNode *insert(RBTreeNode *root, int data, RBTreeNode *parent)
{if (NULL == root)
    {return getNode(data, parent);
    }
    if (data >= root->data)
    {root->right  = insert(root->right, data, root);
    }else{root->left   = insert(root->left, data, root);
    }
    return root;
}

5.2 插入 (均衡)

RBTreeNode *inserRB(RBTreeNode *root, int data, RBTreeNode *parent)
{root = insert(root,data,parent);
    return rebalance3(RBTreeEndNode,root);
}

6 测试红黑树构建

int main()
{ 
    struct RBTreeNode *node;
    
    //2.2.1.1 测试用例
    node = NULL;
    node = inserRB(node, 8, NULL);
    node = inserRB(node, 4, NULL);
    node = inserRB(node, 12, NULL);
    node = inserRB(node, 2, NULL);
    printf("***2.2.1.1 测试用例 前序 ***:  \n");
    preOrderTraverse(node);

    //2.2.1.2.1 测试用例
    node = NULL;
    node = inserRB(node, 8, NULL);
    node = inserRB(node, 4, NULL);
    node = inserRB(node, 12, NULL);
    node = inserRB(node, 2, NULL);
    node = inserRB(node, 1, NULL);
    printf("***2.2.1.2.1 测试用例 前序 ***:  \n");
    preOrderTraverse(node);

    //2.2.1.2.2 测试用例
    node = NULL;
    node = inserRB(node, 8, NULL);
    node = inserRB(node, 4, NULL);
    node = inserRB(node, 12, NULL);
    node = inserRB(node, 2, NULL);
    node = inserRB(node, 3, NULL);
    printf("***2.2.1.2.2 测试用例 前序 ***:  \n");
    preOrderTraverse(node);

    //2.2.2.1 测试用例
    node = NULL;
    node = inserRB(node, 8, NULL);
    node = inserRB(node, 4, NULL);
    node = inserRB(node, 12, NULL);
    node = inserRB(node, 20, NULL);
    printf("***2.2.2.1 测试用例 前序 ***:  \n");
    preOrderTraverse(node);

    //2.2.2.2.1 测试用例
    node = NULL;
    node = inserRB(node, 8, NULL);
    node = inserRB(node, 12, NULL);
    node = inserRB(node, 10, NULL);
    printf("***2.2.2.2.1 测试用例 前序 ***:  \n");
    preOrderTraverse(node);

    //2.2.2.2.2 测试用例
    node = NULL;
    node = inserRB(node, 8, NULL);
    node = inserRB(node, 12, NULL);
    node = inserRB(node, 20, NULL);
    printf("***2.2.2.2.2 测试用例 前序 ***:  \n");
    preOrderTraverse(node);
}

测试后果:

7 红黑树删除节点

@todo

退出移动版