-
Notifications
You must be signed in to change notification settings - Fork 0
/
rbtree.h
188 lines (156 loc) · 4.46 KB
/
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
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
//
// Created by luo on 2023/5/29.
//
#ifndef LIBNE_RBTREE_H
#define LIBNE_RBTREE_H
#ifdef cplusplus
extern "C" {
#endif
#include <stddef.h>
#include <assert.h>
#define RBN_COLOR_BLK (0)
#define RBN_COLOR_RED (1)
#define RBT_LEFT(n) \
((n)->children[0])
#define RBT_RIGHT(n) \
((n)->children[1])
#define RBT_DIR(n) \
(RBT_LEFT((n)->parent) == (n) ? 0 : 1)
#define RBT_REVERSE_DIR(i) \
(((i) ^ 0x1) & 0x1 )
#define RBT_IS_RED(n) \
((n)->color == RBN_COLOR_RED)
typedef struct rbnode {
char color;
struct rbnode *parent;
struct rbnode *children[2];
} rbnode_t;
typedef struct rbtree {
rbnode_t *root;
int (*cmpfn)(rbnode_t *, rbnode_t *);
void (*rotatefn[2])(rbnode_t **);
} rbtree_t;
static rbnode_t *rbt_min(rbnode_t *n);
static rbnode_t *rbt_next(rbnode_t *n);
static void rbt_rotate_left(rbnode_t **n);
static void rbt_rotate_right(rbnode_t **n);
static void rbt_insert_balance(rbtree_t *tree, rbnode_t *n);
static void rbtree_init(rbtree_t *tree, int(*cmp)(rbnode_t*,rbnode_t*)) {
tree->root = NULL;
tree->cmpfn = cmp;
tree->rotatefn[0] = rbt_rotate_left;
tree->rotatefn[1] = rbt_rotate_right;
}
static rbnode_t *rbtree_insert(rbtree_t *tree, rbnode_t *n) {
rbnode_t **tmp;
RBT_LEFT(n) = RBT_RIGHT(n) = n->parent = NULL;
tmp = &tree->root;
while ((*tmp) != NULL) {
n->parent = *tmp;
int cmp = tree->cmpfn(n, (*tmp));
if (cmp < 0)
tmp = &(RBT_LEFT(*tmp));
else if (cmp > 0)
tmp = &(RBT_RIGHT(*tmp));
else
return *tmp;
}
(*tmp) = n;
n->color = RBN_COLOR_RED;
rbt_insert_balance(tree, n);
return NULL;
}
static void rbtree_move(rbtree_t *dst, rbtree_t *src) {
dst->root = src->root;
dst->cmpfn = src->cmpfn;
dst->rotatefn[0] = rbt_rotate_left;
dst->rotatefn[1] = rbt_rotate_right;
src->root = NULL;
}
rbnode_t *rbt_min(rbnode_t *n) {
if (n == NULL)
return NULL;
while (RBT_LEFT(n) != NULL)
n = RBT_LEFT(n);
return n;
}
rbnode_t *rbt_next(rbnode_t *n) {
if (RBT_RIGHT(n) != NULL) {
n = RBT_RIGHT(n);
while (RBT_LEFT(n) != NULL)
n = RBT_LEFT(n);
} else {
if (n->parent && n == RBT_LEFT(n->parent))
return n->parent;
while (n->parent && n == RBT_RIGHT(n->parent))
n = n->parent;
n = n->parent;
}
return n;
}
void rbt_rotate_left(rbnode_t **n) {
rbnode_t *node, *newn;
node = *n;
newn = RBT_RIGHT(node);
*n = newn;
if (RBT_LEFT(newn) != NULL)
RBT_LEFT(newn)->parent = node;
RBT_RIGHT(node) = RBT_LEFT(newn);
RBT_LEFT(newn) = node;
newn->parent = node->parent;
node->parent = newn;
}
void rbt_rotate_right(rbnode_t **n) {
rbnode_t *node, *newn;
node = *n;
newn = RBT_LEFT(node);
*n = newn;
if (RBT_RIGHT(newn) != NULL)
RBT_RIGHT(newn)->parent = node;
RBT_LEFT(node) = RBT_RIGHT(newn);
RBT_RIGHT(newn) = node;
newn->parent = node->parent;
node->parent = newn;
}
void rbt_insert_balance(rbtree_t *tree, rbnode_t *node) {
rbnode_t *uncle, *parent, *grandp;
int dir;
// 1.红黑树中的节点只能有红色和黑色两种颜色
// 2.根节点一定是黑色
// 3.叶子节点一定是黑色节点(所有空节点都涂为黑色,但在具体实现时不对空节点
// 进行处理,可见下示例图)
// 4.红色节点的子节点只能是黑色节点(从这条准则中我们可以得到一些推论:红色
// 节点的父节点也一定是黑色节点,若父节点是红色节点,则父节点显然不满足定
// 义。从某一节点到子节点的路径中不可能有连续的两个红色节点)
// 5.从任意节点到叶子节点的任意路径上,黑色的节点数量一定相同
while ((parent = node->parent) != NULL && RBT_IS_RED(parent)) {
parent->color = RBN_COLOR_BLK;
dir = RBT_DIR(parent);
grandp = parent->parent;
uncle = grandp->children[RBT_REVERSE_DIR(dir)];
if (uncle && RBT_IS_RED(uncle)) {
uncle->color = RBN_COLOR_BLK;
parent->color = RBN_COLOR_BLK;
node = parent->parent;
node->color = RBN_COLOR_RED;
continue;
}
if (dir != RBT_DIR(node)) {
tree->rotatefn[dir](&(grandp->children[dir]));
node = parent;
parent = grandp->children[dir];
}
parent->color = RBN_COLOR_BLK;
grandp->color = RBN_COLOR_RED;
dir = RBT_REVERSE_DIR(dir);
if (grandp->parent != NULL) {
tree->rotatefn[dir](&(grandp->parent->children[RBT_DIR(grandp)]));
} else
tree->rotatefn[dir](&tree->root);
}
tree->root->color = RBN_COLOR_BLK;
}
#ifdef cpluscplus
}
#endif
#endif //LIBNE_RBTREE_H