红黑树的代码实现
分类:
IT文章
•
2022-03-30 19:05:25
红黑树满足一下规则
1. 每个节点不是红色就是黑色
2.根节点为黑色
3.如果节点为红，其子节点必须为黑
4.任一节点至nil的任何路径，所包含的黑节点数必须相同。
5.叶子节点nil为黑色
当破坏了平衡时，在调整的时候需要用到左旋和右旋
左旋：
右旋：
代码实现：
![]()
1 void rb_tree::__rb_tree_rotate_left(link_type x) {
2 link_type y = x->right;
3 x->right = y->left;
4 if(y->left != nil) {
5 y->left->parent = x;
6 }
7 y->parent = x->parent;
8 if(x == root) {
9 root = y;
10 } else if(x == x->parent->left) {
11 x->parent->left = y;
12 } else {
13 x->parent->right = y;
14 }
15 x->parent = y;
16 y->left = x;
17 }
左旋转
![]()
1 void rb_tree::__rb_tree_rotate_right(link_type x) {
2 link_type y = x->left;
3 x->left = y->right;
4 if(x->left != nil) {
5 x->left->parent = x;
6 }
7 y->parent = x->parent;
8 if(x == root) {
9 root = y;
10 } else if(x->parent->left == x) {
11 x->parent->left = y;
12 } else {
13 x->parent->right = y;
14 }
15
16 x->parent = y;
17 y->right = x;
18 }
右旋转
插入节点时，可能会破坏红黑树的结构，如下图，在插入3,8,35,75的时候，就破坏了树的结构：
设定如下用语：新节点为X，其父节点为P，组父节点为G，伯父节点为S，曾祖父节点GG。
根据红黑树规则4，X必为红，若P也为红(这就违反了规则3，必须调整树形)，则G必为黑。于是，根据X的插入位置及外围节点的颜色，有了以下三种考虑。
情况1：S为黑且X为外侧插入。
对此情况，我们先对P，G做一次单旋转，并更改P，G的颜色，即可重新满足红黑树的规则3。
情况2：S为黑且X为内侧插入。
对此情况，我们必须先对P，X做一次单旋转并更改G，X颜色，再将结果对G做一次单旋转，即可重新满足红黑树规则3.
情况3：S为红，不考虑X是否内外测。
对此情况，我们需将P和S设置为黑色，G设置为红色，并将X设置成G继续判断即可。
以下为插入和调整代码
![]()
1 void rb_tree::insert(key_type __x) {
2 link_type new_node;
3 link_type new_parent = nil;
4 link_type pos = root;
5 while (pos != nil) {
6 new_parent = pos;
7 if(__x < pos->key) {
8 pos = pos->left;
9 } else if(__x > pos->key) {
10 pos = pos->right;
11 } else {
12 fprintf(stderr, "Error: node %d already in the tree.
", __x);
13 exit(1);
14 }
15 }
16 new_node = get_node(__x);
17 new_node->parent = new_parent;
18 if(new_parent == nil) {
19 root = new_node;
20 } else if(__x < new_parent->key) {
21 new_parent->left = new_node;
22 } else {
23 new_parent->right = new_node;
24 }
25 __rb_tree_rebalance(new_node);
26 ++ node_count;
27 }
插入
![]()
1 void rb_tree::__rb_tree_rebalance(link_type x) {
2 while (x != root && x->parent->color == __rb_tree_red) {
3 if(x->parent == x->parent->parent->left) {
4 link_type s = x->parent->parent->right;
5 if(s && s->color == __rb_tree_red) {
6 x->parent->color = __rb_tree_black;
7 s->color = __rb_tree_black;
8 x->parent->parent->color = __rb_tree_red;
9 x = x->parent->parent;
10 } else {
11 if(x == x->parent->right) {
12 x = x->parent;
13 __rb_tree_rotate_left(x);
14 }
15 x->parent->color = __rb_tree_black;
16 x->parent->parent->color = __rb_tree_red;
17 __rb_tree_rotate_right(x->parent->parent);
18 }
19 } else {
20 link_type s = x->parent->parent->left;
21 if(s && s->color == __rb_tree_red) {
22 s->color = __rb_tree_black;
23 x->parent->color = __rb_tree_black;
24 x->parent->parent->color = __rb_tree_red;
25 x = x->parent->parent;
26 } else {
27 if(x == x->parent->left) {
28 x = x->parent;
29 __rb_tree_rotate_right(x);
30 }
31 x->parent->color = __rb_tree_black;
32 x->parent->parent->color = __rb_tree_red;
33 __rb_tree_rotate_left(x->parent->parent);
34 }
35 }
36 }
37 root->color = __rb_tree_black;
38 }
调整结构
删除节点的操作和二叉搜索树的原理一样，只是加了旋转和着色。
1.当删除节点没有子节点树直接删除，用nil代替当前位置，
2.当删除节点只有一个子树时，用子节点代替当前位置，
3.当删除节点有两个字数时，找到它的后继节点，将它们继续更换，那么就变成了删除后继节点，而且后继节点至多有一个字数，这就转换成前两种情况了。
假设删除节点为y，子节点为x。
如果y是红色的，那就不会破坏结构。
如果y是黑色的，x是红色的，那么将x变为黑色就OK了
如果y是黑色的，x是黑色且是根，不会破坏结构。
否则的话就有下面四种情况：
情况1：X为黑色，S为红色。
如果X是P的左孩子，将S设置为黑色，X设置为红色，对P进行左旋装，重新设置S
如果X是P的右孩子，将S设置为黑色，X设置为红色，对P进行右旋转，重新设置S
情况2：X为黑色，S为黑色，并且S的两个孩子都为黑色。
将S设置为红色，设置X为P。
情况3：X为黑色，S为黑色。
如果X是P的左孩子，S的左孩子为红色，右孩子为黑色。
将S的左孩子设置为黑色，S设置为红色，对S进行右旋转，重新设置S。
如果X是P的右孩子，S的右孩子为红色，左孩子为黑色。
将S的右孩子设置为黑色，S设置为红色，对S进行左旋转，重新设置S。
情况4：X为黑色，S为黑色。
如果X是P的左孩子，S的右孩子为红色，左孩子任意。
将P的颜色赋值给S，设置P的颜色为黑色，S的右孩子为黑色，对P进行左旋转，设置X为root
如果X是P的右孩子，S的左孩子为红色，右孩子任意。
将P的颜色赋值给S，设置P的颜色为黑色，S的左孩子为红色，对P进行右旋转，设置X为root
其实X是P的左孩子或者右孩子，它们的操作都是对应的。
以下是删除代码和删除后调整的代码
![]()
1 rb_tree::link_type rb_tree::erase(key_type __x) {
2 link_type dead = find(__x);
3 if(dead == nil) {
4 fprintf(stderr, "Error,node %d does not exist
", __x);
5 return nil;
6 }
7 link_type x = nil, y = nil;
8 if(dead->left == nil || dead->right == nil) {
9 y = dead;
10 } else {
11 y = __get_next_node(dead);
12 }
13 if(y->left == nil) {
14 x = y->right;
15 }else if(y->right == nil) {
16 x = y->left;
17 }
18 // if(x) {
19 x->parent = y->parent;
20 // }
21 if(y->parent == nil) {
22 root = x;
23 } else if(y == y->parent->left) {
24 y->parent->left = x;
25 } else if(y == y->parent->right) {
26 y->parent->right = x;
27 }
28
29 if(dead != y) {
30 dead->key = y->key;
31 }
32 if(y->color == __rb_tree_black) {
33 __rb_tree_delete_fixup(x);
34 }
35 return y;
36 }
删除
![]()
1 void rb_tree::__rb_tree_delete_fixup(link_type x) {
2 // printf("nil:%d
", x==nil);
3 while (x != root && x->color == __rb_tree_black) {
4 if(x == x->parent->left) {
5 link_type s = x->parent->right;
6 if(s->color == __rb_tree_red) {
7 s->color = __rb_tree_black;
8 x->parent->color = __rb_tree_red;
9 __rb_tree_rotate_left(x->parent);
10 s = x->parent->right;
11 }
12
13 if(s->left->color == __rb_tree_black && s->right->color == __rb_tree_black) {
14 s->color = __rb_tree_red;
15 x = x->parent;
16 } else {
17 if(s->right->color == __rb_tree_black) {
18 s->left->color = __rb_tree_black;
19 s->color = __rb_tree_red;
20 __rb_tree_rotate_right(s);
21 s = x->parent->right;
22 }
23
24 s->color = x->parent->color;
25 x->parent->color = __rb_tree_black;
26 s->right->color = __rb_tree_black;
27 __rb_tree_rotate_left(x->parent);
28 x = root;
29 }
30 } else {
31 link_type s = x->parent->left;
32 if(s->color == __rb_tree_red) {
33 s->color = __rb_tree_black;
34 x->parent->color = __rb_tree_red;
35 __rb_tree_rotate_right(x->parent);
36 s = x->parent->left;
37 }
38
39 if(s->left->color == __rb_tree_black && s->right->color == __rb_tree_black) {
40 s->color = __rb_tree_red;
41 x = x->parent;
42 } else {
43 if(s->left->color == __rb_tree_black) {
44 s->right->color = __rb_tree_black;
45 s->color = __rb_tree_red;
46 __rb_tree_rotate_left(s);
47 s = x->parent->left;
48 }
49
50 s->color = x->parent->color;
51 x->parent->color = __rb_tree_black;
52 s->left->color = __rb_tree_black;
53 __rb_tree_rotate_right(x->parent);
54 x = root;
55 }
56 }
57 }
58 x->color = __rb_tree_black;
59 }
调整代码
以下是两个完整的代码，只需 #include "rb_tree.h"即可使用。
![]()
1 //
2 // Created by starry on 2019/8/24.
3 //
4
5 #ifndef TREE_PTR_H
6 #define TREE_PTR_H
7
8 #include <stdio.h>
9 //#define nil NULL
10
11 typedef bool __rb_tree_color_type;
12 const __rb_tree_color_type __rb_tree_red = false;
13 const __rb_tree_color_type __rb_tree_black = true;
14
15 struct __rb_tree_node{
16 typedef __rb_tree_color_type color_type;
17 typedef __rb_tree_node* rb_node_ptr;
18 typedef int key_type;
19
20 key_type key;
21 color_type color;
22 rb_node_ptr parent;
23 rb_node_ptr left, right;
24 };
25
26 class rb_tree{
27 public:
28 typedef __rb_tree_node rb_tree_node;
29 typedef __rb_tree_color_type color_type;
30
31 typedef rb_tree_node* link_type;
32 typedef size_t size_type;
33 typedef void* void_pointer;
34 typedef int key_type;
35
36 public:
37 rb_tree();
38
39 bool empty() const { return node_count == 0;}
40 size_type size() const { return node_count;}
41
42 void clear();
43 void insert(key_type __x);
44 link_type erase(key_type __x);
45 link_type find(key_type __x);
46 void draw();
47 int rb_height(link_type x);
48
49 private:
50
51 link_type get_node(key_type __x);
52 void __rb_tree_rebalance(link_type x);
53 void __rb_tree_rotate_left(link_type x);
54 void __rb_tree_rotate_right(link_type x);
55 void __rb_tree_delete_fixup(link_type x);
56 void __serialize(link_type x);
57 void __delete(link_type x);
58 link_type __get_next_node(link_type x);
59
60 size_type node_count;
61 link_type root;
62 link_type nil;
63 };
64
65
66 #endif //TREE_PTR_H
rb_tree.h
![]()
1 //
2 // Created by starry on 2019/8/24.
3 //
4
5 #include "rb_tree.h"
6 #include <stdlib.h>
7 #include <stdio.h>
8
9 void rb_tree::draw() {
10 __serialize(root);
11 printf("
");
12 }
13
14 int rb_tree::rb_height(link_type x) {
15 if(x == nil)
16 return 0;
17 int l = rb_height(x->left);
18 int r = rb_height(x->right);
19 return 1 + (l>r?l:r);
20 }
21
22 rb_tree::rb_tree() {
23 nil = (link_type)malloc(sizeof(rb_tree_node));
24 nil->left = nil->right = nil->parent = nil;
25 nil->color = __rb_tree_black;
26 root = nil;
27 node_count = 0;
28 }
29
30 void rb_tree::clear() {
31 __delete(root);
32 root = nil;
33 node_count = 0;
34 }
35
36 void rb_tree::__delete(link_type x) {
37 if(x == nil) return;
38 __delete(x->left);
39 __delete(x->right);
40 free(x);
41 }
42
43 rb_tree::link_type rb_tree::find(key_type __x) {
44 link_type pos = root;
45 while (pos != nil) {
46 if(pos->key == __x) return pos;
47 else if(pos->key > __x) pos = pos->left;
48 else if(pos->key < __x) pos = pos->right;
49 }
50 return pos;
51 }
52
53 void rb_tree::insert(key_type __x) {
54 link_type new_node;
55 link_type new_parent = nil;
56 link_type pos = root;
57 while (pos != nil) {
58 new_parent = pos;
59 if(__x < pos->key) {
60 pos = pos->left;
61 } else if(__x > pos->key) {
62 pos = pos->right;
63 } else {
64 fprintf(stderr, "Error: node %d already in the tree.
", __x);
65 exit(1);
66 }
67 }
68 new_node = get_node(__x);
69 new_node->parent = new_parent;
70 if(new_parent == nil) {
71 root = new_node;
72 } else if(__x < new_parent->key) {
73 new_parent->left = new_node;
74 } else {
75 new_parent->right = new_node;
76 }
77 __rb_tree_rebalance(new_node);
78 ++ node_count;
79 }
80
81 rb_tree::link_type rb_tree::erase(key_type __x) {
82 link_type dead = find(__x);
83 if(dead == nil) {
84 fprintf(stderr, "Error,node %d does not exist
", __x);
85 return nil;
86 }
87 link_type x = nil, y = nil;
88 if(dead->left == nil || dead->right == nil) {
89 y = dead;
90 } else {
91 y = __get_next_node(dead);
92 }
93 if(y->left == nil) {
94 x = y->right;
95 }else if(y->right == nil) {
96 x = y->left;
97 }
98 // if(x) {
99 x->parent = y->parent;
100 // }
101 if(y->parent == nil) {
102 root = x;
103 } else if(y == y->parent->left) {
104 y->parent->left = x;
105 } else if(y == y->parent->right) {
106 y->parent->right = x;
107 }
108
109 if(dead != y) {
110 dead->key = y->key;
111 }
112 if(y->color == __rb_tree_black) {
113 __rb_tree_delete_fixup(x);
114 }
115 return y;
116 }
117
118 void rb_tree::__rb_tree_delete_fixup(link_type x) {
119 while (x != root && x->color == __rb_tree_black) {
120 if(x == x->parent->left) {
121 link_type s = x->parent->right;
122 if(s->color == __rb_tree_red) {
123 s->color = __rb_tree_black;
124 x->parent->color = __rb_tree_red;
125 __rb_tree_rotate_left(x->parent);
126 s = x->parent->right;
127 }
128
129 if(s->left->color == __rb_tree_black && s->right->color == __rb_tree_black) {
130 s->color = __rb_tree_red;
131 x = x->parent;
132 } else {
133 if(s->right->color == __rb_tree_black) {
134 s->left->color = __rb_tree_black;
135 s->color = __rb_tree_red;
136 __rb_tree_rotate_right(s);
137 s = x->parent->right;
138 }
139
140 s->color = x->parent->color;
141 x->parent->color = __rb_tree_black;
142 s->right->color = __rb_tree_black;
143 __rb_tree_rotate_left(x->parent);
144 x = root;
145 }
146 } else {
147 link_type s = x->parent->left;
148 if(s->color == __rb_tree_red) {
149 s->color = __rb_tree_black;
150 x->parent->color = __rb_tree_red;
151 __rb_tree_rotate_right(x->parent);
152 s = x->parent->left;
153 }
154
155 if(s->left->color == __rb_tree_black && s->right->color == __rb_tree_black) {
156 s->color = __rb_tree_red;
157 x = x->parent;
158 } else {
159 if(s->left->color == __rb_tree_black) {
160 s->right->color = __rb_tree_black;
161 s->color = __rb_tree_red;
162 __rb_tree_rotate_left(s);
163 s = x->parent->left;
164 }
165
166 s->color = x->parent->color;
167 x->parent->color = __rb_tree_black;
168 s->left->color = __rb_tree_black;
169 __rb_tree_rotate_right(x->parent);
170 x = root;
171 }
172 }
173 }
174 x->color = __rb_tree_black;
175 }
176
177 rb_tree::link_type rb_tree::__get_next_node(link_type x) {
178 if(x == nil) return nil;
179 link_type next = nil;
180 if(x->right != nil) {
181 x = x->right;
182 while(x->left != nil) x = x->left;
183 next = x;
184 } else {
185 link_type y = x->parent;
186 while (y && x == y->right) {
187 x = y;
188 y = y->parent;
189 }
190 next = y;
191 }
192 return next;
193 }
194
195 void rb_tree::__serialize(link_type x) {
196 if(x == nil) {
197 printf("#$");
198 return;
199 }
200 printf("(%d,%d)",x->key,x->color);
201 __serialize(x->left);
202 __serialize(x->right);
203 }
204
205 rb_tree::link_type rb_tree::get_node(key_type __x) {
206 link_type ret;
207 if((ret = (link_type)malloc(sizeof(rb_tree_node))) == NULL) {
208 fprintf(stderr, "Error: out of memory.
");
209 exit(1);
210 }
211 ret->left = nil;
212 ret->right = nil;
213 ret->parent = nil;
214 ret->color = __rb_tree_red;
215 ret->key = __x;
216 return ret;
217 }
218
219 void rb_tree::__rb_tree_rebalance(link_type x) {
220 while (x != root && x->parent->color == __rb_tree_red) {
221 if(x->parent == x->parent->parent->left) {
222 link_type s = x->parent->parent->right;
223 if(s && s->color == __rb_tree_red) {
224 x->parent->color = __rb_tree_black;
225 s->color = __rb_tree_black;
226 x->parent->parent->color = __rb_tree_red;
227 x = x->parent->parent;
228 } else {
229 if(x == x->parent->right) {
230 x = x->parent;
231 __rb_tree_rotate_left(x);
232 }
233 x->parent->color = __rb_tree_black;
234 x->parent->parent->color = __rb_tree_red;
235 __rb_tree_rotate_right(x->parent->parent);
236 }
237 } else {
238 link_type s = x->parent->parent->left;
239 if(s && s->color == __rb_tree_red) {
240 s->color = __rb_tree_black;
241 x->parent->color = __rb_tree_black;
242 x->parent->parent->color = __rb_tree_red;
243 x = x->parent->parent;
244 } else {
245 if(x == x->parent->left) {
246 x = x->parent;
247 __rb_tree_rotate_right(x);
248 }
249 x->parent->color = __rb_tree_black;
250 x->parent->parent->color = __rb_tree_red;
251 __rb_tree_rotate_left(x->parent->parent);
252 }
253 }
254 }
255 root->color = __rb_tree_black;
256 }
257
258 void rb_tree::__rb_tree_rotate_left(link_type x) {
259 link_type y = x->right;
260 x->right = y->left;
261 if(y->left != nil) {
262 y->left->parent = x;
263 }
264 y->parent = x->parent;
265 if(x == root) {
266 root = y;
267 } else if(x == x->parent->left) {
268 x->parent->left = y;
269 } else {
270 x->parent->right = y;
271 }
272 x->parent = y;
273 y->left = x;
274 }
275
276 void rb_tree::__rb_tree_rotate_right(link_type x) {
277 link_type y = x->left;
278 x->left = y->right;
279 if(x->left != nil) {
280 x->left->parent = x;
281 }
282 y->parent = x->parent;
283 if(x == root) {
284 root = y;
285 } else if(x->parent->left == x) {
286 x->parent->left = y;
287 } else {
288 x->parent->right = y;
289 }
290
291 x->parent = y;
292 y->right = x;
293 }
rb_tree.cpp
