【数据结构】二叉排序树小礼包(对splay,Treap,SBT的理解,例
二×排序树(BST),的主要性质是有序性,树的中序遍历始终为同一个有序序列,也就是对于每一节点u u的左儿子的键值应当小于u,右儿子键值大于u。 排序树的基本操作0.节点 struct Node {
int v,ch[2],fa,sz;
} d[MAXD];
int tot = 0;
inline int newNode() {
memset(d + ++tot,0,sizeof d[0]);
return tot;
}
v: 键值 1.旋转 (旋转,跳跃!) inline void updata(int x) {
d[x].sz = d[d[x].ch[0]].sz + d[d[x].ch[1]].sz + 1;
}
inline void rotate(int x) {
int y = d[x].fa;
bool f = (d[y].ch[1] == x);
d[x].fa = d[y].fa;
d[y].fa = x;
if(d[x].fa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
d[y].ch[f] = d[x].ch[!f];
if(d[x].ch[!f]) d[d[x].ch[!f]].fa = y;
d[x].ch[!f] = y;
updata(y);
updata(x);
}
2.插入 int getPos(int val) {
int u = root,l = 0;
while(u) {
if(d[u].v == val) return u;
l = u;
u = d[u].ch[val > d[u].v];
}
return l;
}
int insert(int val) {
int p = getPos(val);
if(p && d[p].v == val) {d[p].cnt ++; return p;}
int r = newNode();
if(p) d[p].ch[val > d[p].v] = r;
d[r].fa = p;
d[r].v = val;
d[r].cnt = 1;
d[r].pri = random(MAXP);
if(!root) root = r;
adjust(r);
return r;
}
#2 按照排名插入类似于按照键值, 寻找插入位置方法类似于下面的函数 int getByRank(int rk,int u = root) {
while(u) {
if(d[d[u].ch[0]].sz >= rk)
u = d[u].ch[0];
else if(d[d[u].ch[0]].sz + 1 >= rk)
return u;
else rk -= d[d[u].ch[0]].sz + 1,u = d[u].ch[1];
}
return u;
}
3.删除 ps : 通用简单但是略暴力的方法是伪删除,找到原节点后打个vis标记表示之后的操作忽略该节点即可 4.查找 int getPos(int val) {
int u = root,l = 0;
while(u) {
if(d[u].v == val) return u;
l = u;
u = d[u].ch[val > d[u].v];
}
return l;
}
5.获得前驱或后继 int getNearby(int u,bool f) {
splay(u,0);
if(!d[u].ch[f]) throw "getNearby";
u = d[u].ch[f];
while(d[u].ch[!f]) u = d[u].ch[!f];
return u;
}
** 关于批量插入 int * src;
int buildTree(int lef,int rig) {
if(lef > rig) return 0;
int mid = (lef + rig) >> 1;
int r = newNode();
d[r].v = src[mid];
d[r].sz = 1;
if(lef == rig)
return r;
d[r].ch[0] = buildTree(lef,mid - 1);
d[r].ch[1] = buildTree(mid + 1,rig);
d[d[r].ch[0]].fa = r;
d[d[r].ch[1]].fa = r;
d[r].sz += d[d[r].ch[0]].sz + d[d[r].ch[1]].sz;
return r;
}
以上大约就是排序树最基本的通用操作了 splay 伸展树特点 : 我爱旋转! splay通过splay进行调整 首先显然只需要不停地while(d[x].fa != g) rotate(x)就可以了 比如: void splay (int x,int g) {
while(d[x].fa != g) {
int y = d[x].fa;
int z = d[y].fa;
if(z != g) {
if((d[z].ch[1] == y) == (d[y].ch[1] == x))
rotate(y);
else rotate(x);
}
rotate(x);
}
if(g == 0) root = x;
else updata(x);
}
既然有更好的调整方法,那我们为什么要splay呢? 我们可以使用splay操作来改变,操作树的形态来简单地完成一些其他排序树难以完成的操作。 void erase(int x) {
int p = getPos(x);
int lpos = getNearby(p,false);
int rpos = getNearby(p,true);
splay(lpos,0);
splay(rpos,lpos);
d[rpos].ch[0] = 0;
splay(rpos,0);
}
上面的单点删除,获取了x的位置,然后获取x的前驱后继,把前驱旋转到根(0),然后把后继旋转到根的右儿子位置,那么节点x必然在根的右儿子的左儿子并且x的子树里只有它自己,于是直接删去 扩广一下,运用到区间删除中 void eraseInterval(int lpos,int rpos) {
splay(lpos,0);
}
2.splay区间翻转 void reverseInterval(int lefp,int rigp) {
splay(lefp,0);
splay(rigp,lefp);
if(d[rigp].ch[0]) d[d[rigp].ch[0]].rv ^= 1;
}
接下来每访问一个节点前都要下传懒标记 inline void pushdown(int x) {
if(!d[x].rv) return ;
swap(d[x].ch[0],d[x].ch[1]);
d[d[x].ch[0]].rv ^= 1;
d[d[x].ch[1]].rv ^= 1;
d[x].rv = 0;
}
…大概就那么几个特别操作 接下来是splay的模板以及“普通平衡树”一题的运行效果
代码(两年前写的比较丑请见谅= =!) #include<cstdio>
//#define TAG
#ifdef TAG
#include<time.h>
#include<windows.h>
#endif
#define FOR(x) for(int i=1;i<=x;i++)
#define INF 90100099
#define MAXN 601000
int ch[MAXN][2],fa[MAXN],k[MAXN],sz[MAXN],cnt[MAXN];
int tmp,root=0,top=1;
void getint(int&num)
{
char c;int flag=1;num=0;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
num*=flag;
}
void chi(int i){
printf("%d,%d ",k[ch[i][0]],k[ch[i][1]]);
}
void debug(int x){
if(x==-1)x=root;
puts("-========================-");
printf("index:%dn",x);
printf("code:%dn",k[x]);
printf("cnt:%dn",cnt[x]);
printf("child:n %d,%dn",k[ch[x][0]],k[ch[x][1]]);
chi(ch[x][0]);chi(ch[x][1]);
puts("");
printf("father:%dn",fa[x]);
printf("size:%dn",sz[x]);
puts("-========================-");
}
void updata(int v){
sz[v]=sz[ch[v][0]]+sz[ch[v][1]]+cnt[v];
}
void rotato(int x){
int y=fa[x],z=fa[y];
bool f=(ch[y][1]==x);
ch[y][f]=ch[x][!f];
if(ch[y][f])fa[ch[y][f]]=y;
ch[x][!f]=y,fa[y]=x;
fa[x]=z;
if(z)ch[z][ch[z][1]==y]=x;
updata(y);
//updata(x);
//printf("rotato %d up->%d[sz%d]n",x,ch[x][!f],sz[x]);
}
void splay(int a,int g){
int b,c;
for(;fa[a]!=g;rotato(a)){
b=fa[a];
c=fa[b];
if(c!=g){
if((ch[b][0]==a)==(ch[c][0]==b)){
rotato(b);
}
else rotato(a);
}
}
if(g==0)root=a;
if(!g)updata(a);
}
int nxtNod(int v,bool mod){
int x=root,y;
while(x!=0){
y=x;
if(k[x]==v)break;
x=ch[x][k[x]<v];
}
if((k[y]>v&&mod==1)||(k[y]<v&&mod==0))
return y;
splay(y,0);
int tmp=ch[y][mod];
while(ch[tmp][!mod])tmp=ch[tmp][!mod];
return tmp;
}
void insert(int v){
int x=root,y=0;
while(x!=0){
sz[x]++;
y=x;
if(k[x]==v){
cnt[x]++;
splay(x,0);
return;
}
if(k[x]<v)x=ch[x][1];
else if(k[x]>v)x=ch[x][0];
}
k[top]=v;
if(y)ch[y][v>k[y]]=top;
fa[top]=y;
cnt[top]=sz[top]=1;
top++;
splay(top-1,0);
return;
}
void deletf(int v){
int l=nxtNod(v,0);
int r=nxtNod(v,1);
splay(l,0);
splay(r,l);
cnt[ch[r][0]]--;
if(!cnt[ch[r][0]]){
ch[r][0]=0;
}
updata(ch[r][0]);
updata(r);
updata(l);
}
int rank(int v){//v的排名
int x=root,ret=0;
while(x!=0){
if(k[x]==v)return ret+sz[ch[x][0]];
if(k[x]>v) x=ch[x][0];
else ret+=sz[ch[x][0]]+cnt[x],x=ch[x][1];
}
return ret+x?0:1;
}
int rankval(int rk){//排名的数 2
int x=root,y;
if(sz[x]<rk)return 0;
while(x!=0){
//printf("rkget:%d(%d)n",k[x],rk);
y=x;
if(sz[ch[x][0]]>=rk)x=ch[x][0];
else if(cnt[x]>=rk-sz[ch[x][0]])return x;
else rk-=sz[ch[x][0]]+cnt[x],x=ch[x][1];
}
return y;
}
int main(){
int n,ag1,ag2;
insert(INF);
//debug(1);
insert(-INF);
//freopen("in.txt","r",stdin);
scanf("%d",&n);
FOR(n){
getint(ag1);getint(ag2);
if(ag1==1)insert(ag2);
if(ag1==2)deletf(ag2);
if(ag1==3)printf("%dn",rank(ag2));
if(ag1==4)printf("%dn",k[rankval(ag2+1)]);
if(ag1==5)printf("%dn",k[nxtNod(ag2,false)]);
if(ag1==6)printf("%dn",true)]);
if(ag1==0)debug(ag2);
}
}
效率: 例题1.[TYVJ1729]文艺平衡树 splay区间翻转裸题,思路见上文 #include <cstdio>
#include <cstring>
#include <algorithm>
namespace splay {
using std :: swap;
const int MAXD = 110000;
struct Node {
int v,sz;
bool rv;
} d[MAXD];
int tot = 0,root = 0,maxium,minimum;
inline int newNode() {
memset(d + ++tot,sizeof d[0]);
return tot;
}
inline void pushdown(int x) {
if(!d[x].rv) return ;
swap(d[x].ch[0],d[x].ch[1]);
d[d[x].ch[0]].rv ^= 1;
d[d[x].ch[1]].rv ^= 1;
d[x].rv = 0;
}
inline void updata(int x) {
d[x].sz = d[d[x].ch[0]].sz + d[d[x].ch[1]].sz + 1;
}
inline void rotate(int x) {
int y = d[x].fa;
bool f = (d[y].ch[1] == x);
d[x].fa = d[y].fa;
d[y].fa = x;
if(d[x].fa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
d[y].ch[f] = d[x].ch[!f];
if(d[x].ch[!f]) d[d[x].ch[!f]].fa = y;
d[x].ch[!f] = y;
updata(y);
updata(x);
}
void splay (int x,int g) {
while(d[x].fa != g) {
int y = d[x].fa;
int z = d[y].fa;
if(z != g) {
if((d[z].ch[1] == y) == (d[y].ch[1] == x))
rotate(y);
else rotate(x);
}
rotate(x);
}
if(g == 0) root = x;
else updata(x);
}
int * src;
int buildTree(int lef,int rig) {
if(lef > rig) return 0;
int u = newNode();
int mid = (lef+rig) >> 1;
d[u].v = src[mid];
if(lef == rig){
d[u].sz = 1;
return u;
}
d[u].ch[0] = buildTree(lef,mid - 1);
d[u].ch[1] = buildTree(mid + 1,rig);
if(d[u].ch[0]) d[d[u].ch[0]].fa = u;
if(d[u].ch[1]) d[d[u].ch[1]].fa = u;
updata(u);
return u;
}
int getByRank(int rk,int u = root) {
while(u) {
pushdown(u);
if(d[d[u].ch[0]].sz >= rk)
u = d[u].ch[0];
else if(d[d[u].ch[0]].sz + 1 == rk)
return u;
else rk -= d[d[u].ch[0]].sz + 1,u = d[u].ch[1];
}
return u;
}
int jump(int u,int rk) {
splay(u,0);
if(d[u].ch[1] == 0) return 0;
return getByRank(rk,d[u].ch[1]);
}
void reverseInterval(int lefp,int rigp) {
//printf("rev: %d %dn",lefp,rigp);
splay(lefp,lefp);
if(d[rigp].ch[0]) d[d[rigp].ch[0]].rv ^= 1;
}
int * output;
void print(int u) {
if(!u) return ;
pushdown(u);
print(d[u].ch[0]);
*(output++) = d[u].v;
print(d[u].ch[1]);
}
void init() {
root = minimum = newNode();
d[minimum].ch[1] = maxium = newNode();
d[maxium].sz = 1;
d[minimum].sz = 2;
d[maxium].fa = minimum;
}
}
int buf[110000];
inline int getInt() {
int ret = 0;
char ch;
while((ch = getchar()) < '0' || ch > '9') ;
do {ret *= 10; ret += ch - '0';}
while((ch = getchar()) >= '0' && ch <= '9') ;
return ret;
}
int main() {
int n,m;
n = getInt(),m = getInt();
for(int i = 1; i<=n; i++)
buf[i] = i;
splay :: init();
splay :: src = buf;
splay :: d[splay :: maxium].ch[0]
= splay :: buildTree(1,n);
splay :: d[splay :: d[splay :: maxium].ch[0]].fa
= splay :: maxium;
splay :: d[splay :: maxium].sz += n;
splay :: d[splay :: minimum].sz += n;
int a,b;
for(int i = 1; i<=m; i++){
a = getInt();
b = getInt();
splay :: reverseInterval
(splay :: getByRank(a),splay :: getByRank(b + 2));
}
splay :: output = buf;
splay :: print(splay :: root);
for(int i = 1; i<=n; i++)
printf("%d ",buf[i]);
}
2.[NOI2003]文本编辑器 这道题充分体现了splay的灵活性 #include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
const int MAXL = 1024*1024*2;
namespace splay {
using std :: pair;
const int MAXD = MAXL;
void debug(int a,int b);
struct Node {
char v;
int fa,sz,ch[2];
} d[MAXD];
int tot = 0,minimum,root;
inline int newNode() {
memset(&d[++tot],sizeof d[0]);
return tot;
}
inline void updata(int u) {
d[u].sz = d[d[u].ch[0]].sz + d[d[u].ch[1]].sz + 1;
}
inline int rotate(int x) {
int y = d[x].fa;
bool f = (d[y].ch[1] == x);
d[y].ch[f] = d[x].ch[!f];
if(d[y].ch[f])d[d[y].ch[f]].fa = y;
d[x].ch[!f] = y;
d[x].fa = d[y].fa;
d[y].fa = x;
if(d[x].fa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
updata(y);
updata(x);
//printf("rot:%dn",x);
//getchar();
return x;
}
void splay(int x,int goal) {
while(d[x].fa != goal) {
int y = d[x].fa,z = d[y].fa;
if(z != goal) {
if((d[z].ch[0] == y) == (d[y].ch[0] == x))
rotate(y);
else rotate(x);
}
rotate(x);
}
if(goal == 0) root = x;
else updata(x);
}
int getNearby(int u,0);
if(!d[u].ch[f]) throw "getNearby";
u = d[u].ch[f];
while(d[u].ch[!f]) u = d[u].ch[!f];
return u;
}
int getByRank(int rk,int len) {
splay(u,0);
return getByRank(len+1,d[u].ch[1]);
}
void insertDir (int id,int to) {
int t = getNearby(to,true);
//puts("bef:");
//debug(root,0);
splay(t,0);
//printf("to : %d,t : %dn",to,t);
//debug(root,0);
splay(to,t);
d[to].ch[1] = id;
d[id].fa = to;
while(to){
d[to].sz += d[id].sz;
to = d[to].fa;
}
}
char * src;
int buildTree(int lef,int rig) {
if(lef > rig) return 0;
int mid = (lef + rig) >> 1;
int r = newNode();
d[r].v = src[mid];
d[r].sz = 1;
if(lef == rig)
return r;
d[r].ch[0] = buildTree(lef,mid - 1);
d[r].ch[1] = buildTree(mid + 1,rig);
d[d[r].ch[0]].fa = r;
d[d[r].ch[1]].fa = r;
d[r].sz += d[d[r].ch[0]].sz + d[d[r].ch[1]].sz;
return r;
}
void eraseInterval(int lpos,0);
}
char * output;
void print(int u) {
if(!u) return;
print(d[u].ch[0]);
*output = d[u].v;
++ output;
print(d[u].ch[1]);
}
char * getInterval(char * ans,int lpos,lpos);
output = ans;
print(d[rpos].ch[0]);
*output = ' ';
return ans;
}
void clear() {
tot = 0;
minimum = root = newNode();
maxium = d[root].ch[1] = newNode();
d[maxium].sz = 1;
d[minimum].sz = 2;
d[maxium].fa = minimum;
}
void debug(int u,int dep = 0) {
if(!u) return;
debug(d[u].ch[0],dep + 1);
printf("[%d](%d) u:%d,sz:%dn",dep,d[u].v,u,d[u].sz);
debug(d[u].ch[1],dep + 1);
}
}
char * readChars(char * str,int c) {
char * r = str;
while(c --){
*str = getchar();
if(*str == 'r' || *str == 'n') c ++;
else ++str;
}
return r;
}
inline int getInt() {
int ret = 0;
char ch;
while((ch = getchar()) < '0' || ch > '9') ;
do {ret *= 10; ret += ch - '0';}
while((ch = getchar()) >= '0' && ch <= '9') ;
ungetc(ch,stdin);
return ret;
}
char buf[MAXL];
int main () {
splay :: clear();
int cur = splay :: minimum;
int n;
scanf("%d",&n);
for(int i = 1; i<=n; i++) {
scanf("%s",buf);
if(buf[0] == 'I'){
int len = getInt();
splay :: src = readChars(buf,len);
splay :: insertDir(
splay :: buildTree(0,len - 1),cur);
} else if(buf[0] == 'N')
cur = splay :: getNearby(cur,true);
else if(buf[0] == 'P')
cur = splay :: getNearby(cur,false);
else if(buf[0] == 'D')
splay :: eraseInterval(cur,splay :: jump(cur,getInt()));
else if(buf[0] == 'M')
cur = splay :: getByRank(getInt() + 1);
else if(buf[0] == 'G')
printf("%sn",splay :: getInterval(buf,cur,getInt())));
else if(buf[0] == '*') splay :: debug(splay :: root);
}
}
Treap(身体有点不舒服。。下次在更Treap, SBT) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |