Dev►DS

一种无递归、无栈、无parent指针的红黑树实现

前言

红黑树是一种复杂的平衡树，在大部分情况下都会使用父指针或者递归实现。假如我们一定要三无实现呢？

本文必须配合OI-Wiki食用！！

基础结构

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
#define BLK_COLOR 0
#define RED_COLOR 1
#define LEFT 0
#define RIGHT 1
#define Color(node) (node==NULL?BLK_COLOR:node->color)
#define Dir(par,node) (par->left==node?LEFT:RIGHT)

struct RBTNode
{
    int data;
    RBTNode *left;
    RBTNode *right;
    int color;

    RBTNode(int data):data(data),left(NULL),right(NULL),color(RED_COLOR){}
};

RBTNode* tree;

//directly insert son under father
void directInsert(RBTNode* fa, RBTNode* son){
    if(fa->data<son->data){
        fa->right=son;
    }else{
        fa->left=son;
    }
}

RBTNode* rotateLeft(RBTNode* root){
    auto r=root->right;
    auto rl=r==NULL?NULL:root->right->left;
    root->right=rl;
    r->left=root;
    return r;
}

RBTNode* rotateRight(RBTNode* root){
    auto l=root->left;
    auto lr=l==NULL?NULL:root->left->right;
    root->left=lr;
    l->right=root;
    return l;
}

插入

插入共有6种情况，其中只有Case 4会将祖父设为红色，从而导致需要递归向上继续维护，其他情况的祖父都是黑色，不需要向上传递。

所以，我们不妨直接从上往下考虑，沿着插入新节点的路径一路向下，如果遇到了黑色节点下面两个儿子都是红色的，我们无论怎样都下放黑色。这个时候如果当前节点的父亲也是红色的，我们不妨视作“插入”了当前节点，进行局部维护即可。我们不难发现，这样维护不再需要上传，因为我们已经下放了上方的所有Case 4的父节点的颜色，我们已经不会出现Case 4.

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void insert(int x){
	for(x路径上从上往下的每个节点){
		if(我黑色，两个儿子红色){
			儿子=黑色
			我=红色
			if(爸爸是红色){
				rebalance(我)
			}
		}
	}
	
	directInsert(x)
	rebalance(新节点)
		
	if(根节点是红色){
		根节点=黑色
	}
}

真代码：

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
void insert(int x){
    auto node=new RBTNode(x);

    if(tree==NULL){
        tree=node;
        tree->color=BLK_COLOR;
        return;
    }

    RBTNode* now=tree;
    RBTNode* par=NULL;
    RBTNode* gpar=NULL;
    RBTNode* ggpar=NULL;

    while(true){

        //if can be push down then just push down
        if(now->color==BLK_COLOR && Color(now->left)==RED_COLOR && Color(now->right)==RED_COLOR){
            now->color=RED_COLOR;
            now->left->color=BLK_COLOR;
            now->right->color=BLK_COLOR;

            if(par==NULL){ //tree root
                now->color=BLK_COLOR;
            }else{ //rebalance
                if(par->color==RED_COLOR){
                    rebalance(ggpar,gpar,par,now);
                }
            }
        }

        if(now->data==x){
            //already in tree
            delete node;
            return;
        }
        if(now->data<x){
            //move to the right
            if(now->right==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->right;
        }else{
            //move to the left
            if(now->left==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    directInsert(now,node);

    if(now->color==RED_COLOR){
        rebalance(gpar,par,now,node);
    }

    //ensure root node is black
    if(tree->color==RED_COLOR){
        tree->color=BLK_COLOR;
    }
}

rebalance的情况请看OI-Wiki，下面只给出实现（注意细节！）：

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
//Assume me is red, par is red
void rebalance(RBTNode* ggpar, RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(gpar==NULL){
        //par is root
        par->color=BLK_COLOR;
        return;
    }

    if(Dir(gpar,par)==LEFT){
        if(Dir(par,me)==RIGHT){
            gpar->left=rotateLeft(par);
            swap(par,me); //after rotation switched place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateRight(gpar);
            }else{
                ggpar->right=rotateRight(gpar);
            }
        }else{
            tree=rotateRight(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }else{
        if(Dir(par,me)==LEFT){
            gpar->right=rotateRight(par);
            swap(par,me); //after rotation swapped place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateLeft(gpar);
            }else{
                ggpar->right=rotateLeft(gpar);
            }
        }else{
            tree=rotateLeft(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }
}

删除

根据OI-Wiki，删除有3（+1）种情况，其中只有一种情况会导致rebalance：那就是删除的点是 黑色叶子 。其根本原因是： 黑高度的改变。只有黑高度改变了，才会上传。

所以删除的核心是判断一棵子树什么时候黑高度会改变！注意到，rebalance的5种情况中，只有Case3黑高度会改变。所以，如果$h(rt)$表示以rt为根的子树黑高度会不会改变，假设我们要删除的节点在左子树种，那么根据Case 3，我们有：

h(rt)= h(L) && (rt.color==Black) && (R.color==Black) && (RL.color==Black) && (RR.color==Black)

其中R为右节点、RL为右节点的左儿子、RR为右节点的右儿子。

所以我们只需要维护最后一个不满足(rt.color==Black) && (R.color==Black) && (RL.color==Black) && (RR.color==Black)的节点，这个节点下面的每个节点黑高度都会改变，都需要rebalance。我们自上而下的rebalance:

伪代码：

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
void remove(int x){
	先找到结构上要删除的节点toDelete
		
	for(toDelete路径上每一个节点){
		if(toDelete在左子树中){
			if(我是黑色、右儿子是黑色、右儿子的儿子都是黑色){
				//啥也不做
			}else{
				firstNoShorter=我
			}
		}else{
			//x在右子树中
			对称大法
		}
	}
	
	if(toDelete是红叶子){
		直接删除;
		return;
	}
	if(toDelete有儿子){
		把儿子挂到toDelete父亲上;
		儿子=黑色;
		return;
	}
	if(toDelete是树中唯一节点){
		tree=NULL;
		return;
	}
	for(firstNoShorter到toDelete路径上的点，但是不含firstNoShorter){
		reblanceRemoval(我)
	}
}

真代码：

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

void remove(int x){
    RBTNode* now=tree;
    RBTNode* par=NULL;

    RBTNode* nodeX=NULL; //the node containing X
    RBTNode* toDelete=NULL; //really gonna delete this
    RBTNode* toDelPar=NULL;

    RBTNode* parFirstNoShorter=NULL; //parent of first of no shorter
    RBTNode* firstNoShorter=NULL;

    //find node of value x
    while(now!=NULL){
        if(now->data==x){
            //found!
            nodeX=now;
            break;
        }
        if(now->data<x){
            //move to the right
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }else{
            //move to the left

            if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->left;
        }
    }

    if(nodeX==NULL){
        //did not find node
        return;
    }

    //find scapegoat
    if(nodeX->left==NULL){
        toDelPar=par;
        toDelete=nodeX;
    }else{
        if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
            parFirstNoShorter=par;
            firstNoShorter=now;
        }
        par=nodeX;
        now=nodeX->left;
        while(now->right!=NULL){
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }
        toDelPar=par;
        toDelete=now;
    }

    //case 1 it's a leaf red
    if(toDelete->left==NULL && toDelete->right==NULL && toDelete->color==RED_COLOR){
        if(toDelete==par->left){
            par->left=NULL;
        }else{
            par->right=NULL;
        }
        nodeX->data=toDelete->data;
        delete toDelete;
        return;
    }

    //case 2 it has a child (must be red)
    if(toDelete->left!=NULL){
        toDelete->left->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->left;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->left;
            }else{
                par->right=toDelete->left;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }
    if(toDelete->right!=NULL){
        toDelete->right->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->right;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->right;
            }else{
                par->right=toDelete->right;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }

    //tree gone
    if(toDelPar==NULL){
        tree=NULL;
        delete toDelete;
        return;
    }

    //balance
    RBTNode* gpar=parFirstNoShorter;
    par=firstNoShorter;
    if(firstNoShorter==NULL){
        now=tree;
    }else{
        if(firstNoShorter->data<toDelete->data){
            now=firstNoShorter->right;
        }else{
            now=firstNoShorter->left;
        }
    }

    while(now!=NULL){
        rebalanceRemoval(gpar,par,now);
        if(now->data<toDelete->data){
            gpar=par;
            par=now;
            now=now->right;
        }else{
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    nodeX->data=toDelete->data;
    if(toDelete==toDelPar->left){
        toDelPar->left=NULL;
    }else{
        toDelPar->right=NULL;
    }
    delete toDelete;
}

我们按照OI-wiki上的5种情况做balance（注意大量细节）：

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
void rebalanceRemoval(RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(par==NULL){
        return;
    }
    if(me==par->left){
        auto sib=par->right;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateLeft(par);
                }else{
                    gpar->right=rotateLeft(par);
                }
            }else{
                tree=rotateLeft(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->right;
            //resolve now, par in the next case:
        }
        
        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->right)==BLK_COLOR){
            //need to fucking rotate
            par->right=rotateRight(sib);
            par->right->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->right;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateLeft(par);
            }else{
                gpar->right=rotateLeft(par);
            }
        }else{
            tree=rotateLeft(par);
        }

        swap(sib->color,par->color);
        sib->right->color=BLK_COLOR;
    }else{ //i am the right side child
        auto sib=par->left;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateRight(par);
                }else{
                    gpar->right=rotateRight(par);
                }
            }else{
                tree=rotateRight(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->left;

            //resolve now, par in the next case:
        }
        
        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->left)==BLK_COLOR){
            //need to fucking rotate
            par->left=rotateLeft(sib);
            par->left->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->left;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateRight(par);
            }else{
                gpar->right=rotateRight(par);
            }
        }else{
            tree=rotateRight(par);
        }

        swap(sib->color,par->color);
        sib->left->color=BLK_COLOR;
    }
}

总结

其实RB-tree的实现更多的是细节和分析case（细节卡了半天啊啊啊啊啊），非递归化本身难度并不高，特别是已经弄清楚AVL的分析情况下。

完整代码

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
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define qi ios::sync_with_stdio(0)

bool debug = true;

/*    *************************************
      * Written in Acer computer          *
      * The following code belongs to     *
      *    XGN from HellHoleStudios       *
      *************************************

    Current Problem Is:
*/
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> ptt)
{
    os << ptt.first << "," << ptt.second;
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> vt)
{
    os << "{";
    for (int i = 0; i < vt.size(); i++)
    {
        os << vt[i] << " ";
    }
    os << "}";
    return os;
}

#define BLK_COLOR 0
#define RED_COLOR 1
#define LEFT 0
#define RIGHT 1
#define Color(node) (node==NULL?BLK_COLOR:node->color)
#define Dir(par,node) (par->left==node?LEFT:RIGHT)

struct RBTNode
{
    int data;
    RBTNode *left;
    RBTNode *right;
    int color;

    RBTNode(int data):data(data),left(NULL),right(NULL),color(RED_COLOR){}
};

RBTNode* tree;

void directInsert(RBTNode* fa, RBTNode* son){
    if(fa->data<son->data){
        fa->right=son;
    }else{
        fa->left=son;
    }
}

RBTNode* rotateLeft(RBTNode* root){
    auto r=root->right;
    auto rl=r==NULL?NULL:root->right->left;
    root->right=rl;
    r->left=root;
    return r;
}

RBTNode* rotateRight(RBTNode* root){
    auto l=root->left;
    auto lr=l==NULL?NULL:root->left->right;
    root->left=lr;
    l->right=root;
    return l;
}

//Assume me is red, par is red
void rebalance(RBTNode* ggpar, RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(gpar==NULL){
        //par is root
        par->color=BLK_COLOR;
        return;
    }

    if(Dir(gpar,par)==LEFT){
        if(Dir(par,me)==RIGHT){
            gpar->left=rotateLeft(par);
            swap(par,me); //after rotation switched place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateRight(gpar);
            }else{
                ggpar->right=rotateRight(gpar);
            }
        }else{
            tree=rotateRight(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }else{
        if(Dir(par,me)==LEFT){
            gpar->right=rotateRight(par);
            swap(par,me); //after rotation swapped place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateLeft(gpar);
            }else{
                ggpar->right=rotateLeft(gpar);
            }
        }else{
            tree=rotateLeft(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }
}

void insert(int x){
    auto node=new RBTNode(x);

    if(tree==NULL){
        tree=node;
        tree->color=BLK_COLOR;
        return;
    }

    RBTNode* now=tree;
    RBTNode* par=NULL;
    RBTNode* gpar=NULL;
    RBTNode* ggpar=NULL;

    while(true){

        //if can be push down then just push down
        if(now->color==BLK_COLOR && Color(now->left)==RED_COLOR && Color(now->right)==RED_COLOR){
            now->color=RED_COLOR;
            now->left->color=BLK_COLOR;
            now->right->color=BLK_COLOR;

            if(par==NULL){ //tree root
                now->color=BLK_COLOR;
            }else{ //rebalance
                if(par->color==RED_COLOR){
                    rebalance(ggpar,gpar,par,now);
                }
            }
        }

        if(now->data==x){
            //already in tree
            delete node;
            return;
        }
        if(now->data<x){
            //move to the right
            if(now->right==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->right;
        }else{
            //move to the left
            if(now->left==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    directInsert(now,node);

    if(now->color==RED_COLOR){
        rebalance(gpar,par,now,node);
    }

    //ensure root node is black
    if(tree->color==RED_COLOR){
        tree->color=BLK_COLOR;
    }
}

//assume me is black
void rebalanceRemoval(RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(par==NULL){
        return;
    }
    if(me==par->left){
        auto sib=par->right;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateLeft(par);
                }else{
                    gpar->right=rotateLeft(par);
                }
            }else{
                tree=rotateLeft(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->right;
            //resolve now, par in the next case:
        }
        
        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->right)==BLK_COLOR){
            //need to fucking rotate
            par->right=rotateRight(sib);
            par->right->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->right;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateLeft(par);
            }else{
                gpar->right=rotateLeft(par);
            }
        }else{
            tree=rotateLeft(par);
        }

        swap(sib->color,par->color);
        sib->right->color=BLK_COLOR;
    }else{
        auto sib=par->left;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateRight(par);
                }else{
                    gpar->right=rotateRight(par);
                }
            }else{
                tree=rotateRight(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->left;

            //resolve now, par in the next case:
        }
        
        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->left)==BLK_COLOR){
            //need to fucking rotate
            par->left=rotateLeft(sib);
            par->left->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->left;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateRight(par);
            }else{
                gpar->right=rotateRight(par);
            }
        }else{
            tree=rotateRight(par);
        }

        swap(sib->color,par->color);
        sib->left->color=BLK_COLOR;
    }
}

void remove(int x){
    RBTNode* now=tree;
    RBTNode* par=NULL;

    RBTNode* nodeX=NULL; //the node containing X
    RBTNode* toDelete=NULL; //really gonna delete this
    RBTNode* toDelPar=NULL;

    RBTNode* parFirstNoShorter=NULL; //parent of first of no shorter
    RBTNode* firstNoShorter=NULL;

    //find node of value x
    while(now!=NULL){
        if(now->data==x){
            //found!
            nodeX=now;
            break;
        }
        if(now->data<x){
            //move to the right
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }else{
            //move to the left

            if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->left;
        }
    }

    if(nodeX==NULL){
        //did not find node
        return;
    }

    //find scapegoat
    if(nodeX->left==NULL){
        toDelPar=par;
        toDelete=nodeX;
    }else{
        if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
            parFirstNoShorter=par;
            firstNoShorter=now;
        }
        par=nodeX;
        now=nodeX->left;
        while(now->right!=NULL){
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }
        toDelPar=par;
        toDelete=now;
    }

    //case 1 it's a leaf red
    if(toDelete->left==NULL && toDelete->right==NULL && toDelete->color==RED_COLOR){
        if(toDelete==par->left){
            par->left=NULL;
        }else{
            par->right=NULL;
        }
        nodeX->data=toDelete->data;
        delete toDelete;
        return;
    }

    //case 2 it has a child (must be red)
    if(toDelete->left!=NULL){
        toDelete->left->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->left;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->left;
            }else{
                par->right=toDelete->left;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }
    if(toDelete->right!=NULL){
        toDelete->right->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->right;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->right;
            }else{
                par->right=toDelete->right;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }

    //tree gone
    if(toDelPar==NULL){
        tree=NULL;
        delete toDelete;
        return;
    }

    //balance
    RBTNode* gpar=parFirstNoShorter;
    par=firstNoShorter;
    if(firstNoShorter==NULL){
        now=tree;
    }else{
        if(firstNoShorter->data<toDelete->data){
            now=firstNoShorter->right;
        }else{
            now=firstNoShorter->left;
        }
    }

    while(now!=NULL){
        rebalanceRemoval(gpar,par,now);
        if(now->data<toDelete->data){
            gpar=par;
            par=now;
            now=now->right;
        }else{
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    nodeX->data=toDelete->data;
    if(toDelete==toDelPar->left){
        toDelPar->left=NULL;
    }else{
        toDelPar->right=NULL;
    }
    delete toDelete;
}

bool checkColorConstraint(RBTNode *node)
{
    if (node == nullptr)
        return true;
    bool leftOK = checkColorConstraint(node->left);
    bool rightOK = checkColorConstraint(node->right);
    if (!leftOK || !rightOK)
        return false;
    if (node->color == BLK_COLOR)
        return true;
    else if (node->color == RED_COLOR)
    {
        if (node->left != nullptr && node->left->color == RED_COLOR)
        {
            cout << "COLOR problem: " << node->data << " left " << node->left->data;
            return false;
        }
        if (node->right != nullptr && node->right->color == RED_COLOR)
        {
            cout << "COLOR problem: " << node->data << " right " << node->right->data;
            return false;
        }
        return true;
    }
    else
        assert(0); // 颜色只能是red,black

    return true;
}

// 这个函数检查黑高度约束是否满足
int checkBlackHeightConstraint(RBTNode *node)
{
    if (node == 0)
        return 1;

    int lH = checkBlackHeightConstraint(node->left);
    int rH = checkBlackHeightConstraint(node->right);
    if (lH != rH || lH < 0)
    {
        cout << "BLACK HEIGHT problem: " << node->data << " left " << lH << " right " << rH << endl;
        return -1;
    }
    return lH + (node->color == BLK_COLOR ? 1 : 0);
}

bool CheckOrder(RBTNode *node, RBTNode *prevNode)
{
    if (node == nullptr)
        return true;

    if (prevNode != nullptr && prevNode->data >= node->data)
    {
        return false;
    }
    if (!CheckOrder(node->left, prevNode))
        return false;
    return CheckOrder(node->right, node);
}

bool checkRedBlackTree(RBTNode *rt)
{
    if (!checkColorConstraint(rt))
    {
        cout << "Color Constraint violated" << endl;
        return false;
    }

    if (checkBlackHeightConstraint(rt) < 0)
    {
        cout << "Black Height Constraint violated!" << endl;
        return false;
    }
    if (!CheckOrder(rt, nullptr))
    {
        cout << "Not a binary search tree";
        return false;
    }
    if (rt != nullptr && rt->color != BLK_COLOR)
    {
        cout << "The root is not black!" << endl;
        return false;
    }
    return true;
}

// 通过中序遍历，从小到大输出树中Key集合的代码
void midOrderPrint(RBTNode *rt)
{
    if (rt == nullptr)
        return;

    midOrderPrint(rt->left);
    cout << rt->data << " ";
    midOrderPrint(rt->right);
}

int main(int argc, char *argv[])
{
    freopen("in.txt","r",stdin);

    int n;
    // n=1000;
    cin>>n;
    for(int i=0;i<n;i++){
        int op,data;
        // op=rand()%2+1;
        // data=rand();
        // cout<<op<<" "<<data<<endl;
        cin>>op>>data;
        if(op==1){
            insert(data);
        }else{
            remove(data);
        }

        midOrderPrint(tree);
        cout<<endl;

        bool ok=checkRedBlackTree(tree);
        assert(ok);
        cout<<"OK"<<endl;
    }
    return 0;
}