POJ3481 AVL树模板 ++codevs1285

Posted by Cww97 on 2016-05-20

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/51465036
这两天鲍鱼讲AVL树
poj3481
题意大概是每个人有两个参数k,p
按p排序,每次输出最大的或最小的人的k值
这道题方法很多,,
正好练一下AVL树
这里有个板不过这孩子似乎把左旋右旋写反了,同时delete的时候少了一个域= =
当然你要是用set,map之类的玩意A了我也没什么办法这里写图片描述
敲完之后编译失败了好久,一开始以为是class的锅
呜呜呜,找cw和kpm看了看,,半天没编译通过
后来,,,一会rorate,一会rotate。。
这里写图片描述
前面falg后面flag,,,,mdzz

存一下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
//poj3481 cww97
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
int x,y,bf,h;//bf=balance factor,h=height
Node *l,*r;
};

class AVLTree{
public:
void Init() { rt = NULL; }
int H(Node *T){return (T==NULL)?0:T->h;}
int BF(Node *l,Node *r){//get balance factor
if (NULL==l && NULL==r) return 0;
else if (NULL == l) return -r->h;
else if (NULL == r) return l->h;
return l->h - r->h;
}

Node *Lrorate(Node *a){//left rorate
Node *b;
b=a->r;
a->r=b->l;
b->l=a;
a->h=max(H(a->l),H(a->r)) + 1;
b->h=max(H(b->l),H(b->r)) + 1;
a->bf=BF(a->l,a->r);
b->bf=BF(b->l,b->r);
return b;
}
Node *Rrorate(Node *a){//right rorate
Node *b;
b=a->l;
a->l=b->r;
b->r=a;
a->h=max(H(a->l),H(a->r)) + 1;
b->h=max(H(b->l),H(b->r)) + 1;
a->bf=BF(a->l,a->r);
b->bf=BF(b->l,b->r);
return b;
}
Node *LRrorate(Node *a){//left then right
a->l = Lrorate(a->l);
Node *c;
c=Rrorate(a);
return c;
}
Node *RLrorate(Node *a){//right then left
a->r=Rrorate(a->r);
Node *c;
c=Lrorate(a);
return c;
}

void Insert(int x,int y){_Insert(rt,x,y);}
void _Insert (Node *&T,int x,int y){
if (NULL==T){
T=(Node*)malloc(sizeof(Node));
T->x=x; T->y=y;
T->bf=0;T->h=1;
T->l=T->r=NULL;
return ;
}
if (y < T->y) _Insert(T->l,x,y);
else if (y > T->y) _Insert(T->r,x,y);
else return ; //error :the same y

T->h=max(H(T->l),H(T->r))+1;//maintain
T->bf=BF(T->l,T->r);

if (T->bf > 1 || T->bf < -1){//not balanced
if (T->bf > 0 && T->l->bf > 0)T=Rrorate(T);
else if (T->bf < 0 && T->r->bf < 0)T=Lrorate(T);
else if (T->bf > 0 && T->l->bf < 0)T=LRrorate(T);
else if (T->bf < 0 && T->r->bf > 0)T=RLrorate(T);
}
}

void Delete(int flag){//flag==1:delete max
if (NULL==rt){puts("0");return ;}
Node *t=rt;
if (flag)while (t->r)t=t->r;
else while (t->l)t=t->l;
printf("%d\n",t->x);
_Delete(rt,t->y);
}
void _Delete(Node *&T,int y){
if (NULL==T)return ;
if (y < T->y){//y at left
_Delete(T->l,y);
T->bf=BF(T->l,T->r);
if (T->bf<-1){
if (1==T->r->bf)T=RLrorate(T);
else T=Lrorate(T);//bf==0 or -1
}
}else if (y > T->y){//y at right
_Delete(T->r,y);
T->bf=BF(T->l,T->r);
if (T->bf>1){
if (-1==T->l->bf)T=LRrorate(T);
else T=Rrorate(T);//bf==0 or 1
}
}else {//here is y,,this part is not used in this problem
if (T->l&&T->r){//left &&right
Node *t=T->l;
while (t->r)t=t->r;
T->y=t->y;
T->x=t->x;
_Delete(T->l,t->y);
T->bf=BF(T->l,T->r);
if (T->bf<-1){
if (1==T->r->bf)T=RLrorate(T);
else T=Lrorate(T);//bf==0 or -1
}
}else {//left || right
Node *t=T;
if (T->l)T=T->l;
else if(T->r)T=T->r;
else {free(T);T=NULL;}
if (T)free(t);
}
}
}

//Debug,you will not need it at this problem
void show(){InOrder(rt);puts("EndShow");}
void InOrder(Node *T){//print l rt r
if (NULL==T)return ;
InOrder(T->l);
printf("%d:%d ",T->x,T->y);
InOrder(T->r);
}
void Free(){FreeTree(rt);}
void FreeTree(Node *T){
if (NULL==T)return ;
FreeTree(T->l);
FreeTree(T->r);
free(T);
}

private:
Node *rt;//root
};

int main(){
//freopen("fuck.in","r",stdin);
int op,x,y;
AVLTree T;
T.Init();
for (;scanf("%d",&op)==1&&op;){
if (op==1){
scanf("%d%d",&x,&y);
T.Insert(x,y);
}else if(op==2)T.Delete(1);
else if (op==3)T.Delete(0);
else break;//error
//T.show();
}
T.Free();
return 0;
}
这里写图片描述
这里写图片描述

codevs1285
这题要注意题意
宠物多人少的时候,把宠物扔树上
反之,把人扔树上
写这里的时候发现前面delete的时候有个地方写残了= =
承旭说此题可以用多重集秒掉
set里面就是红黑树,,,WUWUWU
过两天尝试一下

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
//codevs1285 宠物收养所
//by cww97
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 0xfffffff
#define BASE 1000000
using namespace std;
int ans=0;
struct Node{
int x,bf,h;//bf=balance factor,h=height
Node *l,*r;
};

class AVLTree{
public:
void Init() { rt = NULL; }
int H(Node *T){return (T==NULL)?0:T->h;}
int BF(Node *l,Node *r){//get balance factor
if (NULL==l && NULL==r) return 0;
else if (NULL == l) return -r->h;
else if (NULL == r) return l->h;
return l->h - r->h;
}

Node *Lrorate(Node *a){//left rorate
Node *b;
b=a->r;
a->r=b->l;
b->l=a;
a->h=max(H(a->l),H(a->r)) + 1;
b->h=max(H(b->l),H(b->r)) + 1;
a->bf=BF(a->l,a->r);
b->bf=BF(b->l,b->r);
return b;
}
Node *Rrorate(Node *a){//right rorate
Node *b;
b=a->l;
a->l=b->r;
b->r=a;
a->h=max(H(a->l),H(a->r)) + 1;
b->h=max(H(b->l),H(b->r)) + 1;
a->bf=BF(a->l,a->r);
b->bf=BF(b->l,b->r);
return b;
}
Node *LRrorate(Node *a){//left then right
a->l = Lrorate(a->l);
Node *c;
c=Rrorate(a);
return c;
}
Node *RLrorate(Node *a){//right then left
a->r=Rrorate(a->r);
Node *c;
c=Lrorate(a);
return c;
}

void Insert(int x){_Insert(rt,x);}
void _Insert (Node *&T,int x){
if (NULL==T){
T=(Node*)malloc(sizeof(Node));
T->x=x;
T->bf=0;T->h=1;
T->l=T->r=NULL;
return ;
}
if (x < T->x) _Insert(T->l,x);
else if (x > T->x) _Insert(T->r,x);
else return ; //error :the same y

T->h=max(H(T->l),H(T->r))+1;//maintain
T->bf=BF(T->l,T->r);

if (T->bf > 1 || T->bf < -1){//not balanced
if (T->bf > 0 && T->l->bf > 0)T=Rrorate(T);
else if (T->bf < 0 && T->r->bf < 0)T=Lrorate(T);
else if (T->bf > 0 && T->l->bf < 0)T=LRrorate(T);
else if (T->bf < 0 && T->r->bf > 0)T=RLrorate(T);
}
}

void GetPet(int x){//get pet or person
if (NULL==rt){return ;}
int small=0,large=INF;
//printf("x=%d\n",x);
int flag;
if (Find(rt,x,small,large)){
printf("find %d\n",x);
_Delete(rt,x);
}else if (small==0)flag=1;
else if (large==INF)flag=0;
else if (large-x<x-small)flag=1;
else flag=0;

if (!flag){//choose large
_Delete(rt,small);
ans=(ans+x-small)%BASE;
}else {
_Delete(rt,large);
ans=(ans+large-x)%BASE;
}
}
bool Find(Node *T,int x,int &small,int &large){
if (NULL==T)return 0;
if (x==T->x)return 1;
if (x<T->x){
large=min(large,T->x);
return Find(T->l,x,small,large);
}else{
small=max(small,T->x);
return Find(T->r,x,small,large);
}
}
void _Delete(Node *&T,int x){
if (NULL==T)return ;
if (x < T->x){//y at left
_Delete(T->l,x);
T->bf=BF(T->l,T->r);
if (T->bf<-1){
if (1==T->r->bf)T=RLrorate(T);
else T=Lrorate(T);//bf==0 or -1
}
}else if (x > T->x){//y at right
_Delete(T->r,x);
T->bf=BF(T->l,T->r);
if (T->bf>1){
if (-1==T->l->bf)T=LRrorate(T);
else T=Rrorate(T);//bf==0 or 1
}
}else {//here is x
if (T->l&&T->r){//left &&right
Node *t=T->l;
while (t->r)t=t->r;
T->x=t->x;
_Delete(T->l,t->x);
T->bf=BF(T->l,T->r);
if (T->bf<-1){
if (1==T->r->bf)T=RLrorate(T);
else T=Lrorate(T);//bf==0 or -1
}
}else {//left || right
Node *t=T;
if (T->l)T=T->l;
else if(T->r)T=T->r;
else {free(T);T=NULL;}
if (T)free(t);
}
}
}

//Debug,you will not need it at this problem
void show(){InOrder(rt);puts("EndShow");}
void InOrder(Node *T){//print l rt r
if (NULL==T)return ;
InOrder(T->l);
printf("%d ",T->x);
InOrder(T->r);
}
void Free(){FreeTree(rt);}
void FreeTree(Node *T){
if (NULL==T)return ;
FreeTree(T->l);
FreeTree(T->r);
free(T);
}

private:
Node *rt;//root
};

int main(){
freopen("fuck.in","r",stdin);
int n,x,op,a=0,b=0;
scanf("%d",&n);
AVLTree T; T.Init();
for (;n--;){
scanf("%d%d",&op,&x);
//if pets>people put pets into the tree
//else put people into the tree
if (op==0){//come a pet
a++;
if (a>b)T.Insert(x);//more pet
else T.GetPet(x);//more people
}else{//come a person
b++;
if (a<b)T.Insert(x);//more people
else T.GetPet(x);//more pet
}
}
printf("%d\n",ans%BASE);
T.Free();
return 0;
}

这里写图片描述这里写图片描述