ddddfang's Blog.

rb-tree

红黑树
字数统计: 4.5k阅读时长: 22 min
2019/01/30 Share

1. 介绍

Key-value 键值对貌似有用红黑书实现的（或者使用hash表实现，二者各有优劣）,关于红黑树的详细介绍可以参看 http://blog.csdn.net/v_JULY_v/article/details/6105630

红黑树必须满足的规则：

  • 所有节点都有颜色，要么红色，要么黑色
  • 根节点是黑色，所有叶子节点也是黑色
  • 叶子节点中不包含数据
  • 非叶子节点都有2个子节点
  • 如果一个节点是红色，那么它的父节点和子节点都是黑色的（黑节点无此要求！）
  • 从任何一个节点开始，到其下叶子节点的路径中都包含相同数目的黑节点

rbtree

根据规则,可以知道:

  • 红黑树中最长的路径就是红黑交替的路径，最短的路径是全黑节点的路径，再加上根节点和叶子节点都是黑色，可以保证红黑树中最长路径的长度不会超过最短路径的2倍(这就是红黑树的平衡性，并不是绝对平衡)

以下红黑树的实现摘自 linux2.6.34 版本（是不是一棵二叉搜索树是由使用者决定的哦）

2. rbtree.h

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/* linux/include/linux/rbtree.h */

#ifndef        _LINUX_RBTREE_H
#define        _LINUX_RBTREE_H

//stddef.h里面有NULL和offsetof的定义
#include <stddef.h>

//vs下的话aligned那里是加 #pragma pack(4)
struct rb_node
{
    unsigned long  rb_parent_color;    //存储父节点的地址(low 2 bit 为 0) + 本节点的 r/b 信息(就放在 low 2 bit 中)
#define        RB_RED        0
#define        RB_BLACK      1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long)))); //4bytes对齐,因此节点地址的 low 2 bit 必然为 0

struct rb_root
{
    struct rb_node *rb_node;
};

//获取本节点的父节点的地址
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
//获取本节点的 color
#define rb_color(r)   ((r)->rb_parent_color & 1)

#define rb_is_red(r)   (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)

//设置本节点的父节点(为 p)
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
    rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}

//设置本节点的color
static inline void rb_set_color(struct rb_node *rb, int color)
{
    rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}

//将 一个含有NULL指针的结构体 强制转换为 struct rb_root
#define RB_ROOT        (struct rb_root) { NULL, }

//下面这个宏摘自include/linux/kerne.h
//#define container_of(ptr, type, member) ({            \
//    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
//    (type *)( (char *)__mptr - offsetof(type,member) );})

//这是jensen的写法，反倒好用，且不用再搞一个offsetof了，上面的写法在vs环境可能会不认识
#define container_of(node, container, member) \
    (container *) (((char*) (node)) - ((unsigned long) &((container *)0)->member))

#define        rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node)  (rb_parent(node) == node)
#define RB_CLEAR_NODE(node)  (rb_set_parent(node, node))

extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);

extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);

extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
    struct rb_root *root);

//vs下inline写作__inline
//将node节点插入 由parent 和 rb_link 决定的那个位置
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link)
{
    node->rb_parent_color = (unsigned long )parent;  //parent地址low 2 bit为0,因此默认红色节点
    node->rb_left = node->rb_right = NULL;
    *rb_link = node;
}

#endif        /* _LINUX_RBTREE_H */

img02
img02

3. rbtree.c

rbtree.c.part1 之 __rb_rotate_left()
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
/*  linux/lib/rbtree.c  */
#include "rbtree.h"

//左旋转（没有做颜色上的处理），减少右子树高度
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *right = node->rb_right;
    struct rb_node *parent = rb_parent(node);

    if ((node->rb_right = right->rb_left))    //1.B的右为E, E为NULL的话就没必要设置了
        rb_set_parent(right->rb_left, node);  //2.E的父设为B
    right->rb_left = node;    //3.D的左设为B

    rb_set_parent(right, parent);    //4.D的父设为A

    if (parent)
    {
        if (node == parent->rb_left)    //5.A的左设为D
            parent->rb_left = right;
        else
            parent->rb_right = right;    //5.(or)A的右设为D
    }
    else    //若B原来就是root,(A为NULL)
        root->rb_node = right;
    rb_set_parent(node, right);    //6.B的父设为D
}

img02 img02 img02

rbtree.c.part2 之 __rb_rotate_right()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//右旋转（没有做颜色上的处理），减少左子树高度
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *left = node->rb_left;
    struct rb_node *parent = rb_parent(node);

    if ((node->rb_left = left->rb_right))    //1.B的左设为F
        rb_set_parent(left->rb_right, node); //2.F的父设为B
    left->rb_right = node;    //3.C的右设为B

    rb_set_parent(left, parent);    //4.C的父设为A

    if (parent)
    {
        if (node == parent->rb_right)    //5.A的右设为C
            parent->rb_right = left;
        else
            parent->rb_left = left;    //5.A的左设为C
    }
    else
        root->rb_node = left;    //若B原来就是root,(A为NULL)
    rb_set_parent(node, left);    //6.B的父设为C
}

img02 img02 img02

rbtree.c.part3 之 rb_insert_color()
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//此函数并不插入节点, 只是作为插入节点完毕之后最为关键的调整(包括高度和颜色)
//插入节点的操作由用户完成，用户会将新增节点插入为叶子节点(在红黑树的概念里，NULL才是叶子节点，那他就不叫叶子节点)，而本函数可能将其调整为非叶子节点
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *parent, *gparent;

    while ((parent = rb_parent(node)) && rb_is_red(parent))    //默认插入红节点，因此若父节点为黑，其实不需任何调整(A位置)
    {    //进入这里说明是插入到了B线上的某个位置
        gparent = rb_parent(parent);

        if (parent == gparent->rb_left)    //uncle在右
        {
            {
                register struct rb_node *uncle = gparent->rb_right;
                if (uncle && rb_is_red(uncle))         //uncle在右，uncle为红
                {
                    rb_set_black(uncle);        //uncle和parent必然在一左一右两个子树上，
                    rb_set_black(parent);        //同时黑化不影响本<祖父子三代>的平衡，但<三代>整体黑节点多了
                    rb_set_red(gparent);     //这样<三代>颜色正好了，但 祖 与 祖的父亲 同为红！这刚好与在gp下插入
                    node = gparent;                      //红色节点的case相同，成为一个 递归/迭代 问题
                    continue;
                }
            }
                                                       //uncle在右，uncle为黑
            if (parent->rb_right == node)                   //若是LR型，则先转换为LL型
            {
                register struct rb_node *tmp;
                __rb_rotate_left(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }
                                                      //走到这里一定是LL型
            rb_set_black(parent);
            rb_set_red(gparent);
            __rb_rotate_right(gparent, root);
        } else {                             //uncle在左边
            {
                register struct rb_node *uncle = gparent->rb_left;
                if (uncle && rb_is_red(uncle))   //uncle在左，uncle为红
                {
                    rb_set_black(uncle);
                    rb_set_black(parent);
                    rb_set_red(gparent);
                    node = gparent;
                    continue;
                }
            }
                                               //uncle在左，uncle为黑
            if (parent->rb_left == node)                //若是RL型，则先转换为RR型
            {
                register struct rb_node *tmp;
                __rb_rotate_right(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }
                                              //走到这里一定是RR型
            rb_set_black(parent);
            rb_set_red(gparent);
            __rb_rotate_left(gparent, root);
        }
    }

    rb_set_black(root->rb_node);
}

img02
img02 img02
img02 img02

rbtree.c.part4 之 __rb_erase_color() and rb_erase()
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root)  //case A 就不会进到这个函数中
{
struct rb_node *other;

    while ((!node || rb_is_black(node)) && node != root->rb_node)  //此节点不应该是根节点,且此节点为黑 (为NULL也是黑。所以case C出局)
    {
        if (parent->rb_left == node)       //此node为左子树
        {
            other = parent->rb_right;
            if (rb_is_red(other))         //case B5(然后case B5就转化为B1 B2 B3 B4中的一个了)
            {
                rb_set_black(other);
                rb_set_red(parent);
                __rb_rotate_left(parent, root);
                other = parent->rb_right;
            }  //走到这里只可能是 case B1 B2 B3 B4中的一种了
            if ((!other->rb_left || rb_is_black(other->rb_left)) &&
                (!other->rb_right || rb_is_black(other->rb_right))) //如果SL与SR均为黑(为NULL也是黑哦)，caseB1/B2
            {
                rb_set_red(other);
                node = parent;              //继续向上迭代,caseB1还会while继续，caseB2就不会再进while了
                parent = rb_parent(node);
            }
            else    //case B3/B4
            {
                if (!other->rb_right || rb_is_black(other->rb_right)) //SR为黑,caseB4（下面一顿操作B4就变成了B3）
                {
                    rb_set_black(other->rb_left);
                    rb_set_red(other);
                    __rb_rotate_right(other, root);
                    other = parent->rb_right;
                }    //走到这里只可能是caseB3了
                rb_set_color(other, rb_color(parent));
                rb_set_black(parent);
                rb_set_black(other->rb_right);
                __rb_rotate_left(parent, root);
                node = root->rb_node;
                break;   //
            }
        }
        else                                //此node为右子树,和左子树的case对称
        {
            other = parent->rb_left;
            if (rb_is_red(other))       //case B5
            {
                rb_set_black(other);
                rb_set_red(parent);
                __rb_rotate_right(parent, root);
                other = parent->rb_left;
            }
            if ((!other->rb_left || rb_is_black(other->rb_left)) &&
                (!other->rb_right || rb_is_black(other->rb_right)))
            {
                rb_set_red(other);
                node = parent;
                parent = rb_parent(node);
            }
            else
            {
                if (!other->rb_left || rb_is_black(other->rb_left))
                {
                    rb_set_black(other->rb_right);
                    rb_set_red(other);
                    __rb_rotate_left(other, root);
                    other = parent->rb_left;
                }
                rb_set_color(other, rb_color(parent));
                rb_set_black(parent);
                rb_set_black(other->rb_left);
                __rb_rotate_right(parent, root);
                node = root->rb_node;
                break;
            }
        }
    }
    if (node)
        rb_set_black(node);
}

void rb_erase(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *child, *parent;
    int color;

    if (!node->rb_left)
        child = node->rb_right;
    else if (!node->rb_right)
        child = node->rb_left;
    else    //左右子树均存在时,用此节点的下一个节点(中序遍历)替代此节点，之后将那个节点删除(又成了上面俩分支的case)
    {
        struct rb_node *old = node, *left;

        node = node->rb_right;
        while ((left = node->rb_left) != NULL)          //此即找到此节点中序遍历的next节点(所谓上位节点)，用它替换原节点没问题
            node = left;

                      //下面next节点像八爪蜘蛛一样爬到待删节点处，给整个树造成一直好像消失的是next节点一样的假象
        if (rb_parent(old)) {                                         //待删节点的父亲认 上位的next节点 为子（架空待删节点step1）
            if (rb_parent(old)->rb_left == old)
                rb_parent(old)->rb_left = node;        //
            else
                rb_parent(old)->rb_right = node;     //
        } else                                             //要删root节点啊
            root->rb_node = node;

                //记录八爪蜘蛛原来位置的parent,children和color
        child = node->rb_right;                                  //next肯定没有左子树,但可能会有右子树,(右子树也会上位，填next节点的坑)
        parent = rb_parent(node);
        color = rb_color(node);

        if (parent == old) {          //这个位置已经要被next节点架空了，也说明找next节点的时候根本没向左找
            parent = node;
        } else {                                                              //next节点右子树上位填next节点的坑
            if (child)
                rb_set_parent(child, parent);  //step2
            parent->rb_left = child;                       //step3

            node->rb_right = old->rb_right;        //step4
            rb_set_parent(old->rb_right, node); //step5
        }                                                                       //到此原来next节点已经没有他的位置了

        node->rb_parent_color = old->rb_parent_color; //step6
        node->rb_left = old->rb_left;                                   //step7
        rb_set_parent(old->rb_left, node);          //step8
                                                                               //同时也就相当于原待删节点至此已经完全被架空了
        goto color;
    }

    parent = rb_parent(node);
    color = rb_color(node);

    if (child)                                          //待删节点的父亲 和 待删节点的孩子 建立了父子关系
        rb_set_parent(child, parent);
    if (parent)                                      //待删节点的父亲 和 待删节点的孩子 建立了父子关系
    {
        if (parent->rb_left == node)
            parent->rb_left = child;
        else
            parent->rb_right = child;
    }
    else
        root->rb_node = child;

color:                                           //走到这一步，则node已经从树中被删除了，删除了的节点原来的
    if (color == RB_BLACK)                  //parent和child信息交给__rb_erase_color函数用于 rebalance（case A不会调用此函数）
        __rb_erase_color(child, parent, root);
}

img02
img02 img02
img02
img02 img02 img02 img02 img02

rbtree.c.part5 之 others
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
 * This function returns the first node (in sort order) of the tree.
 */
struct rb_node *rb_first(const struct rb_root *root)
{
    struct rb_node        *n;

    n = root->rb_node;
    if (!n)
        return NULL;
    while (n->rb_left)
        n = n->rb_left;
    return n;
}

struct rb_node *rb_last(const struct rb_root *root)
{
    struct rb_node        *n;

    n = root->rb_node;
    if (!n)
        return NULL;
    while (n->rb_right)
        n = n->rb_right;
    return n;
}

struct rb_node *rb_next(const struct rb_node *node)
{
    struct rb_node *parent;

    if (rb_parent(node) == node)
        return NULL;

    /* If we have a right-hand child, go down and then left as far as we can. */
    if (node->rb_right) {
        node = node->rb_right;
        while (node->rb_left)
            node=node->rb_left;
        return (struct rb_node *)node;
    }

    /* No right-hand children.  Everything down and left is
       smaller than us, so any 'next' node must be in the general
       direction of our parent. Go up the tree; any time the
       ancestor is a right-hand child of its parent, keep going
       up. First time it's a left-hand child of its parent, said
       parent is our 'next' node. */
    while ((parent = rb_parent(node)) && node == parent->rb_right)
        node = parent;

    return parent;
}

struct rb_node *rb_prev(const struct rb_node *node)
{
    struct rb_node *parent;

    if (rb_parent(node) == node)
        return NULL;

    /* If we have a left-hand child, go down and then right as far
       as we can. */
    if (node->rb_left) {
        node = node->rb_left;
        while (node->rb_right)
            node=node->rb_right;
        return (struct rb_node *)node;
    }

    /* No left-hand children. Go up till we find an ancestor which
       is a right-hand child of its parent */
    while ((parent = rb_parent(node)) && node == parent->rb_left)
        node = parent;

    return parent;
}

void rb_replace_node(struct rb_node *victim, struct rb_node *new,
     struct rb_root *root)
{
    struct rb_node *parent = rb_parent(victim);

    /* Set the surrounding nodes to point to the replacement */
    if (parent) {
        if (victim == parent->rb_left)
            parent->rb_left = new;
        else
            parent->rb_right = new;
    } else {
        root->rb_node = new;
    }
    if (victim->rb_left)
        rb_set_parent(victim->rb_left, new);
    if (victim->rb_right)
        rb_set_parent(victim->rb_right, new);

    /* Copy the pointers/colour from the victim to the replacement */
    *new = *victim;
}

4. 一个使用红黑树的例子

（从中可以看到红黑树一般都实现为二叉搜索树，即left和right是有大小关系约束的。但这一点其实是靠使用者来保证的）。
用tree实现一个key-value map（红黑树实现map与hash表实现map各有优劣）。每一个Node除了包含 rb_node 还包含key(string)和value(int)。添加键值对的时候按照 key （string）的 ASCII 按序插入，查找的时候利用 strcmp 进行查找，若找到则返回 value。但貌似 linux里面的 idr不是这样实现的，她是一个32叉树，why? 效率高？ 这里也讲解了一个如何使用红黑树的例子.

commonTree.h
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
#ifndef COMMON_TREE_H
#define COMMON_TREE_H

#include "rbtree.h"

typedef struct
{
    struct rb_node node;
    void *kdata;        //按 kdata 为关键字组成二叉排序树
    void *vdata;        //custom app data, maybe a structure
}cTreeNode,*cTreeNodeId;

typedef struct
{
    int total;
    int (*cmp)(const void *p1,const void *p2);        //p1<p2 return <0
    struct rb_root root;
}cTreeManager,*cTree;

cTree cTreeCreate(int (*cmp)(const void *p1,const void *p2));

//这个主要是想配合 cTreeEraseFromNodeId 函数使用的
cTreeNodeId cTreeSearch(cTree ctree,void *kdata);

void *getVdataFromNodeId(cTreeNodeId id);
void *getKdataFromNodeId(cTreeNodeId id);

//如果vdata指向自定义的数据结构,则返回update之前的vdata,必须释放,否则可能内存泄漏
//vdata不需要释放的则可以不用关心free操作及返回的void*
void *cTreeInsert(cTree ctree,void *kdata,unsigned int kdataSize,void *vdata);

void *cTreeEraseFromNodeId(cTree ctree,cTreeNodeId *pid);
void *cTreeErase(cTree ctree,void *kdata);
int cTreeMap(cTree ctree,void apply(void *k,void **pv,void *cl), void *cl);
int cTreeMap2(cTree ctree,void apply(void *k,void **x,void *cl,int lev), void *cl);
int cTreeDestroy(cTree *pctree);

#endif
commonTree.c
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "commonTree.h"

//默认是按照 kdata 指针值排序(即key的地址值)
static int cmp_default(const void *p1,const void *p2)
{
    return ((unsigned int)p1 - (unsigned int)p2);
}

cTree cTreeCreate(int (*cmp)(const void *p1,const void *p2))
{
    cTree p = (cTreeManager *)malloc(sizeof(cTreeManager));
    if(!p)
        return NULL;
    p->total = 0;
    p->root = RB_ROOT;        //init rb tree
    p->cmp = (cmp == NULL) ? cmp_default : cmp;                //init rb tree
    return p;
}

cTreeNodeId cTreeSearch(cTree ctree,void *kdata)
{
    cTreeNode *pTreeNode = NULL;
    int cmpRes = 0;
    struct rb_root *pRoot = &(ctree->root);        //the root, including a pointer to rb_node
    struct rb_node *pNode = pRoot->rb_node;        //the first node

    while(pNode != NULL)
    {
        pTreeNode = container_of(pNode,cTreeNode,node);
        cmpRes = (*(ctree->cmp))(kdata,pTreeNode->kdata);
        if(cmpRes < 0)
        {
            pNode = pNode->rb_left;
        }
        else if(cmpRes > 0)
        {
            pNode = pNode->rb_right;
        }
        else
        {
            return pTreeNode;        //cTreeNodeId 就是一个 cTreeNode*
        }
    }
    return NULL;
}

void *getKdataFromNodeId(cTreeNodeId id)
{
    return (id->kdata);
}
void *getVdataFromNodeId(cTreeNodeId id)
{
    return (id->vdata);
}

void *cTreeInsert(cTree ctree,void *kdata,unsigned int kdataSize,void *vdata)
{
    void *oldVdata = NULL;
    cTreeNode *pTreeNode = NULL;
    int cmpRes = 0;

    struct rb_root *pRoot = &(ctree->root);        //the root, including a pointer to rb_node
    struct rb_node **ppNode = &(pRoot->rb_node);    //这里参见 rbtree.h 那里的第二张图,这里是想改变指针的指向 而不是改变指针指向的那个值
    struct rb_node *pParent = NULL;

    while(*ppNode)
    {
        pTreeNode = container_of(*ppNode,cTreeNode,node);
        pParent = *ppNode;
        cmpRes = (*(ctree->cmp))(kdata,pTreeNode->kdata);
        if(cmpRes < 0)
        {
            ppNode = &(*ppNode)->rb_left;
        }
        else if(cmpRes > 0)
        {
            ppNode = &(*ppNode)->rb_right;
        }
        else
        {
            //如果有相同的 key 要插入,返回之前的old vdata,用户 MUST 进行必要的 释放 操作 !!!
            //我们使用的 kdata 有没有可能存在泄露?
            //case.1: kdata 通过malloc分配的,那么更新后的 pTreeNode->kdata 仍然指向他,没有丢失
            //case.2: kdata 是vdata指向结构体的某个成员,那么更新后的 pTreeNode->kdata 地址失效
            //这样太复杂了,关键是不可控制,因此我们无论如何自己保存一份kdata!,这样的话,这里的kdata无论无何都是有效的(只是我们不必再memcpy一次了)
            oldVdata = pTreeNode->vdata;
            pTreeNode->vdata = vdata;
            return oldVdata;
        }
    }
    //malloc a tree node for (k,v)
    cTreeNode *pTargetTreeNode = (cTreeNode *)malloc(sizeof(cTreeNode)+kdataSize+1);
    if(!pTargetTreeNode)
        return NULL;
    pTargetTreeNode->kdata = (void *)(pTargetTreeNode+1);    //kdata的值紧跟着节点存放
    memset(pTargetTreeNode->kdata,0,kdataSize+1);
    memcpy(pTargetTreeNode->kdata,kdata,kdataSize);        //我们默认 kdata 指向的地址是一个有效的值!! 不允许 "(void *)i" 这样的玩法!!
    pTargetTreeNode->vdata = vdata;

    rb_link_node(&pTargetTreeNode->node, pParent,ppNode);        //first, link this node to rbTree
    rb_insert_color(&pTargetTreeNode->node, pRoot);                        //rebalance

    ctree->total++;
    return NULL;
}

//这个只是删除(释放) cTreeNode,其 vdata 指向的内存需要自己来释放!
void *cTreeEraseFromNodeId(cTree ctree,cTreeNodeId *pid)
{
    void *oldVdata = NULL;
    struct rb_root *pRoot = &(ctree->root);        //the root, including a pointer to rb_node
    if(!pid || !(*pid))
        return NULL;
    cTreeNode *pTreeNode = *pid;

    oldVdata = pTreeNode->vdata;
    rb_erase(&pTreeNode->node,pRoot);                //just remove from rbtree relationship
    free(pTreeNode);        //if pTreeNode->pdata pointer to a struct ,you MUST free yourself !!
    ctree->total--;
    *pid = NULL;
    return oldVdata;        //留待用户释放的 vdata (如有必要释放)
}

//equals to "search and erase by id" operation
void *cTreeErase(cTree ctree,void *kdata)
{
    void *oldVdata = NULL;
    cTreeNode *pTreeNode = NULL;
    int cmpRes = 0;
    struct rb_root *pRoot = &(ctree->root);        //the root, including a pointer to rb_node
    struct rb_node *pNode = pRoot->rb_node;        //the first node

    while(pNode != NULL)
    {
        pTreeNode = container_of(pNode,cTreeNode,node);
        cmpRes = (*(ctree->cmp))(kdata,pTreeNode->kdata);
        if(cmpRes < 0)
        {
            pNode = pNode->rb_left;
        }
        else if(cmpRes > 0)
        {
            pNode = pNode->rb_right;
        }
        else
        {
            oldVdata = pTreeNode->vdata;
            rb_erase(pNode,pRoot);
            free(pTreeNode);        //if pTreeNode->pdata pointer to a struct ,you MUST free yourself !!
            ctree->total--;
            return oldVdata;        //留待用户释放的 vdata (如有必要释放)
        }
    }
    return NULL;
}

int cTreeMap(cTree ctree,void apply(void *k,void **pv,void *cl), void *cl)
{
    struct rb_root *pRoot = &(ctree->root);        //the root, including a pointer to rb_node
    struct rb_node *pNode = NULL;
    cTreeNode *pTreeNode = NULL;
    //(其实就是while迭代实现的中序遍历),rb_first()找到的node也是中序遍历意义上的第一个
    for(pNode = rb_first(pRoot);pNode;pNode = rb_next(pNode))
    {
        pTreeNode = container_of(pNode,cTreeNode,node);
        //printf("%d,",pMgrNode->value);
        apply(pTreeNode->kdata,&pTreeNode->vdata,cl);
    }
    return 0;
}

static int cTreeMapInternal(struct rb_node *pNode,void apply(void *k,void **x,void *cl,int lev), void *cl, int level)
{
    cTreeNode *pTreeNode = NULL;
    if(!pNode)
        return 0;

    if(pNode->rb_left)
        cTreeMapInternal(pNode->rb_left,apply,cl,level+1);
    //else
    //        apply(NULL,NULL,cl,level+1);

    //mid order access
    pTreeNode = container_of(pNode,cTreeNode,node);
    apply(pTreeNode->kdata,&pTreeNode->vdata,cl,level);

    if(pNode->rb_right)
        cTreeMapInternal(pNode->rb_right,apply,cl,level+1);
    //else
    //        apply(NULL,NULL,cl,level+1);
    return 0;
}

int cTreeMap2(cTree ctree,void apply(void *k,void **x,void *cl,int lev), void *cl)
{
    struct rb_root *pRoot = &(ctree->root);        //the root, including a pointer to rb_node
    struct rb_node *pNode = pRoot->rb_node;        //the first node

    return cTreeMapInternal(pNode,apply,cl,0);
}

//调用本 cTreeDestroy 前,应该先调用 cTreeMap 释放掉所有的 vdata 指向的内存
int cTreeDestroy(cTree *pctree)
{
    if(!pctree || !(*pctree))
        return 0;
    cTree ctree = *pctree;
    struct rb_root *pRoot = &(ctree->root);        //the root, including a pointer to rb_node
    struct rb_node *pNode = NULL;
    struct rb_node *pNodeTmp = NULL;
    cTreeNode *pTreeNodeTmp = NULL;

    pNode = rb_first(pRoot);
    while(pNode)
    {
        pNodeTmp = pNode;
        pNode = rb_next(pNode);

        pTreeNodeTmp = container_of(pNodeTmp,cTreeNode,node);
        rb_erase(pNodeTmp,pRoot);
        free(pTreeNodeTmp);        //if pTreeNode->pdata pointer to a struct ,you MUST free yourself !!
        ctree->total--;
    }
    free(ctree);
    *pctree = NULL;
    return 0;
}

原文作者：ddddfang

原文链接：https://ddddfang.github.io/2019/01/30/rb-tree/

发表日期：January 30th 2019, 4:49:49 pm

更新日期：January 30th 2019, 7:43:30 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 1. 介绍
  2. 2. 2. rbtree.h
  3. 3. 3. rbtree.c
    1. 3.0.0.1. rbtree.c.part1 之 __rb_rotate_left()
    2. 3.0.0.2. rbtree.c.part2 之 __rb_rotate_right()
    3. 3.0.0.3. rbtree.c.part3 之 rb_insert_color()
    4. 3.0.0.4. rbtree.c.part4 之 __rb_erase_color() and rb_erase()
    5. 3.0.0.5. rbtree.c.part5 之 others
  • 4. 4. 一个使用红黑树的例子
    1. 4.0.0.1. commonTree.h
    2. 4.0.0.2. commonTree.c
    • Total : 42
    2019
    binary-search bitmap caffe c++ 单例模式 common misc makefile 宏 顺序容器 智能指针 排序 shell linux command docker blog ffmpeg gdb gitbook p4 printf 可变参数 static and dynamic library 第k小的数 ubuntu setup 并查集 git draw.io markdown vscode office2016 密钥 键值对集合 链表 最大堆(大顶堆) swig python c vim 红黑树 skip-list hash-table
    algorithm-and-data-struct caffe common-misc cpp linux-daily ffmpeg