【算法笔记】普通平衡树的实现

  • 本文为博主原创，未经许可不得转载

时空复杂度对比

种类 Treap Splay 替罪羊树 0/1Trie树
Time 248ms 484ms 180ms 288ms
Memory 3762kb 3668kb 3668kb 39968kb

Treap

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define FILE "read"
#define MAXN 100005
int n,len,root,ans;
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
namespace Treap_Tree{
	struct node{int l,r,v,size,fix,w;}tr[MAXN];
	void update(int k){tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;}
	void rturn(int &k){int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;tr[t].size=tr[k].size;update(k);k=t;}
	void lturn(int &k){int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;tr[t].size=tr[k].size;update(k);k=t;}
	void insert(int &k,int x){
		if(k==0){len++;k=len;tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].fix=rand();return;}
		tr[k].size++;
		if(tr[k].v==x)tr[k].w++;
		else if(x>tr[k].v){insert(tr[k].r,x);if(tr[tr[k].r].fix<tr[k].fix)lturn(k);}
		else {insert(tr[k].l,x);if(tr[tr[k].l].fix<tr[k].fix)rturn(k);} 
	}
	void del(int &k,int x){
		if(k==0)return; 
		if(tr[k].v==x){
			if(tr[k].w>1){tr[k].w--;tr[k].size--;return;}
			if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;
			else if(tr[tr[k].l].fix<tr[tr[k].r].fix)rturn(k),del(k,x);
			else lturn(k),del(k,x);
		}
		else if(x>tr[k].v)tr[k].size--,del(tr[k].r,x);
		else tr[k].size--,del(tr[k].l,x);
	}
	int rank(int k,int x){
		if(k==0)return 0;
		if(tr[k].v==x)return tr[tr[k].l].size+1;
		else if(x>tr[k].v)return tr[tr[k].l].size+tr[k].w+rank(tr[k].r,x);
		else return rank(tr[k].l,x);
	}
	int Findkth(int k,int x){
		if(k==0)return 0;
		if(x<=tr[tr[k].l].size)return Findkth(tr[k].l,x);
		else if(x>tr[tr[k].l].size+tr[k].w)return Findkth(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
		else return tr[k].v;
	}
	void get_before(int k,int x){
		if(k==0)return;
		if(tr[k].v<x){ans=k;get_before(tr[k].r,x);}
		else get_before(tr[k].l,x);
	}
	void get_behind(int k,int x){
		if(k==0)return;
		if(tr[k].v>x){ans=k;get_behind(tr[k].l,x);}
		else get_behind(tr[k].r,x);
	}
}using namespace Treap_Tree;
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();
	int flag,x;
	for(int i=1;i<=n;i++){
		flag=read();  x=read();
		switch(flag){
			case 1:insert(root,x);break;
			case 2:del(root,x);break;
			case 3:printf("%d\n",rank(root,x));break;
			case 4:printf("%d\n",Findkth(root,x));break;
			case 5:ans=0;get_before(root,x);printf("%d\n",tr[ans].v);break;
			case 6:ans=0;get_behind(root,x);printf("%d\n",tr[ans].v);break;
		}
	}
	return 0;
}

　　

Splay

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define FILE "phs"
#define MAXN 100010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
namespace Splay_Tree{
	int root,cnt,v[MAXN],w[MAXN],size[MAXN],f[MAXN],son[MAXN][2];
	bool get(int x) {return son[f[x]][1]==x;}
	void clear(int x) {son[x][0]=son[x][1]=v[x]=w[x]=f[x]=size[x]=0;}
	void updata(int x) {size[x]=size[son[x][0]]+size[son[x][1]]+w[x];}
	int before(){int now=son[root][0];while(son[now][1])  now=son[now][1];return now;}
	int behind(){int now=son[root][1];while(son[now][0])  now=son[now][0];return now;}
	void rotate(int x){
		int y=f[x],z=f[y],which=get(x);
		son[y][which]=son[x][which^1];  f[son[y][which]]=y;
		f[y]=x;  son[x][which^1]=y;
		f[x]=z;  if(z)  son[z][son[z][1]==y]=x;
		updata(y);  updata(x);
	}
	void splay(int x){for(int fa;(fa=f[x]);rotate(x))if(f[fa])rotate((get(x)==get(fa)?fa:x));root=x;}
	void insert(int value){
		int now=root,fa(0);
		if(!now) {root=++cnt;v[root]=value;size[root]=w[root]=1;return;}
		while(1){
			if(value==v[now]) {w[now]++;splay(now);break;}
			fa=now; now=son[now][value>v[now]];
			if(now==0){
				now=++cnt;v[now]=value;size[now]=w[now]=1;
				f[now]=fa; son[fa][value>v[fa]]=now;splay(now); 
				break;
			}
		}
	}
	int find_rank(int value){
		int now=root,ans(0);
		while(1){
			if(value<v[now])  now=son[now][0];
			else{
				ans+=size[son[now][0]];
				if(value==v[now]) {splay(now); return ans+1;}
				ans+=w[now];
				now=son[now][1];
			}
		}
	}
	int find_Kth(int x){
		int now=root;
		while(1){
			if(son[now][0]&&x<=size[son[now][0]])  now=son[now][0];
			else{
				int temp=size[son[now][0]]+w[now];
				if(x<=temp)  return v[now];
				x-=temp;  now=son[now][1];
			}
		}
	}
	void del(int value){
		find_rank(value);
		if(w[root]>1)  {w[root]--; size[root]--;}
		else if(son[root][0]+son[root][1]==0) clear(root),root=0;
		else if(!son[root][0]) {int last=root;root=son[root][1];f[root]=0;clear(last);}
		else if(!son[root][1]) {int last=root;root=son[root][0];f[root]=0;clear(last);}
		else{
			int x=before(),last=root;
			splay(x);  son[root][1]=son[last][1];  f[son[last][1]]=root;
			clear(last);  updata(root);  
		}
	}
}using namespace Splay_Tree;
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n=read();
	for(int i=1;i<=n;i++){
		int flag=read(),x=read();
		switch(flag){
			case 1:insert(x);break;
			case 2:del(x);break;
			case 3:printf("%d\n",find_rank(x));break;
			case 4:printf("%d\n",find_Kth(x));break;
			case 5:insert(x);printf("%d\n",v[before()]);del(x);break;
			case 6:insert(x);printf("%d\n",v[behind()]);del(x);break;
		}
	}
	return 0;
}

　　

替罪羊树

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define INF 1000000000
#define FILE "read"
int n,len,root,top,stack[100005];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
namespace TiZuiYang_Tree{
	const double chty=0.75;  //平衡常数
	struct node{int son[2],f,size,v;}tr[100005];
	void init(){
		len=2;  root=1;
		tr[1].size=2;  tr[1].v=-INF;  tr[1].son[1]=2;
		tr[2].size=1;  tr[2].v=INF;   tr[2].f=1;
	}
	bool balance(int x) {
		double p=tr[x].size*chty;
		return p>=(double)tr[tr[x].son[0]].size&&p>=(double)tr[tr[x].son[1]].size;
	}
	void dfs(int x){//中序遍历
		if(!x)  return;
		dfs(tr[x].son[0]);
		stack[++top]=x;
		dfs(tr[x].son[1]);
	}
	int build(int l,int r){
		if(l>r)  return 0;
		int mid=(l+r)/2,x=stack[mid];
		tr[tr[x].son[0]=build(l,mid-1)].f=x;
		tr[tr[x].son[1]=build(mid+1,r)].f=x;
		tr[x].size=tr[tr[x].son[0]].size+tr[tr[x].son[1]].size+1;
		return x;
	}
	void rebuild(int x){
		top=0;  dfs(x);
		int fa=tr[x].f,which=(tr[fa].son[1]==x);
		int sonroot=build(1,top);
		tr[tr[fa].son[which]=sonroot].f=fa;
		if(x==root)  root=sonroot;
	}
	int find(int v){
		int now=root;
		while(now){
			if(v==tr[now].v)  return now;
			else now=tr[now].son[v>tr[now].v];
		}
	}
	void insert(int v){
		int now=root,p=++len; 
		tr[p].v=v;  tr[p].size=1;//新开结点
		while(1){
			tr[now].size++;
			int which=(v>=tr[now].v);//表示p在当前根的哪个子树内
			if(tr[now].son[which])  now=tr[now].son[which];  
			else {tr[tr[now].son[which]=p].f=now;  break;}
		}
		int id=0;
		for(int i=p;i;i=tr[i].f)  if(!balance(i))  id=i;//记录不平衡点
		if(id)  rebuild(id);//重构子树
	}
	void del(int x){
		if(tr[x].son[0]&&tr[x].son[1]){
			int p=tr[x].son[0];
			while(tr[p].son[1])  p=tr[p].son[1];
			tr[x].v=tr[p].v;  x=p;
		}
		int Son=(tr[x].son[0])?tr[x].son[0]:tr[x].son[1],which=(tr[tr[x].f].son[1]==x);
		tr[tr[tr[x].f].son[which]=Son].f=tr[x].f;
		for(int i=tr[x].f;i;i=tr[i].f)  tr[i].size--;
		if(x==root)  root=Son;
	}
	int rank(int v){
		int now=root,ans=0;
		while(now){
			if(tr[now].v<v)  {ans+=tr[tr[now].son[0]].size+1;  now=tr[now].son[1];}
			else now=tr[now].son[0];
		}
		return ans;
	}
	int kth(int x){
		int now=root;
		while(1){
			if(tr[tr[now].son[0]].size==x-1)  return now;
			else if(tr[tr[now].son[0]].size>=x)  now=tr[now].son[0];
			else x-=tr[tr[now].son[0]].size+1,now=tr[now].son[1];
		}
		return now;
	}
	int before(int v){
		int now=root,ans=-INF;
		while(now){
			if(tr[now].v<v)  ans=max(ans,tr[now].v),now=tr[now].son[1];
			else now=tr[now].son[0];
		}
		return ans;
	}
	int after(int v){
		int now=root,ans=INF;
		while(now){
			if(tr[now].v>v)  ans=min(ans,tr[now].v),now=tr[now].son[0];
			else now=tr[now].son[1];
		}
		return ans;
	}
}using namespace TiZuiYang_Tree;
int main(){
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    init();
    n=read();
    for(int i=1;i<=n;i++){
        int flag=read(),x=read();
        if(flag==1)  insert(x);
        if(flag==2)  del(find(x));
        if(flag==3)  printf("%d\n",rank(x));
        if(flag==4)  printf("%d\n",tr[kth(x+1)].v);
        if(flag==5)  printf("%d\n",before(x));
        if(flag==6)  printf("%d\n",after(x));
    }
    return 0;
}

　　

0/1Trie树

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
#include<bits/stdc++.h>
#define FILE "phs"
#define MAXN 100010*33
using namespace std;
const int chty=1e7;//整数偏差值
int n,cnt=1,size[MAXN],tr[MAXN][2];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int val,int f){
	val+=chty;  int now=1;
	for(int i=31;i>=0;--i){
		int which=((val>>i)&1);
		if(!tr[now][which])  tr[now][which]=++cnt;
		now=tr[now][which];  size[now]+=f;
	}
}
int rank(int val){
	val+=chty;  int now=1,ret=0;
	for(int i=31;i>=0;--i){
		int which=((val>>i)&1);
		if(which)  ret+=size[tr[now][0]];
		now=tr[now][which];
	}
	return ret+1;
}
int kth(int k){
	int now=1,ret=0;
	for(int i=31;i>=0;--i){
		if(k>size[tr[now][0]])  ret|=(1<<i),k-=size[tr[now][0]],now=tr[now][1];
		else now=tr[now][0];
	}
	return ret-chty;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i){
		int opt=read(),x=read();
		if(opt==1)  insert(x,1);
		else if(opt==2)  insert(x,-1);
		else if(opt==3)  printf("%d\n",rank(x));
		else if(opt==4)  printf("%d\n",kth(x));
		else if(opt==5)  printf("%d\n",kth(rank(x)-1));
		else if(opt==6)  printf("%d\n",kth(rank(x+1)));
	}
	return 0;
}

本文标题:【算法笔记】普通平衡树的实现

文章作者:chty

发布时间:2018年07月09日 - 20时17分

最后更新:2018年12月10日 - 17时03分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. 时空复杂度对比
  2. 2. Treap
  3. 3. Splay
  4. 4. 替罪羊树
  5. 5. 0/1Trie树
,