```cpp
class rbtree{
int root;//根节点编号。
int cnt;//节点个数
// struct trush{//垃圾回收
// int num;
// int no[1000010];
// }tr;
struct data{
int key;//数据值
int fa;//父节点编号
int rs;//右儿子编号
int ls;//左儿子编号
bool col;//颜色 1红,0黑
int getkey() {return key;}
int getpar() {return fa;}
}node[1000100];
void leftrotate(int x)//对x左旋
{
int y=node[x].rs;
node[x].rs=node[y].ls;
if(node[y].ls!=0) node[node[y].ls].fa=x;
node[y].fa=node[x].fa;
if(node[x].fa==0) root=y;
else {
if(x==node[node[x].fa].ls) node[node[x].fa].ls=y;
else node[node[x].fa].rs=y;
}
return ;
}
void rightrotate(int y)//对y右旋
{
int x=node[y].ls;
node[y].ls=node[x].rs;
if(node[x].rs!=0) node[node[x].rs].fa=y;
node[x].fa=node[y].fa;
if(node[y].fa==0) root=x;
else{
if(y==node[node[y].fa].rs) node[node[y].fa].rs=x;
else node[node[y].fa].ls=x;
}
return ;
}
void insertfixedup(int n)
{
int par,grapar;//父亲和祖父的节点编号
while(((par = node[n].fa)!=0) && (node[par].col==1) )
{
grapar=node[par].fa;
if(par==node[grapar].ls)
{
int unc=node[grapar].rs;
if(unc!=0&&node[unc].col==1)
{
node[unc].col=0;node[par].col=0;
node[grapar].col=1;
n=grapar;
continue;
}
if(n==node[par].rs)
{
leftrotate(par);
data tem=node[par];
node[par]=node[n];
node[n]=tem;
/*
leftrotate(par);
swap(par,n);
*/
}
node[par].col=0;
node[grapar].col=1;
leftrotate(grapar);
}
}
node[root].col=0;
}
void insert(int n)//将编号为n的节点插入到树里.
{
int x=root;
int par=0;
while(x!=0)
{
par=x;
int cmp=node[x].key-node[n].key;
if(cmp<0) x=node[x].rs;
else x=node[x].ls;
}
node[n].fa=par;
if(par!=0) {
int cmp=node[par].key-node[n].key;
if(cmp<0) node[par].rs=n;
else node[par].ls=n;
}
else root=n;
insertfixedup(n);
}
int newnode(int key)
{
// if(tr.num>0) {
// node[tr.no[tr.num]].key=key;
// node[tr.no[tr.num]].fa=0;
// node[tr.no[tr.num]].rs=0;
// node[tr.no[tr.num]].ls=0;
// node[tr.no[tr.num]].col=1;
// tr.num--;
// return tr.no[tr.num+1];
// }
node[++cnt].col=1;
node[cnt].key=key;
node[cnt].fa=0;
node[cnt].ls=0;
node[cnt].rs=0;
insert(cnt);
return cnt;
}
void deletfixedup(int n,int par)
{
int other;
while(n==0||node[n].col==0&&(n!=root))
{
if(node[par].ls==n)
{
other=node[par].rs;
if(node[other].col==1) node[other].col=0,node[par].col=1,leftrotate(par),other=node[par].rs;
if(node[other].ls==0 ||(node[node[other].ls].col==0)&&(node[other].rs==0||node[node[other].rs].col==0))
{
node[other].col=1;
n=par;
par=node[n].fa;
}
else {
if(node[other].rs==0||node[node[other].rs].col==0)
{
node[node[other].ls].col=0;
node[other].col=1;
rightrotate(other);
other=node[par].rs;
}
if(other!=0) node[other].col=node[par].col;
node[par].col=0;
node[node[other].rs].col=0;
leftrotate(par);
n=root;
break;
}
}
else {
other=node[par].ls;
if(node[other].col==1) {
node[other].col=0;
node[par].col=1;
rightrotate(par);
other=node[par].ls;
}
if((node[other].ls==0||node[node[other].ls].col==0)&&(node[other].rs==0 || node[node[other].rs].col==0))
{
node[other].col=1;
n=par;
par=node[n].fa;
}
else {
if(node[other].ls==0||node[node[other].ls].col==0)
{
node[node[other].rs].col=0;
node[other].col=1;
leftrotate(other);
other=node[par].ls;
}
node[other].col=node[par].col;
node[par].col=0;
node[node[other].ls].col=0;
rightrotate(par);
n=root;
break;
}
}
}
if(n!=0) node[n].col=0;
}
void delet1(int n)
{
int chi;
int par;
bool col;
if((node[n].ls!=0)&&(node[n].rs!=0))
{
int rep=n;
rep=node[rep].rs;
while(node[rep].ls!=0) rep=node[rep].ls;
if(node[n].fa!=0) {
if(n==node[node[n].fa].ls)
node[node[n].fa].ls=rep;
else node[node[n].fa].rs=rep;
}
else {
root=rep;
}
chi=node[rep].rs;
par=node[rep].fa;
col=node[rep].col;
if(par==n){par=rep;}
else {
if(chi!=0) node[chi].fa=par;
node[par].ls=chi;
node[rep].rs=node[n].rs;
node[node[n].rs].fa=rep;
}
node[rep].fa=node[n].fa;
node[rep].col=node[n].col;
node[rep].ls=node[n].ls;
node[node[n].ls].fa=rep;
if(col=0) {
deletfixedup(chi,par);
}
return ;
}
}
int serch(int x,int k)
{
while(x!=0) {
int cmp=k-node[x].key;
if(cmp<0) x=node[x].ls;
else if(cmp>0) x=node[x].rs;
else return x;
}
return x;
}
void delet(int key)
{
int n;
if((n=serch(root,key))!=0) delet1(n);
}
void print(int t,int k,int dri)
{
if(dri==0) printf("root=: %d key=: %d\n",t,node[t].key);
printf("num=: %d key=: %d col=: %dfa's: %d son'",t,node[t].key,node[t].col,dri);
print(node[t].ls,node[t].key,-1);
print(node[t].rs,node[t].key,1);
return ;
}
}rbt;
```
by Arcturus1350 @ 2018-07-11 08:10:18
太强了
我只会
```cpp
map<int,int> rbt;
```
by iotang @ 2018-07-11 08:20:37
@[cn：苏卿念](/space/show?uid=57699) $\%\%\%$红黑树大王$\%\%\%\%$
by 颜伟业_C_Asm @ 2018-07-11 08:20:51
太强了我只会set<int> RBT
by BriMon @ 2018-07-11 08:22:22
太强了我只会set<int> RBT
by 颜伟业_C_Asm @ 2018-07-11 08:22:54
%%%%
by wangyitong @ 2018-07-11 08:23:01
太强了我只会set<int> RBT
by wangyitong @ 2018-07-11 08:24:42
太强了我只会set<int> RBT
by wzhy @ 2018-07-11 08:25:39
太强了我只会set<int> RBT
by codesonic @ 2018-07-11 08:29:15
太强了我只会set<int> RBT
by Ameyax @ 2018-07-11 08:32:02