数据结构8——无旋Treap-创新互联
题目链接：洛谷 P3369 【模板】普通平衡树.
这只是一篇用来存代码的博客。平衡树使用无旋Treap实现。
将保存不同语言（偏竞赛风格）的代码作为对比。
- C++ 11
- Python 3.6
- Java 8
#include#include#include#includestruct node{int val,rk,siz;
node *ls,*rs;
node(int val=0):val(val){rk=rand();siz=1;ls=rs=NULL;}
void upd(){siz=1;
if(ls!=NULL)
siz+=ls->siz;
if(rs!=NULL)
siz+=rs->siz;
}
}*rt;
void split(node *o,node *&a,node *&b,const int &v){if(o==NULL){a=b=NULL;
return;
}
if(o->val<=v){a=o;
split(o->rs,a->rs,b,v);
}
else{b=o;
split(o->ls,a,b->ls,v);
}
o->upd();
}
void merge(node *&o,node *a,node *b){if(a==NULL){o=b;
return;
}
if(b==NULL){o=a;
return;
}
if(a->rkrk){o=a;
merge(o->rs,a->rs,b);
}
else{o=b;
merge(o->ls,a,b->ls);
}
o->upd();
}
void insert(node *&o,int v){node *l,*r,*u=new node(v);
split(o,l,r,v);
merge(l,l,u);
merge(o,l,r);
}
void erase(node *&o,int v){node *l,*r,*u;
split(o,l,r,v);
split(l,l,u,v-1);
if(u!=NULL){node *t=u;
merge(u,u->ls,u->rs);
delete t;
}
merge(l,l,u);
merge(o,l,r);
}
int find_by_order(const node *o,int k){if(o==NULL)
return -1;
int lsiz=0;
if(o->ls!=NULL)
lsiz=o->ls->siz;
if(k==lsiz+1)
return o->val;
if(k<=lsiz)
return find_by_order(o->ls,k);
else
return find_by_order(o->rs,k-lsiz-1);
}
int order_of_key(node *&o,int v){node *l,*r;
split(o,l,r,v-1);
int res;
if(l==NULL)
res=1;
else
res=l->siz+1;
merge(o,l,r);
return res;
}
int prev_val(node *&o,int v){node *l,*r;
split(o,l,r,v-1);
if(l==NULL)
return -1;
int res=find_by_order(l,l->siz);
merge(o,l,r);
return res;
}
int next_val(node *&o,int v){node *l,*r;
split(o,l,r,v);
if(r==NULL)
return -1;
int res=find_by_order(r,1);
merge(o,l,r);
return res;
}
int main(){srand(100000);
int T;scanf("%d",&T);
while(T--){int opt,x;scanf("%d%d",&opt,&x);
if(opt==1)
insert(rt,x);
else if(opt==2)
erase(rt,x);
else if(opt==3)
printf("%d\n",order_of_key(rt,x));
else if(opt==4)
printf("%d\n",find_by_order(rt,x));
else if(opt==5)
printf("%d\n",prev_val(rt,x));
else
printf("%d\n",next_val(rt,x));
}
return 0;
} from random import random
class treap:
class node:
def __init__(self,val=0,ls=None,rs=None)->None:
self.val=val
self.key=random()
self.ls=ls
self.rs=rs
self.siz=1
def upd(self):
self.siz=1
if self.ls:
self.siz+=self.ls.siz
if self.rs:
self.siz+=self.rs.siz
def __init__(self)->None:
self.root=None
def __merge(self,l,r)->None:
if not l:
return r
if not r:
return l
if l.keyNone:
if not o:
return None,None
if o.val<=v:
o.rs,tr=self.__split(o.rs,v)
o.upd()
return o,tr
else:
tr,o.ls=self.__split(o.ls,v)
o.upd()
return tr,o
def insert(self,v)->None:
u=self.node(val=v)
l,r=self.__split(self.root,v)
l=self.__merge(l,u)
self.root=self.__merge(l,r)
def erase(self,v)->bool:
l,r=self.__split(self.root,v)
l,u=self.__split(l,v-1)
if u==None:
self.root=self.__merge(l,r)
return False
u=self.__merge(u.ls,u.rs)
l=self.__merge(l,u)
self.root=self.__merge(l,r)
return True
def __kth(self,o,v):
if o==None:
return None
lsiz=0
if o.ls:
lsiz=o.ls.siz
if v<=lsiz:
return self.__kth(o.ls,v)
elif v==lsiz+1:
return o.val
else:
return self.__kth(o.rs,v-lsiz-1)
def kth(self,v):
return self.__kth(self.root,v)
def rank(self,v):
l,r=self.__split(self.root,v-1)
res=1
if l:
res+=l.siz
self.root=self.__merge(l,r)
return res
def prev(self,v):
l,r=self.__split(self.root,v-1)
if l==None:
return None
res=self.__kth(l,l.siz)
self.root=self.__merge(l,r)
return res
def next(self,v):
l,r=self.__split(self.root,v)
if r==None:
return None
res=self.__kth(r,1)
self.root=self.__merge(l,r)
return res
if __name__=="__main__":
T=int(input())
tr=treap()
opt=[None,tr.insert,tr.erase,tr.rank,tr.kth,tr.prev,tr.next]
for i in range(T):
expr=list(map(int,input().split()))
if expr[0]>=3:
print(opt[expr[0]](expr[1]))
else:
opt[expr[0]](expr[1]) 咕咕咕。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
新闻标题：数据结构8——无旋Treap-创新互联
本文来源：http://mswzjz.cn/article/dspice.html