Dev►DS

一种基于维护高度的无递归、无栈、无parent指针的AVL树实现方式

引入

AVL树有种种实现方式，其中最自然的是采用递归的写法，毕竟AVL树是递归定义的。但是，有的老师认为“递归时间常数大”，觉得应该用迭代。但是，还有老师认为迭代要用栈，“栈空间大（指占用了 ）空间”，不能用栈。自然，我们可以用parent指针规避掉这一问题，但是显然parent指针需要使用的额外内存更大，这位老师还是不喜欢。所以现在我们被要求实现三无AVL——无递归、无栈、无parent指针。

AVL树的维护方法有两种：维护高度和balance factor（BF）。笔者认为Balance Factor不够优雅、泛用性低、过于特殊化，故采用维护高度的方式。

所以，本文认为，三无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
struct AVL{
    AVL* left;
    AVL* right;
    int value;
    int height;

    void print();
};

int Height(AVL* node){
    return node==NULL? 0 : node->height;
}

void AVL::print(){
    cout<<"(";
    if(left!=NULL){
        left->print();
    }
    cout<<value<<","<<Height(right)-Height(left); //get balance factor
    if(right!=NULL){
        right->print();
    }
    cout<<")";
}

void UpdateHeight(AVL* node){
    node->height=max(Height(node->left),Height(node->right))+1;
}

旋转

AVL消除失衡的方式主要靠旋转，主要有左旋、右旋、double左旋、double右旋四种，具体的旋转方法请参考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
//returns new root
AVL* RotateLeft(AVL* root){
    AVL* r=root->right;
    AVL* rl=root->right->left;
    root->right=rl;
    r->left=root;

    UpdateHeight(root);
    UpdateHeight(r);
    return r;
}

//returns new root
AVL* RotateRight(AVL* root){
    AVL* l=root->left;
    AVL* lr=root->left->right;
    l->right=root;
    root->left=lr;

    UpdateHeight(root);
    UpdateHeight(l);
    return l;
}

相比维护BF，维护height更容易维护旋转后的高度，不用动脑无脑update就好了，多好啊！

在维护高度下，使用左右旋的条件是（伪代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if(Height(now->left)==Height(now->right)+2){
	if(Height(now->left->left)>=Height(now->left->right)){
		RotateRight(now);
	}else{
		RotateLeft(now->left);
		RotateRight(now);
	}
}else if(Height(now->right)==Height(now->left)+2){
	if(Height(now->right->right)>=Height(now->right->left)){
		RotateLeft(now);
	}else{
		RotateRight(now->right);
		RotateLeft(now);
	}
}

经过上述一轮旋转后，我们可以保证-1<=Height(l)-Height(r)<=1（证明略），即满足AVL树的条件。

插入

注意到，插入一个节点时，只有插入的节点路径上的height可能会变化。而且如果变化，一定是增加1。那么我们只要考虑某个子树插入（并有可能失衡进行旋转后）高度会不会变即可。考虑以root为根的子树，假如插入的节点位于root的左子树（右子树可以对称大法），那么考虑下面几种情况：

  1. 左子树增加了一个节点后没有长高，由Height(root)=max(Height(l),Height(r))+1知高度不变。
  2. 左子树原来比右子树高，且左子树变高了，此时一定会失衡旋转，由旋转的性质知，高度不变（也是AVL平衡的基本原理）。
  3. 左子树比右子树矮，左子树变高了，由max知高度不变。
  4. 左子树和右子树一样高，左子树变高了，高度+1.

综上，如果higher(root)表示root为根的子树有没有变高，那么就有higher(root)=Height(l)==Height(r) && higher(l)。

这个递归可以轻松的转换成循环，理解其含义其实是从根到新加入的节点的路径上最后一个Height(l)!=Height(r)的地方开始高度+1.（特别的，如果不存在这样的地方，那么整棵树高度++）：

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
AVL* blocker=NULL;

//find insert location
AVL* now=tree;
AVL* parent=NULL;
while(now!=NULL){
	if(Height(now->left)!=Height(now->right)){
		blocker=now;
	}
	if(data==now->value){
		delete newNode;
		return; //duplicate value in tree
	}else if(data<now->value){
		parent=now;
		now=now->left;
	}else if(data>now->value){
		parent=now;
		now=now->right;
	}
}

if(data>parent->value){
	parent->right=newNode;
}else{
	parent->left=newNode;
}

//update height from blocker
now=blocker==NULL?tree:blocker;
while(now!=NULL){
	if(data<now->value){
		now=now->left;
	}else if(data>now->value){
		now=now->right;
	}else{
		break;
	}
	if(now!=NULL){
		now->height++;
	}
}
if(blocker==NULL){
	//make sure total tree height is increased
	tree->height++;
}

例如，按顺序插入3 2 1。插入2后：

1
2
3
  3(H=2)
 /
2(H=1)

此时插入1，blocker=3，我们只会更新节点1和2的高度：

1
2
3
4
5
    3(H=2)
   /
  2(H=2)
 /
1(H=1)

你会说，哎，不对啊？3的高度怎么错了，为什么不是3？对，我们上述算法所求的高度是假设已经旋转并平衡后的高度，现在我们树的结构还没有更新，所以高度看上去不对。对上面的树进行右旋1次，我们就会有：

1
2
3
   2(H=2)
 /  \
1(H1)3(H1)

这样树的高度就被正确反映出来了。

那么，算出了“真实”的高度后，我们怎么平衡呢？简单，只要沿着从根到新加节点的路径逐个查找左儿子真实高度和右儿子真实高度差距为2的点进行旋转就好了，让高度正确反映旋转后的状态。

要注意很多corner case，下面是平衡全部算法：

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
void balance(int data){
    AVL* now=tree;
    AVL* parent=NULL;
    while(now!=NULL){

        if(Height(now->left)==Height(now->right)+2){
            if(Height(now->left->left)>=Height(now->left->right)){
                if(parent==NULL){
                    tree=RotateRight(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateRight(now);
                    }else{
                        parent->right=RotateRight(now);
                    }
                }
            }else{
                now->left=RotateLeft(now->left);
                if(parent==NULL){
                    tree=RotateRight(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateRight(now);
                    }else{
                        parent->right=RotateRight(now);
                    }
                }
            }
        }else if(Height(now->right)==Height(now->left)+2){
            if(Height(now->right->right)>=Height(now->right->left)){
                if(parent==NULL){
                    tree=RotateLeft(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateLeft(now);
                    }else{
                        parent->right=RotateLeft(now);
                    }
                }
            }else{
                now->right=RotateRight(now->right);
                if(parent==NULL){
                    tree=RotateLeft(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateLeft(now);
                    }else{
                        parent->right=RotateLeft(now);
                    }
                }
            }
        }

        if(now->value==data){
            break;
        }else if(data<now->value){
            parent=now;
            now=now->left;
        }else{
            parent=now;
            now=now->right;
        }
    }
}

所以插入的过程就是：

  • 找到插入位置，并插入节点
  • 找到最后一个Height(l)!=Height(r)的节点，更新他子树下的高度
  • 调准树的结构使其平衡

代码：

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
void Insert(int data){
    AVL* newNode=new AVL();
    newNode->height=0;
    newNode->value=data;

    if(tree==NULL){
        newNode->height=1;
        tree=newNode;
        return;
    }

    AVL* blocker=NULL;
    
    //find insert location
    AVL* now=tree;
    AVL* parent=NULL;
    while(now!=NULL){
        if(Height(now->left)!=Height(now->right)){
            blocker=now;
        }
        if(data==now->value){
            delete newNode;
            return; //duplicate value in tree
        }else if(data<now->value){
            parent=now;
            now=now->left;
        }else if(data>now->value){
            parent=now;
            now=now->right;
        }
    }

    if(data>parent->value){
        parent->right=newNode;
    }else{
        parent->left=newNode;
    }

    //update height from blocker
    now=blocker==NULL?tree:blocker;
    while(now!=NULL){
        if(data<now->value){
            now=now->left;
        }else if(data>now->value){
            now=now->right;
        }else{
            break;
        }
        if(now!=NULL){
            now->height++;
        }
    }
    if(blocker==NULL){
        //make sure total tree height is increased
        tree->height++;
    }

    balance(data);
}

删除

AVL（BST）删除时，我们一定会先找到被删除节点的前驱（左子树最大值）或者后继（右子树最小值），用这个节点的值替换被删除节点原本的值，并形式上删除这个“替罪羊”节点，来保证BST的结构。本文采用删除前驱的方式。首先，我们就要找到形式上被删除的节点和要删除的节点：

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
AVL* now=tree;
AVL* parent=NULL;
AVL* thisNode=NULL;
AVL* toDelNode=NULL;
AVL* toDelPar=NULL;
//looking for the node holding value 'data'
while(now!=NULL){
	if(now->value==data){
		thisNode=now;
		break;
	}else if(data<now->value){
		parent=now;
		now=now->left;
	}else{
		parent=now;
		now=now->right;
	}
}

if(thisNode==NULL){
	//not present in tree
	return;
}

if(thisNode->left==NULL){
	toDelPar=parent;
	toDelNode=thisNode;
}else{
	parent=thisNode;
	now=thisNode->left;
	while(now->right!=NULL){
		parent=now;
		now=now->right;
	}
	toDelPar=parent;
	toDelNode=now;
}

接下来，和插入一样，我们注意到子树高度的改变一定发生在从根到toDelNode（形式上删除的节点）的路径中，且高度如果改变，一定是减少1。那么，考虑根root子树，假设删除的是左子树中的节点，高度什么时候会减少呢？考虑下列情况：

  1. 删除后左子树高度没变，Height(root)不变。
  2. 左子树高度比右子树高，左子树高度减少，Height(root)减少。
  3. 左子树高度比右子树低，左子树高度减少，此时左子树高度比右子树低2，将会触发旋转。

    1. Height(rr)>=Height(rl)，其中rr为右子树的右儿子，rl为右子树的左儿子，此时触发左单旋：

图中高度条件：Height(L)=Height(R)-2,Height(RR)=Height(RL)+1或Height(RR)=Height(RL)。

原高度：Height(RR)+2，旋转后高度：max(Height(RR)+1,Height(RL)+2)，当且仅当Height(RR)>Height(RL)时高度变矮。

3.2. Height(rr)<Height(rl)，此时触发左双旋：

图中高度条件：Height(L)=Height(RL)-1,Height(RL)=Height(RR)+1

原高度：Height(RL)+2，现在高度：max(Height(L)+1,Height(RLL)+1,Height(RLR)+1,Height(RR)+1)，当且仅当Height(RLL)==Height(RLR)时高度变矮。

这一部分有点困难，希望你能自己在草稿纸上画张图搞清楚。

综上，shorter(root) = (Height(L)>Height(R) || Height(L)<Height(R) && (Height(RL)<Height(RR) || Height(RL)>Height(RR) && Height(RLL)==Height(RLR))) && shorter(L)

写成代码就是：

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
//find blocker
now=tree;
while(now!=NULL){
	if(toDelNode->value==now->value){
		break;
	}
	if(toDelNode->value<now->value){
		if(!(Height(now->left)>Height(now->right) ||
			 Height(now->left)<Height(now->right) && Height(now->right->left)<Height(now->right->right) ||
			 Height(now->left)<Height(now->right) && Height(now->right->left)>Height(now->right->right) && Height(now->right->left->left)==Height(now->right->left->right))){
			blocker=now;
		}
		now=now->left;
	}else{
		if(!(Height(now->right)>Height(now->left) || 
			 Height(now->right)<Height(now->left) && Height(now->left->right)<Height(now->left->left) ||
			 Height(now->right)<Height(now->left) && Height(now->left->right)>Height(now->left->left) && Height(now->left->right->left)==Height(now->left->right->right))){
			blocker=now;
		}
		now=now->right;
	}
}

//start from blocker decrease height by 1
now=blocker==NULL?tree:blocker;
while(now!=NULL){
	if(toDelNode->value==now->value){
		break;
	}else if(toDelNode->value<now->value){
		now=now->left;
	}else{
		now=now->right;
	}

	if(now!=NULL){
		now->height--;
	}
}
if(blocker==NULL){
	tree->height--;
}

当然，这一部分求出的高度也是 假设旋转、平衡后的高度，结构上还没更新。最后，我们在结构上删除并更新整棵树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//actually removing toDelNode
bool needToCopy=toDelNode!=thisNode;
int valueDeleted=toDelNode->value;
AVL* toDelSubtree=toDelNode->left!=NULL?toDelNode->left:toDelNode->right;

if(toDelPar==NULL){
	tree=toDelSubtree;
}else{
	if(toDelNode==toDelPar->left){
		toDelPar->left=toDelSubtree;
	}else{
		toDelPar->right=toDelSubtree;
	}
}

delete toDelNode;

balance(valueDeleted);

//copy value to the original node
if(needToCopy){
	thisNode->value=valueDeleted;
}

删除完整代码：

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
void Remove(int data){
    if(tree==NULL){
        return; //nothing to remove
    }

    AVL* now=tree;
    AVL* parent=NULL;
    AVL* thisNode=NULL;
    AVL* toDelNode=NULL;
    AVL* toDelPar=NULL;
    AVL* blocker=NULL;
    //looking for the node holding value 'data'
    while(now!=NULL){
        if(now->value==data){
            thisNode=now;
            break;
        }else if(data<now->value){
            parent=now;
            now=now->left;
        }else{
            parent=now;
            now=now->right;
        }
    }

    if(thisNode==NULL){
        //not present in tree
        return;
    }

    if(thisNode->left==NULL){
        toDelPar=parent;
        toDelNode=thisNode;
    }else{
        parent=thisNode;
        now=thisNode->left;
        while(now->right!=NULL){
            parent=now;
            now=now->right;
        }
        toDelPar=parent;
        toDelNode=now;
    }

    assert(toDelNode->left==NULL || toDelNode->right==NULL);

    //find blocker
    now=tree;
    while(now!=NULL){
        if(toDelNode->value==now->value){
            break;
        }
        if(toDelNode->value<now->value){
            if(!(Height(now->left)>Height(now->right) ||
            Height(now->left)<Height(now->right) && Height(now->right->left)<Height(now->right->right) ||
            Height(now->left)<Height(now->right) && Height(now->right->left)>Height(now->right->right) && Height(now->right->left->left)==Height(now->right->left->right))){
                blocker=now;
            }
            now=now->left;
        }else{
            if(!(Height(now->right)>Height(now->left) || 
            Height(now->right)<Height(now->left) && Height(now->left->right)<Height(now->left->left) ||
            Height(now->right)<Height(now->left) && Height(now->left->right)>Height(now->left->left) && Height(now->left->right->left)==Height(now->left->right->right))){
                blocker=now;
            }
            now=now->right;
        }
    }

    //start from blocker decrease height by 1
    now=blocker==NULL?tree:blocker;
    while(now!=NULL){
        if(toDelNode->value==now->value){
            break;
        }else if(toDelNode->value<now->value){
            now=now->left;
        }else{
            now=now->right;
        }

        if(now!=NULL){
            now->height--;
        }
    }
    if(blocker==NULL){
        tree->height--;
    }

    //actually removing toDelNode
    bool needToCopy=toDelNode!=thisNode;
    int valueDeleted=toDelNode->value;
    AVL* toDelSubtree=toDelNode->left!=NULL?toDelNode->left:toDelNode->right;

    if(toDelPar==NULL){
        tree=toDelSubtree;
    }else{
        if(toDelNode==toDelPar->left){
            toDelPar->left=toDelSubtree;
        }else{
            toDelPar->right=toDelSubtree;
        }
    }

    delete toDelNode;

    balance(valueDeleted);

    if(needToCopy){
        thisNode->value=valueDeleted;
    }
}

完整代码

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
#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;
}

struct AVL{
    AVL* left;
    AVL* right;
    int value;
    int height;

    void print();
};

int Height(AVL* node){
    return node==NULL? 0 : node->height;
}

void AVL::print(){
    cout<<"(";
    if(left!=NULL){
        left->print();
    }
    cout<<value<<","<<Height(right)-Height(left);
    if(right!=NULL){
        right->print();
    }
    cout<<")";
}

void UpdateHeight(AVL* node){
    node->height=max(Height(node->left),Height(node->right))+1;
}

//returns new root
AVL* RotateLeft(AVL* root){
    AVL* r=root->right;
    AVL* rl=root->right->left;
    root->right=rl;
    r->left=root;

    UpdateHeight(root);
    UpdateHeight(r);
    return r;
}

//returns new root
AVL* RotateRight(AVL* root){
    AVL* l=root->left;
    AVL* lr=root->left->right;
    l->right=root;
    root->left=lr;

    UpdateHeight(root);
    UpdateHeight(l);
    return l;
}

AVL* tree;

void balance(int data){
    AVL* now=tree;
    AVL* parent=NULL;
    while(now!=NULL){

        if(Height(now->left)==Height(now->right)+2){
            if(Height(now->left->left)>=Height(now->left->right)){
                if(parent==NULL){
                    tree=RotateRight(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateRight(now);
                    }else{
                        parent->right=RotateRight(now);
                    }
                }
            }else{
                now->left=RotateLeft(now->left);
                if(parent==NULL){
                    tree=RotateRight(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateRight(now);
                    }else{
                        parent->right=RotateRight(now);
                    }
                }
            }
        }else if(Height(now->right)==Height(now->left)+2){
            if(Height(now->right->right)>=Height(now->right->left)){
                if(parent==NULL){
                    tree=RotateLeft(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateLeft(now);
                    }else{
                        parent->right=RotateLeft(now);
                    }
                }
            }else{
                now->right=RotateRight(now->right);
                if(parent==NULL){
                    tree=RotateLeft(now);
                }else{
                    if(parent->left==now){
                        parent->left=RotateLeft(now);
                    }else{
                        parent->right=RotateLeft(now);
                    }
                }
            }
        }

        if(now->value==data){
            break;
        }else if(data<now->value){
            parent=now;
            now=now->left;
        }else{
            parent=now;
            now=now->right;
        }
    }
}

void Insert(int data){
    AVL* newNode=new AVL();
    newNode->height=0;
    newNode->value=data;

    if(tree==NULL){
        newNode->height=1;
        tree=newNode;
        return;
    }

    AVL* blocker=NULL;
    
    //find insert location
    AVL* now=tree;
    AVL* parent=NULL;
    while(now!=NULL){
        if(Height(now->left)!=Height(now->right)){
            blocker=now;
        }
        if(data==now->value){
            delete newNode;
            return; //duplicate value in tree
        }else if(data<now->value){
            parent=now;
            now=now->left;
        }else if(data>now->value){
            parent=now;
            now=now->right;
        }
    }

    if(data>parent->value){
        parent->right=newNode;
    }else{
        parent->left=newNode;
    }

    //update height from blocker
    now=blocker==NULL?tree:blocker;
    while(now!=NULL){
        if(data<now->value){
            now=now->left;
        }else if(data>now->value){
            now=now->right;
        }else{
            break;
        }
        if(now!=NULL){
            now->height++;
        }
    }
    if(blocker==NULL){
        //make sure total tree height is increased
        tree->height++;
    }

    balance(data);
}

void Remove(int data){

    // if(data==37){
    //     cout<<"Stop Here"<<endl;
    // }
    if(tree==NULL){
        return; //nothing to remove
    }

    AVL* now=tree;
    AVL* parent=NULL;
    AVL* thisNode=NULL;
    AVL* toDelNode=NULL;
    AVL* toDelPar=NULL;
    AVL* blocker=NULL;
    //looking for the node holding value 'data'
    while(now!=NULL){
        if(now->value==data){
            thisNode=now;
            break;
        }else if(data<now->value){
            parent=now;
            now=now->left;
        }else{
            parent=now;
            now=now->right;
        }
    }

    if(thisNode==NULL){
        //not present in tree
        return;
    }

    if(thisNode->left==NULL){
        toDelPar=parent;
        toDelNode=thisNode;
    }else{
        parent=thisNode;
        now=thisNode->left;
        while(now->right!=NULL){
            parent=now;
            now=now->right;
        }
        toDelPar=parent;
        toDelNode=now;
    }

    assert(toDelNode->left==NULL || toDelNode->right==NULL);

    //find blocker
    now=tree;
    while(now!=NULL){
        if(toDelNode->value==now->value){
            break;
        }
        if(toDelNode->value<now->value){
            if(!(Height(now->left)>Height(now->right) ||
            Height(now->left)<Height(now->right) && Height(now->right->left)<Height(now->right->right) ||
            Height(now->left)<Height(now->right) && Height(now->right->left)>Height(now->right->right) && Height(now->right->left->left)==Height(now->right->left->right))){
                blocker=now;
            }
            now=now->left;
        }else{
            if(!(Height(now->right)>Height(now->left) || 
            Height(now->right)<Height(now->left) && Height(now->left->right)<Height(now->left->left) ||
            Height(now->right)<Height(now->left) && Height(now->left->right)>Height(now->left->left) && Height(now->left->right->left)==Height(now->left->right->right))){
                blocker=now;
            }
            now=now->right;
        }
    }

    //start from blocker decrease height by 1
    now=blocker==NULL?tree:blocker;
    while(now!=NULL){
        if(toDelNode->value==now->value){
            break;
        }else if(toDelNode->value<now->value){
            now=now->left;
        }else{
            now=now->right;
        }

        if(now!=NULL){
            now->height--;
        }
    }
    if(blocker==NULL){
        tree->height--;
    }

    //actually removing toDelNode
    bool needToCopy=toDelNode!=thisNode;
    int valueDeleted=toDelNode->value;
    AVL* toDelSubtree=toDelNode->left!=NULL?toDelNode->left:toDelNode->right;

    if(toDelPar==NULL){
        tree=toDelSubtree;
    }else{
        if(toDelNode==toDelPar->left){
            toDelPar->left=toDelSubtree;
        }else{
            toDelPar->right=toDelSubtree;
        }
    }

    delete toDelNode;

    balance(valueDeleted);

    if(needToCopy){
        thisNode->value=valueDeleted;
    }
}

int main(int argc,char* argv[]){

    // freopen("output/in.txt","r",stdin);

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int op,data;
        cin>>op>>data;
        if(op==1){
            Insert(data);
        }else{
            Remove(data);
        }

        tree->print();
        cout<<endl;
    }
    return 0;
}