紅黑樹的應用：
1、利用key_value對，快速查找，O(logn)
- socket與客戶端id之間，形成映射關系(socket, id)
-
內存分配管理
- 一整塊內存，不斷分配小塊
- 每分配一次，就加入到紅黑樹
- 釋放的時候，在紅黑樹找到相應的塊，然后去釋放
2、利用紅黑樹中序遍歷是順序的特性
-
進程的調度
- 進程處于等待狀態，每個進程都有等待的時間，在未來某個時刻會運行，將這些進程利用紅黑樹組織起來
- 在某個時刻，找到對應時刻的節點，然后中序遍歷，就可以把該節點之前的節點全部運行到。
3、nginx定時器
為什么使用紅黑樹不使用哈希表？
- 極少情況下，需要key是有序的，如定時器
二叉排序樹（bstree）
- 左子樹 < 根 < 右子樹
- 中序遍歷結果是順序的
-
極端情況下，如果順序插入，結果就成了鏈表
- 為了解決這個問題，引入了紅黑樹
紅黑樹性質
- 每個節點是紅色的或黑色的
- 根節點是黑色的
- 葉子節點是黑色的
- 紅色節點的兩個子節點必須是黑色的
-
對每個節點，該節點到其子孫節點的所有路徑上的包含相同數目的黑節點（黑高相同）
- 最短路徑就是全黑
- 最長路徑就是黑紅相間
如何證明紅黑樹的正確性？
- 采用歸納法
左旋與右旋
- 改變三個方向，六根指針
紅黑樹的插入：
- 插入節點的時候，原先的樹是滿足紅黑樹性質的
- 插入節點的顏色是紅色更容易滿足紅黑樹的性質
- 插入的節點是紅色，且其父節點也是紅色的時候，需要調整
插入有三種情況：
- 叔父節點是紅色
- 叔父節點是黑色，且祖父節點，父節點和插入節點不是一條直線
- 叔父節點是黑色，且祖父節點，父節點和插入節點是一條直線
平衡二叉樹：
- 內部不是color，而是一個high記錄高度，如果左右子樹高度相差超過1，就需要調整。
紅黑樹的刪除：
- 什么是刪除節點? y-> y是z的后繼節點
-
什么是軸心節點? x是y的右子樹
- 如果x是紅色，把x變成黑色
- 如果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
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
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
|
#include <stdio.h>#include <stdlib.h>#include <string.h>#define RED 1#define BLACK 2typedef int KEY_TYPE;typedef struct _rbtree_node { unsigned char color; struct _rbtree_node *right; struct _rbtree_node *left; struct _rbtree_node *parent; KEY_TYPE key; void *value;} rbtree_node;typedef struct _rbtree { rbtree_node *root; rbtree_node *nil;} rbtree;rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) { while (x->left != T->nil) { x = x->left; } return x;}rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) { while (x->right != T->nil) { x = x->right; } return x;}rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) { rbtree_node *y = x->parent; if (x->right != T->nil) { return rbtree_mini(T, x->right); } while ((y != T->nil) && (x == y->right)) { x = y; y = y->parent; } return y;}void rbtree_left_rotate(rbtree *T, rbtree_node *x) { rbtree_node *y = x->right; // x --> y , y --> x, right --> left, left --> right x->right = y->left; //1 1 if (y->left != T->nil) { //1 2 y->left->parent = x; } y->parent = x->parent; //1 3 if (x->parent == T->nil) { //1 4 T->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; //1 5 x->parent = y; //1 6}void rbtree_right_rotate(rbtree *T, rbtree_node *y) { rbtree_node *x = y->left; y->left = x->right; if (x->right != T->nil) { x->right->parent = y; } x->parent = y->parent; if (y->parent == T->nil) { T->root = x; } else if (y == y->parent->right) { y->parent->right = x; } else { y->parent->left = x; } x->right = y; y->parent = x;}void rbtree_insert_fixup(rbtree *T, rbtree_node *z) { while (z->parent->color == RED) { //z ---> RED if (z->parent == z->parent->parent->left) { rbtree_node *y = z->parent->parent->right; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; //z --> RED } else { if (z == z->parent->right) { z = z->parent; rbtree_left_rotate(T, z); } z->parent->color = BLACK; z->parent->parent->color = RED; rbtree_right_rotate(T, z->parent->parent); } }else { rbtree_node *y = z->parent->parent->left; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; //z --> RED } else { if (z == z->parent->left) { z = z->parent; rbtree_right_rotate(T, z); } z->parent->color = BLACK; z->parent->parent->color = RED; rbtree_left_rotate(T, z->parent->parent); } } } T->root->color = BLACK;}void rbtree_insert(rbtree *T, rbtree_node *z) { rbtree_node *y = T->nil; rbtree_node *x = T->root; while (x != T->nil) { y = x; if (z->key < x->key) { x = x->left; } else if (z->key > x->key) { x = x->right; } else { //Exist return ; } } z->parent = y; if (y == T->nil) { T->root = z; } else if (z->key < y->key) { y->left = z; } else { y->right = z; } z->left = T->nil; z->right = T->nil; z->color = RED; rbtree_insert_fixup(T, z);}void rbtree_delete_fixup(rbtree *T, rbtree_node *x) { while ((x != T->root) && (x->color == BLACK)) { if (x == x->parent->left) { rbtree_node *w= x->parent->right; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rbtree_left_rotate(T, x->parent); w = x->parent->right; } if ((w->left->color == BLACK) && (w->right->color == BLACK)) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; rbtree_right_rotate(T, w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; rbtree_left_rotate(T, x->parent); x = T->root; } } else { rbtree_node *w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rbtree_right_rotate(T, x->parent); w = x->parent->left; } if ((w->left->color == BLACK) && (w->right->color == BLACK)) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; rbtree_left_rotate(T, w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rbtree_right_rotate(T, x->parent); x = T->root; } } } x->color = BLACK;}rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) { rbtree_node *y = T->nil; rbtree_node *x = T->nil; if ((z->left == T->nil) || (z->right == T->nil)) { y = z; } else { y = rbtree_successor(T, z); } if (y->left != T->nil) { x = y->left; } else if (y->right != T->nil) { x = y->right; } x->parent = y->parent; if (y->parent == T->nil) { T->root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } if (y != z) { z->key = y->key; z->value = y->value; } if (y->color == BLACK) { rbtree_delete_fixup(T, x); } return y;}rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) { rbtree_node *node = T->root; while (node != T->nil) { if (key < node->key) { node = node->left; } else if (key > node->key) { node = node->right; } else { return node; } } return T->nil;}void rbtree_traversal(rbtree *T, rbtree_node *node) { if (node != T->nil) { rbtree_traversal(T, node->left); printf("key:%d, color:%d\n", node->key, node->color); rbtree_traversal(T, node->right); }}int main() { int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15}; rbtree *T = (rbtree *)malloc(sizeof(rbtree)); if (T == NULL) { printf("malloc failed\n"); return -1; } T->nil = (rbtree_node*)malloc(sizeof(rbtree_node)); T->nil->color = BLACK; T->root = T->nil; rbtree_node *node = T->nil; int i = 0; for (i = 0;i < 20;i ++) { node = (rbtree_node*)malloc(sizeof(rbtree_node)); node->key = keyArray[i]; node->value = NULL; rbtree_insert(T, node); } rbtree_traversal(T, T->root); printf("----------------------------------------\n"); for (i = 0;i < 20;i ++) { rbtree_node *node = rbtree_search(T, keyArray[i]); rbtree_node *cur = rbtree_delete(T, node); free(cur); rbtree_traversal(T, T->root); printf("----------------------------------------\n"); } } |
總結
到此這篇關于C++實現紅黑樹的文章就介紹到這了,更多相關C++實現紅黑樹內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://www.cnblogs.com/ZGreMount/p/15488553.html
