正文

C++实现红黑树应用实例代码

︶ㄣ米米素材网 メ
米米素材网V管理员 / 阅读
0715

红黑树它一种特殊的二叉查找树,这意味着它满足二叉查找树的特征,但是也有许多自己的特性,这篇文章主要给大家介绍了关于C++实现红黑树的相关资料,需要的朋友可以参考下

红黑树的应用：

1、利用key_value对，快速查找，O(logn)

  1. socket与客户端id之间，形成映射关系(socket, id)
  2. 内存分配管理
    1. 一整块内存，不断分配小块
    2. 每分配一次，就加入到红黑树
    3. 释放的时候，在红黑树找到相应的块，然后去释放

2、利用红黑树中序遍历是顺序的特性

  1. 进程的调度
    1. 进程处于等待状态，每个进程都有等待的时间，在未来某个时刻会运行，将这些进程利用红黑树组织起来
    2. 在某个时刻，找到对应时刻的节点，然后中序遍历，就可以把该节点之前的节点全部运行到。

3、nginx定时器

为什么使用红黑树不使用哈希表？

  • 极少情况下，需要key是有序的，如定时器

二叉排序树（bstree）

  1. 左子树 < 根 < 右子树
  2. 中序遍历结果是顺序的
  3. 极端情况下，如果顺序插入，结果就成了链表
    1. 为了解决这个问题，引入了红黑树

红黑树性质

  1. 每个节点是红色的或黑色的
  2. 根节点是黑色的
  3. 叶子节点是黑色的
  4. 红色节点的两个子节点必须是黑色的
  5. 对每个节点，该节点到其子孙节点的所有路径上的包含相同数目的黑节点（黑高相同）
    1. 最短路径就是全黑
    2. 最长路径就是黑红相间

如何证明红黑树的正确性？

  • 采用归纳法

左旋与右旋

  • 改变三个方向，六根指针

红黑树的插入：

  1. 插入节点的时候，原先的树是满足红黑树性质的
  2. 插入节点的颜色是红色更容易满足红黑树的性质
  3. 插入的节点是红色，且其父节点也是红色的时候，需要调整

插入有三种情况：

  1. 叔父节点是红色
  2. 叔父节点是黑色，且祖父节点，父节点和插入节点不是一条直线
  3. 叔父节点是黑色，且祖父节点，父节点和插入节点是一条直线

平衡二叉树：

  • 内部不是color，而是一个high记录高度，如果左右子树高度相差超过1，就需要调整。

红黑树的删除：

  1. 什么是删除节点? y-> y是z的后继节点
  2. 什么是轴心节点? x是y的右子树
    1. 如果x是红色，把x变成黑色
    2. 如果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             2
 
typedef 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