红黑树 (洛谷 P3369 【模板】普通平衡树 )

(以前学习的红黑树，在今天写算法大作业的时候用到了，哈哈，即使研究生也要继续学习算法呀）
红黑树的五条性质:
1) 节点颜色为红色或黑色
2) 根节点为黑色
3) 每一个叶子节点两个NIL节点也为黑色
4) 红色节点后继为黑色
5) 从根节点到叶子节点简单路径黑高相同
红黑树是一颗自平衡的二叉查找树, 查询,插入,删除的时间复杂度都为O(logn)
红黑树简直就是一棵神奇的数据结构~~~~~~~~,我很想知道他们的灵感从哪里来的. 据说红黑树是2-3树的变形, RNtree的插入操作类比2-3树我还可以理解.
但BRtree那个删除操作真的好简洁于奇妙~~向这些科学家致敬!!
总结一下:
(1) 插入节点z默认时红色, 可能违反的性质:
1) z的parent节点颜色是红色
2) 根节点是红色
插入时关键要看叔叔节点
(2) 删除节点y,并且用x节点代替,可能违反的性质
1) 经过x的路径,黑高减1
2) x的为红色,x的parent也是红
3) x为根节点,颜色为红色
删除时要看兄弟节点
代码的逻辑时根据算法导论的逻辑写出, 并且经过洛谷P3369习题验证
(这是我提交过的最长代码.....
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define RED 1
  4 #define BLACK 0
  5 #define RBnode node<T> *
  6 
  7 template <class T>
  8 struct node {
  9     T key;
 10     int sum; //sum子树节点数
 11     bool color;
 12     node *p, *left, *right;
 13     node() {
 14         sum = 0; color = BLACK;
 15     }
 16     node(T key, int sum, int color, node *p, node *left, node *right) :
 17         key(key), sum(sum), color(color), p(p), left(left), right(right) {}
 18     void up() {
 19         sum = 1 + left->sum + right->sum; // nil节点不更新
 20     }
 21 };
 22 
 23 template <class T>
 24 class  RBtree {
 25 private:
 26     RBnode rt;
 27     RBnode nil;
 28 public:
 29     RBtree() {
 30         nil = new node<T>();
 31         nil->p = nil->left = nil->right = nil;
 32         rt = nil;
 33     }
 34 
 35     void mid_print(RBnode x) { // 中序遍历
 36         if (x == nil) return;
 37         mid_print(x->left);
 38         cout << "key: " << x->key << " color:" << x->color << " sum: " << x->sum << endl;
 39         mid_print(x->right);
 40     }
 41 
 42     void  my_print() {
 43         mid_print(rt);
 44     }
 45 
 46     void insert(T key) {
 47         RBnode z = new node<T>(key, 1, RED, nil, nil, nil);
 48         RBnode y = nil; // y: x的parent;
 49         RBnode x = rt;
 50         while (x != nil) {
 51             y = x;
 52             if (z->key <= x->key)
 53                 x = x->left;
 54             else
 55                 x = x->right;
 56         }
 57         z->p = y;  // 特别的根节点父节点是nil
 58         if (y == nil)
 59             rt = z;
 60         else if (z->key <= y->key)
 61             y->left = z;
 62         else
 63             y->right = z;
 64         // sum的改变
 65         while (y != nil) {
 66             y->up();
 67             y = y->p;
 68         }
 69         insert_fixup(z);
 70     }
 71 
 72     // 可能违反的性质:
 73     // 1)z的parent节点颜色是红色
 74     // 2)根节点是红色 
 75     void insert_fixup(RBnode z) {  // 插入看叔叔节点 
 76         while (z->p->color == RED) {
 77             if (z->p == z->p->p->left) {
 78                 RBnode uncle = z->p->p->right;
 79                 if (uncle->color == RED) { // case1 叔叔节点是红色; 叔叔和父亲加一层黑色,祖父层变黑(黑色上移)
 80                     z->p->color = BLACK;
 81                     uncle->color = BLACK;
 82                     z->p->p->color = RED;
 83                     z = z->p->p;
 84                 }
 85                 else {
 86                     if (z->p->right == z) { // case2 叔叔是黑色, 祖孙三代不在一条直线, 调整到case3 
 87                         z = z->p;
 88                         left_rotate(z);
 89                     }
 90                     z->p->color = BLACK;  // case3 调整过后,冲突解决
 91                     z->p->p->color = RED;
 92                     right_rotate(z->p->p);
 93                 }
 94             }
 95             else {
 96                 RBnode uncle = z->p->p->left;
 97                 if (uncle->color == RED) { // case1
 98                     z->p->color = BLACK;
 99                     uncle->color = BLACK;
100                     z->p->p->color = RED;
101                     z=z->p->p;
102                 }
103                 else {
104                     if (z->p->left == z) { // case 2
105                         z = z->p;
106                         right_rotate(z);
107                     }
108                     z->p->color = BLACK;  // case 3
109                     z->p->p->color = RED;
110                     left_rotate(z->p->p);
111                 }
112             }
113         }
114         rt->color = BLACK;
115     }
116 
117     // 旋转的性质: 左旋或右旋后,交换两节点的颜色不改变黑高(自我总结)
118     void left_rotate(RBnode x) {
119         RBnode y = x->right;
120         x->right = y->left;
121         if (y->left != nil)
122             y->left->p = x;
123         y->p = x->p;
124         if (x->p == nil)
125             rt = y;
126         else if (x->p->left == x)
127             x->p->left = y;
128         else
129             x->p->right = y;
130         y->left = x;
131         x->p = y;
132         if (x!=nil) x->up(); // 先调整x,再调整y
133         if (y!=nil) y->up();
134     }
135 
136     void right_rotate(RBnode x) {
137         RBnode y = x->left;
138         x->left = y->right;
139         y->p = x->p;
140         if (y->right != nil)
141             y->right->p = x;
142         if (x->p == nil)
143             rt = y;
144         else if (x->p->left == x)
145             x->p->left = y;
146         else
147             x->p->right = y;
148         y->right = x;
149         x->p = y;
150         if (x!=nil) x->up();
151         if (x!=nil) y->up();
152     }
153 
154     RBnode min_mum(RBnode x) {
155         while (x->left != nil)
156             x = x->left;
157         return x;
158     }
159 
160     RBnode max_mum(RBnode x) {
161         while (x->right != nil)
162             x = x->right;
163         return x;
164     }
165 
166     RBnode low_find(int k) { // 寻找比k小且最大的节点
167         return _low(k,rt);
168     }
169 
170     RBnode _low (int k, RBnode x) {
171         if (x==nil) return x;
172         if (k<=x->key) return _low(k,x->left);
173         else {
174             RBnode ans=_low(k,x->right);
175             if (ans!=nil) return ans;
176             else          return x;
177         }
178     }
179 
180     RBnode upp_find(T k) { // 寻找比k大且最小的节点
181         return _upp(k,rt);
182     }
183 
184     RBnode _upp (T k, RBnode x) {
185         if (x==nil) return x;
186         if (k>=x->key) return _upp(k,x->right);
187         else {
188             RBnode ans=_upp(k,x->left);
189             if (ans!=nil) return ans;
190             else          return x;
191         }
192     }
193 
194     RBnode rfind(T key) {  // 相等元素的最后一个节点
195         RBnode x = rt;
196         while (x != nil) {
197             if (key<x->key)
198                 x = x->left;
199             else if (key>x->key)
200                 x = x->right;
201             else
202                 return x;
203         }
204         return x;
205     }
206 
207     RBnode find(T key) {  // 相等元素第一个节点
208         return my_find(key, rt);
209     }
210 
211     RBnode my_find(T key, RBnode x) {
212         if (x == nil) return nil;
213         if (key<x->key) return my_find(key, x->left);
214         if (key == x->key) {
215             RBnode ans = my_find(key, x->left);
216             if (ans == nil) return x;
217             else          return ans;
218         }
219         return my_find(key, x->right);
220     }
221 
222     RBnode find_kth(int k) {  // 排名第k的元素, 相等的元素具有不同的排名
223         RBnode x = rt;
224         if (rt->sum<k) return nil;
225         while (k != x->left->sum + 1) {
226             if (k <= x->left->sum)
227                 x = x->left;
228             else {
229                 k -= x->left->sum + 1;
230                 x = x->right;
231             }
232         }
233         return x;
234     }
235 
236     int get_rank(RBnode x) { // 寻找节点x的排名
237         RBnode t=rt; int k=0;
238         while (t!=x) {
239             if (x->key<=t->key)
240                 t=t->left;
241             else  {
242                 k+=t->left->sum+1;
243                 t=t->right;                
244             }
245         }
246         return k+t->left->sum+1;
247     }
248 
249     void transplate(RBnode y, RBnode x) {  // 以节点x代替y,但不对y的子节点经行替换
250         if (y->p == nil)
251             rt = x;
252         else if (y->p->left == y)
253             y->p->left = x;
254         else
255             y->p->right = x;
256         x->p = y->p;
257     }
258 
259     void remove(RBnode z) {  // y: 要删除的节点  x: 代替的节点
260         RBnode y = z;
261         RBnode x;
262         int ycolor = y->color;
263         if (y->left == nil) {
264             x = y->right;
265             transplate(y, x);
266         }
267         else if (y->right == nil) {
268             x = y->left;
269             transplate(y, x);
270         }
271         else {
272             y = min_mum(y->right);
273             ycolor = y->color;
274             x = y->right;
275             if (y->p == z)
276                 x->p = y;  // x可能是nil节点,因此需要记录其父亲
277             else {
278                 transplate(y, x);
279                 y->right = z->right;
280                 z->right->p = y;
281             }
282             transplate(z,y);
283             y->left = z->left;
284             z->left->p = y;
285             y->color = z->color; // y代替z,但颜色不改变!!!!!!
286             y = z;  // y指向废弃节点
287         }
288         if (ycolor == BLACK)
289             remove_fixup(x);
290         RBnode t=x->p; // 最后调整sum
291         while (t!=nil) { 
292             t->up();
293             t=t->p;
294         }
295         delete y;
296     }
297 
298     // 可能有冲突:
299     // 1)经过x的路径,黑高减1
300     // 2)x的为红色,x的parent也是红
301     // 3)x为根节点,颜色为红色
302     void remove_fixup(RBnode x) { // 看兄弟节点 // 减少x多的一重黑色
303         while (x != rt&&x->color == BLACK) {
304             if (x == x->p->left) {
305                 RBnode bro = x->p->right;
306                 if (bro->color == RED) { // case1 兄弟节点为红色,转化为情况234 
307                     bro->color = BLACK;
308                     bro->p->color = RED;
309                     left_rotate(x->p);
310                     bro = x->p->right;
311                 }
312                 if (bro->left->color == BLACK&&bro->right->color == BLACK) { // case2 兄弟节点及其儿子节点都为黑色
313                     bro->color = RED;
314                     x = x->p;
315                 }
316                 else {
317                     if (bro->right->color == BLACK) { // case3 兄弟右节点不为红色
318                         bro->color = RED;
319                         bro->left->color = BLACK;
320                         right_rotate(bro);
321                         bro = x->p->right;
322                     }
323                     bro->right->color = BLACK; //case4   兄弟右孩子节点为红色,调整之后结束循环
324                     bro->color = bro->p->color;
325                     bro->p->color = BLACK;
326                     left_rotate(x->p);
327                     x = rt; // 终止递归
328                 }
329             }
330             else {
331                 RBnode bro = x->p->left;
332                 if (bro->color == RED) { // case 1
333                     bro->color = BLACK;
334                     bro->p->color = RED;
335                     right_rotate(x->p);
336                     bro = x->p->left;
337                 }
338                 if (bro->left->color == BLACK&&bro->right->color == BLACK) { // case 2
339                     bro->color = RED;
340                     x = x->p;
341                 }
342                 else {
343                     if (bro->left->color == BLACK) { // case 3
344                         bro->color = RED;
345                         bro->right->color = BLACK;
346                         left_rotate(bro);
347                         bro = x->p->left;
348                     }
349                     bro->left->color = BLACK; // case 4
350                     bro->color = bro->p->color;
351                     bro->p->color = BLACK;
352                     right_rotate(x->p);
353                     x = rt;
354                 }
355             }
356         }
357         x->color = BLACK;
358     }
359 
360      RBnode successor(RBnode x) { // 后继节点
361         if (x->right != nil)
362             return min_mum(x->right);
363         RBnode y = x->p;
364         while (y != nil && y->right == x) {
365             x = y;
366             y = y->p;
367         }
368         return y;
369     }
370 
371     RBnode predecessor(RBnode x) { // 前继
372         if (x->left != nil)
373             return max_mum(x->left);
374         RBnode y = x->p;
375         while (y != nil && y->left == x) {
376             x = y;
377             y = y->p;
378         }
379         return y;
380     }
381 
382 };
383 
384 int main()
385 {
386 
387     RBtree<int> tree;
388     int n;  scanf("%d",&n);
389     while (n--) {
390         int op,x; scanf("%d %d",&op,&x);
391         if (op==1) tree.insert(x);
392         else if(op==2)  {
393             node<int>* nd=tree.rfind(x);
394             tree.remove(nd);
395         }
396         else if(op==3) {
397             node<int>* nd=tree.find(x);
398             printf("%d
",tree.get_rank(nd));
399         }
400         else if (op==4)  printf("%d
",tree.find_kth(x)->key);
401         else if (op==5)  printf("%d
",tree.low_find(x)->key);
402         else             printf("%d
",tree.upp_find(x)->key);
403     }
404     return 0;
405 }