红黑树

做过简单的测试，应该没什么大问题。想想算法导论这部分看了很久，又撸过AVL写起来还是有点小迷糊，也在迷糊中学了点东西。总之继续吧

Rb_tree.h

  1 #pragma once
  2 
  3 #include <iostream>
  4 
  5 enum color{RED,BLACK};
  6 
  7 template<class T>
  8 struct node {
  9     node* p;
 10     node *left, *right;
 11     T key;
 12     color c;
 13     int siz;
 14     
 15     node(){}
 16     node(T key):p(0),left(0),right(0), key(key){}
 17 };
 18 
 19 template<class T>
 20 class RbTree {
 21 private:
 22     //typedef struct node node;
 23     node<T>* Root;
 24     node<T>* Nil;//代表本树的nullptr，主要方便去除后的平衡调整
 25 public:
 26     RbTree() :Nil(new node<T>()), Root(0) {
 27         Root = Nil;
 28         Nil->c = BLACK;//叶节点
 29         Nil->siz = 0;
 30     }
 31     ~RbTree() {
 32         destroy(Root); 
 33         delete Nil;
 34     }
 35     
 36     void preorder() { _preorder(Root); }
 37     void insert(T key) {
 38         node<T>* xixi = new node<T>(key);
 39         if (xixi == 0) {//申请内存失败
 40             std::cerr << "new node fail!" << endl;
 41             return;
 42         }
 43 
 44         _insert(xixi);
 45     }
 46     void remove(T key) {
 47         _remove(key);
 48     }
 49     //找到第i顺序统计量对应的关键字
 50     T os_select(int i) { return (select(Root, i))->key; }
 51     //确定关键字key的顺序统计量
 52     int os_rank(T key) { return rank(find(key)); }
 53 
 54 private:
 55     void _preorder(node<T>* u);
 56     void destroy(node<T>* u);
 57     void _insert(node<T>* u);
 58     void _remove(T key);
 59     void leftrotate(node<T>* u);
 60     void rightrotate(node<T>* u);
 61     void transplant(node<T>* u, node<T>* v);
 62     void rb_delete_fixup(node<T>* x);
 63     void rb_insert_fixup(node<T>* x);
 64     node<T>* minimum(node<T>* u);
 65     node<T>* find(T key);
 66     void size_fixup(node<T>* x,int dealta_siz);//添加第二个参数可以给delete和Insert一起用
 67     //找到顺序统计量i的节点
 68     node<T>* select(node<T>* root, int i);
 69     //确定u的顺序统计量
 70     int rank(node<T>* u);
 71 };
 72 template<class T>
 73 node<T>* RbTree<T>::select(node<T>* root, int i) {
 74     if (root->left->siz + 1 == i)return root;
 75     //else
 76     if (i - 1 < root->left->siz)return select(root->left, i);
 77     else return select(root->right, i - 1 - root->left->siz);
 78 }
 79 
 80 template<class T>
 81 int RbTree<T>::rank(node<T>* u) {
 82     int r = u->left->siz + 1;
 83     while (u != Root) {
 84         if (u == u->p->right)
 85             r += u->p->left->siz + 1;
 86         u = u->p;
 87     }
 88     return r;
 89 }
 90 
 91 template<class T>
 92 void RbTree<T>::size_fixup(node<T>* x, int delta_siz) {
 93     while (x->p != Nil) {
 94         x = x->p;
 95         x->siz += delta_siz;
 96     }
 97 }
 98 
 99 template<class T>
100 void RbTree<T>::rb_delete_fixup(node<T>* x) {
101     size_fixup(x, -1);//沿简单路径向上修改siz属性
102 
103     while (x != Root&&x->c == BLACK) {
104         node<T>* w;
105         if (x == x->p->left) {
106             w = x->p->right;
107             if (w->c == RED) {//case 1
108                 w->c = BLACK;
109                 x->p->c = RED;
110                 leftrotate(x->p);
111                 w = x->p->right;//重置
112             }
113             //case 2 3 4,对应w节点颜色为黑色
114                 if (w->left->c == BLACK&&w->right->c == BLACK) {
115                     w->c = RED;
116                     x = x->p;//上移
117                 }
118                 else {
119                     if (w->right->c == BLACK) {
120                         w->c = RED;
121                         w->left->c = BLACK;
122                         rightrotate(w);
123                         w = x->p->right;
124                     }
125                     w->c = x->p->c;
126                     x->p->c = BLACK;
127                     w->right->c = BLACK;
128                     leftrotate(x->p);
129                     x = Root;//退出循环
130                 }        
131         }
132         else {//
133             w = x->p->left;
134             if (w->c == RED) {
135                 x->p->c = RED;
136                 w->c = BLACK;
137                 rightrotate(x->p);
138                 w = x->p->left;
139             }
140             if (w->right->c == BLACK&&w->left->c == BLACK) {
141                 w->c = RED;
142                 x = x->p;
143             }
144             else {
145                 if (w->left->c == BLACK) {
146                     w->c = RED;
147                     w->right->c = BLACK;
148                     leftrotate(w);
149                     w = x->p->left;
150                 }//case 4
151                 w->c = x->p->c;
152                 x->p->c = BLACK;
153                 w->left->c = BLACK;
154                 rightrotate(x->p);
155                 x = Root;
156             }
157         }
158     }
159 
160     x->c = BLACK;
161 }
162 
163 template<class T>
164 node<T>* RbTree<T>::minimum(node<T>* u) {
165     if (u == Nil)return Nil;
166     while (u->left != Nil)
167         u = u->left;
168     return u;
169 }
170 
171 template<class T>
172 node<T>* RbTree<T>::find(T key) {
173     node<T>* u = Root;
174     while (u != Nil&&u->key != key) {
175         if (u->key > key)
176             u = u->left;
177         else u = u->right;
178     }
179     if (u == Nil) 
180         std::cout << "找不到key值为" << key << "的节点" << std::endl;
181     return u;
182 }
183 
184 template<class T>
185 void RbTree<T>::_remove(T key) {
186     node<T>* z = find(key);
187     if (z == Nil)return;//找不到要删除的节点
188     node<T>* y = z;
189     node<T>* x;
190     color original_c = y->c;
191     if (z->left == Nil) {
192         x = z->right;
193         transplant(z, z->right);
194     }
195     else if (z->right == Nil) {
196         x = z->left;
197         transplant(z, z->left);
198     }
199     else {
200         y = minimum(z->right);//后继点，用于代替z
201         original_c = y->c;
202         x = y->right;
203         if (y == z->right)
204             x->p = y;
205         else {
206             y->right = z->right;
207             y->right->p = y;
208             transplant(y, x);//顺序很重要，x可能是空结点
209         }
210 
211         transplant(z, y);
212         y->left = z->left;
213         y->left->p = y;
214         y->c = z->c;
215     }
216     if (original_c == BLACK)
217         rb_delete_fixup(x);
218 
219     delete z;
220 }
221 
222 template<class T>
223 void RbTree<T>::rb_insert_fixup(node<T>* x) {
224     size_fixup(x, 1);
225 
226     while (x->p->c == RED) {//此条件可保证x->p->必定存在
227         if (x->p == x->p->p->left) {//x的父节点在x的爷爷的左侧
228             node<T>* y = x->p->p->right;//叔节点哦
229             if (y->c == RED) {//case 1
230                 y->c = BLACK;
231                 x->p->c = BLACK;
232                 x->p->p->c = RED;
233                 x = x->p->p;//节点上移
234             }
235             else{
236                 if (x == x->p->right){//case 2
237                     x = x->p;
238                     leftrotate(x);
239                 }
240                 x->p->c = BLACK;
241                 x->p->p->c = RED;
242                 rightrotate(x->p->p);
243             }
244         }
245         else {//x->p==x->p->p->right
246             node<T>* y = x->p->p->left;
247             if (y->c == RED) {//case 1
248                 y->c = BLACK;
249                 x->p->c = BLACK;
250                 x->p->p->c = RED;
251                 x = x->p->p;
252             }
253             else {//叔节点y为黑色 分两种情况，其中case2可转化为case3
254                 if (x == x->p->left) {//case 2
255                     x = x->p;
256                     rightrotate(x);
257                 }//case 3
258                 x->p->c = BLACK;
259                 x->p->p->c = RED;
260                 leftrotate(x->p->p);
261             }
262         }
263 //while循环
264     }
265     Root->c = BLACK;
266 }
267 
268 template<class T>
269 void RbTree<T>::_insert(node<T>* u) {
270     node<T>* y = Nil;
271     node<T>* x = Root;
272     while (x != Nil) {
273         y = x;
274         if (u->key < x->key)
275             x = x->left;
276         else x = x->right;
277     }
278 
279     u->p = y;
280     if (y == Nil)Root = u;//原树为空
281     else if (u->key < y->key)
282         y->left = u;
283     else
284         y->right = u;
285 
286     u->left = Nil;
287     u->right = Nil;
288     u->c = RED;
289     u->siz = 1;
290 
291     rb_insert_fixup(u);
292 }
293 
294 template<class T>
295 void RbTree<T>::transplant(node<T>* u, node<T>* v) {//建立u->p和v的联系
296     if (u->p == Nil)
297         Root = v;
298     else if (u == u->p->left)
299         u->p->left = v;
300     else 
301         u->p->right = v;
302 
303     v->p = u->p;//对v是Nil的情况不做特殊讨论
304 
305 }
306 
307 template<class T>
308 void RbTree<T>::rightrotate(node<T>* u) {//调用该函数默认左孩子不为Nil
309     node<T>* lc = u->left;
310     lc->p = u->p;
311     if (u->p == Nil)
312         Root = lc;
313     else if (u == u->p->left)
314         u->p->left = lc;
315     else
316         u->p->right = lc;
317 
318     u->left = lc->right;
319     if (lc->right != Nil)u->left->p = u;
320 
321     lc->right = u;
322     u->p = lc;
323     //change the size
324     u->siz = u->left->siz + u->right->siz + 1;
325     lc->siz = lc->left->siz + lc->right->siz + 1;
326 }
327 
328 template<class T>
329 void RbTree<T>::leftrotate(node<T>* u) {//调用该函数默认右孩子不为Nil
330     node<T>* rc = u->right;
331     rc->p = u->p;
332     if (u->p == Nil)
333         Root = rc;
334     else if (u == u->p->left)
335         u->p->left = rc;
336     else
337         u->p->right = rc;
338 
339     u->right = rc->left;
340     if (rc->left != Nil)u->right->p = u;
341 
342     rc->left = u;
343     u->p = rc;
344     //change the size
345     u->siz = u->left->siz + u->right->siz + 1;
346     rc->siz = rc->left->siz + rc->right->siz + 1;
347 }
348 
349 template<class T>
350 void RbTree<T>::destroy(node<T>* u) {
351     if (u == Nil)return;
352     destroy(u->left);
353     destroy(u->right);
354 
355     delete u;
356 }
357 
358 template<class T>
359 void RbTree<T>::_preorder(node<T>* u) {
360     if (u == Nil)return;
361 
362     if (u->p == Nil)std::cout << u->key << "是树根哦" << std::endl;
363     else if (u == u->p->left)std::cout << u->key << "是" << u->p->key << "的左孩子" << std::endl;
364     else std::cout << u->key << "是" << u->p->key << "的右孩子" << std::endl;
365     std::cout << "颜色为" << (u->c == RED ? "红色" : "黑色") << std::endl;
366     std::cout << "大小为" << u->siz << endl;
367     _preorder(u->left);
368     _preorder(u->right);
369 }

test.cpp

 1 #include <iostream>
 2 #include "RB_tree.h"
 3 
 4 using namespace std;
 5 
 6 int main(void) {
 7     RbTree<int> xixi;
 8     xixi.insert(11);
 9     xixi.insert(2);
10     //xixi.insert(1);
11     xixi.insert(1);
12     xixi.insert(7);
13     xixi.insert(5);
14     xixi.insert(8);
15     xixi.insert(4);
16     xixi.insert(14);
17     xixi.insert(15);
18     //xixi.remove(14);
19     //xixi.remove(11);
20     //xixi.remove(2);
21 
22     xixi.preorder();
23     int i;
24 
25     //cout << "请输入一个合法顺序统计量" << endl;
26     /*while (cin >> i) {
27         if (i <= 0)break;
28         cout << "关键字为" << xixi.os_select(i) << endl;
29         cout << "请输入一个合法顺序统计量" << endl;
30     }*/
31 
32     cout << "请输入一个合法关键字" << endl;
33     while (cin >> i) {
34         cout << "该关键字顺序统计量为" << xixi.os_rank(i) << endl;
35         cout << "请输入一个合法关键字" << endl;
36     }
37 
38     return 0;
39 }