红黑树c语言实现

lkpalu Lv3
  2024-12-02 18:20:54 2024-12-02 18:20:54 创建   2024-12-03 09:05:58 2024-12-03 09:05:58 更新    

红黑树

定义

（叶子节点包含空节点）

1.每个节点是红的或者黑的

2.根节点是黑的

3.每个叶子节点是黑的

4.如果一个节点是红的，则他的两个儿子都是黑的

5.对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点

旋转

节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct rtbtree{

  int key;

  void* value;



  struct rtbtree* left;

  struct rtbtree* right;

  struct rtbtree* parent;



  unsigned char color;

};

关键节点定义

1
2
3
4
typedef struct rbtree{
    rbtree_node* root;
    rbtree_node* nil;
}rbtree;

这里定义nil节点为所有的叶子节点

根据上面定义的节点来看，迁移性非常差，做出如下修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define RBTREE_ENTRY(name,type) \
    struct name{         \
        struct type *left; \
        struct type *right; \
        struct type *parent; \
        unsigned char color; \
    }
typedef int KEY_TYPE;    

typedef struct rbtree_node{
    KEY_TYPE key;
    void* value;
#if 0
        struct type left; 
        struct type right; 
        struct type parent; 
        unsigned char color; 
#else
    RBTREE_ENTRY(,rbtree_node) node;
#endif
}rbtree_node;

这种定义方法可以帮助定义不同类型的红黑树，以及在线程中减少代码量

旋转

用于红黑树性质被破环的时候，需要进行调整，使树重新满足定义

1.左旋

2.右旋

旋转

图中左侧树经过左旋转为右侧，右侧经过左旋转为左侧，左右旋转可逆

图中的x为上图定义的一个rbtree_node，

左旋中以x作为轴心，右旋以y作为轴心

左旋代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void retree_left_rotate(rbtree *T, rbtree_node *x)
{
    rbtree_node *y = x->right;
    //1
    x->right = y->left;
    if (y->left != T->nil)
    {
        y->left->parent = x;
    }
    //2
    y->parent = x->parent;
    if (x->parent == T->nil) // x为root节点
    {
        // 翻转之后root节点为y
        T->root = y;
    }
    else if (x == x->parent->left) // x为左节点
    {
        x->parent->left = y;
    }
    else// x为右节点
    {
        x->parent->right = y;
    }
    //3
    y->left = x;
    x->parent = y;
}

右旋代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void retree_right_rotate(rbtree *T, rbtree_node *y)
{
    rbtree_node* x = y->left;
    //1
    y->left = x->right;
    if(x != T->nil)//x不为叶子节点，叶子节点为nil，不用更改
    {
        y->parent = x;
    }
    //2
    x->parent = y->parent;
    if(y->parent == T->nil)//y为root节点
    {
        T->root = x;
    }
    else if(y == y->parent->left)//y为左节点
    {
        y->parent->left = x;
    }
    else//y为右节点
    {
        y->parent->right = x;
    }
    //3
    x->right = y;
    y->parent = x;

}

左旋右旋代码基本相同，看着上面的图就很容易理解了

插入

插入操作为基本的二叉排序树的插入，即比较当前节点与插入节点的值，大的走右边，小的走左边

重点为直接插入之后的上色极其调整

红黑树在插入之前本身就是一颗红黑树

证明：归纳法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void rbtree_insert(rbtree *T, rbtree_node *z)
{
    rbtree_node *x = T->root;
    while (x != T->nil)
    {
        if (z->key < x->key)
        {
            x = x->left;
        }
        else if (z->key > x->key)
        {
            x = x->right;
        }
        else
        {
            // 这里的else是z->key == x->key,由于红黑树为定义key相同的情况，
            // 具体情况具体分析，可以丢弃，插入，或者更改z->key,这里直接退出，不进行插入
            return;
        }
    }
    if (x == T->nil) // 没有树的情况
    {
        T->root = z;
    }
    else
    {
        if (z->key < x->parent->key)
        {
            x->parent->left = z;
        }
        else
        {
            x->parent->right = z;
        }
    }
    z->parent = x->parent;
    z->color = RED;
    /*
    上红色原因
    1.不改变黑色节点个数，满足第五条性质
    */
   rbtree_insert_fixup(T, z);
}

在插入节点之后，会遇到三种情况，需要进行旋转操作使树重新符合红黑树定义

1.叔节点为红色

1

这种情况需要把父节点和叔父节点调整为黑色，祖父节点调整为红色，不需要进行旋转

1
2
3
4
y->color = BLACK;
z->parent->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;//回溯

2.叔节点为黑色，当前节点为右孩子

2

这种需要进行两次旋转造作，先进性一次操作转为情况3

需要以z的父节点为轴进行左旋

1
2
3
4
5
if(z == z->parent->right)
{
z = z->parent;
retree_left_rotate(T,z);
}

3..叔节点为黑色，当前节点为左孩子

将父节点变黑色，祖父变红色后进行右旋操作

1
2
3
z->parent->color = BLACK;
z->parent->parent->color = RED;
retree_right_rotate(T, z->parent->parent);

插入即可完成

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void rbtree_insert_fixup(rbtree *T, rbtree_node *z)
{
    //z为红色节点（重点）
    //z需要时刻保持为红色节点

    /*
    推断
    1.z的父节点为红色
    2.z的祖父节点为黑色
    3.z的叔父未知
    */
    while(z->parent == RED)
    {
        if(z->parent == z->parent->parent->left)
        {
            rbtree_node* y = z->parent->parent->right;
            if(y->color == RED)
            {
                y->color = BLACK;
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;//回溯
            }
            else
            {//y为黑色
                if(z == z->parent->right)
                {
                    z = z->parent;
                    retree_left_rotate(T,z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                retree_right_rotate(T, z->parent->parent);
            
            }
        }
    }
}

总结

红黑树是一种时间复杂度极高的k,v存储，被广泛应用于互联网各方面，实现相对复杂

  • 标题: 红黑树c语言实现
  • 作者: lkpalu
  • 创建于 : 2024-12-02 18:20:54
  • 更新于 : 2024-12-03 09:05:58
  • 链接: https://redefine.ohevan.com/2024/12/02/红黑树/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
红黑树c语言实现
  1. 红黑树
    1. 定义
      1. 节点定义
      2. 关键节点定义
    2. 旋转
    3. 插入
    4. 总结