平衡树学习笔记
程序员文章站
2023-11-10 21:52:52
> 平 衡 树 学 习 笔 记 < 目录 ) 1 -- > 平衡树简介 ) 2 -- > 平衡树实现 | 1 = = > > 平衡树存储 平衡树存储： 1 struct node{ 2 int size,value,num,rand; 3 int son[2]; 4 }n[1000001]； siz ......
> 平 衡 树 学 习 笔 记 <
目录
) 1 -- > 平衡树简介
) 2 -- > 平衡树实现
| 1 = = > > 平衡树存储
平衡树存储：
1 struct node{
2 int size,value,num,rand;
3 int son[2];
4 }n[1000001]；
size就是节点的个数。
value是节点代表的权值。
权值相同的两个节点被视为一个，num记录折叠数量。
rand是随机数，用来维护平衡树。
son就是两个儿子。
平衡树size更新：
实际操作中，各个变量的值都是不断更新的，size也不例外。
函数体：
1 inline void pushup(int root){}
一个节点包括的节点个数用脚也能想到：左儿子size与右儿子size的和，加上这个节点折叠数量。
1 n[root].size = n[n[root].son[0]].size + n[n[root].son[1]].size + n[root].num;
完整的平衡树size更新代码：
1 inline void pushup(int root)
2 {
3 n[root].size = n[n[root].son[0]].size + n[n[root].son[1]].size + n[root].num;
4 }
平衡树插入：
学习完上面的内容，接下来的基本逼死人的操作插入与删除就很简单了：
由于treap = tree + heap
所以平衡树插入与二叉排序树插入差不多
函数体：
1 inline void add(int &root,int data){}
插入节点总会遇到各种增加码量的情况，需要我们一一判断：
[ 1 ]节点不存在
什么？？节点不存在？？杀了出题人！
当插入函数用在建树中，这种情况很常见。
没有节点，那我们就开垦一个节点。（水土流失，土地荒漠化请走开）
├ 节点总数加1
├ 新节点size为1
├ 新节点num为1
├ 权值为data
└ 生成rand
→→→崭新的节点！！（不要998，不要98，只要9.8！）
代码实现就是一个简单的模拟：
奇怪的行号 if(!root)
9 {
8 sum+=1;
7 root=sum;
6 n[root].size=1;
5 n[root].num=1;
4 n[root].value=data;
3 n[root].rand=rand();
2 return;
1 }
0 点火，起飞！！
[ 2 ]有一个权值为data的节点
那更简单了！！
1 if (n[root].value==data)
2 {
3 n[root].num+=1;
4 n[root].size+=1;
5 return;
6 }
[ 3 ]寻找子树满足情况一或情况二
去哪棵子树呢？？定义一个变量。
1 int d(data>n[root].value);
有了明确的方向，就应该坚持走下去：
1 add(n[root].son[d],data);
随机数判断，随机旋转：
1 if(n[root].rand<n[n[root].son[d]].rand) 2 rotate(root,d^1);
更新size：
1 pushup(root);
至此，插入操作基本完成。
完整平衡树插入代码：
1 inline void add(int &root,int data)
2 {
3 if (!root)
4 {
5 sum+=1;
6 root=sum;
7 n[root].size=1;
8 n[root].num=1;
9 n[root].value=data;
10 n[root].rand=rand();
11 return;
12 }
13 if (n[root].value==data)
14 {
15 n[root].num+=1;
16 n[root].size+=1;
17 return;
18 }
19 int d(data>n[root].value);
20 add(n[root].son[d],data);
21 if(n[root].rand<n[n[root].son[d]].rand)
22 rotate(root,d^1);
23 pushup(root);
24 }
平衡树旋转：
平衡树旋转不破坏平衡树的性质，也就是说
旋转前：a<b<c<d<e<f
旋转后：a<b<c<d<e<f
完整平衡树旋转代码：
1 inline void rotate(int &root,int way)
2 {
3 int copy=n[root].son[way^1];
4 n[root].son[way^1]=n[copy].son[way];
5 n[copy].son[way]=root;
6 pushup(root);pushup(copy);
7 root=copy;
8 }
1 inline void remove(int &root,int data)
2 {
3 if(!root) return;
4 if(data<n[root].value) remove(n[root].son[0],data);
5 else if(data>n[root].value) remove(n[root].son[1],data);
6 else
7 {
8 if((!n[root].son[0])&&(!n[root].son[1]))
9 {
10 n[root].num-=1,n[root].size-=1;
11 if(n[root].num==0) root=0;
12 }
13 else if(n[root].son[0]&&!n[root].son[1])
14 {
15 rotate(root,1);remove(n[root].son[1],data);
16 }
17 else if(!n[root].son[0]&&n[root].son[1])
18 {
19 rotate(root,0);remove(n[root].son[0],data);
20 }
21 else if(n[root].son[0]&&n[root].son[1])
22 {
23 int d=(n[n[root].son[0]].rand>n[n[root].son[1]].rand);
24 rotate(root,d);remove(n[root].son[d],data);
25 }
26 }
27 pushup(root);
28 }
1 inline int rank(int root,int data)
2 {
3 if(!root)
4 return 0;
5 if(n[root].value==data)
6 return n[n[root].son[0]].size+1;
7 if(n[root].value<data)
8 return n[n[root].son[0]].size+n[root].num+rank(n[root].son[1],data);
9 if(n[root].value>data)
10 return rank(n[root].son[0],data);
11 }
1 inline int find(int root,int data)
2 {
3 if(!root)
4 return 0;
5 if(n[n[root].son[0]].size>=data)
6 return find(n[root].son[0],data);
7 else if(n[n[root].son[0]].size+n[root].num<data)
8 return find(n[root].son[1],data-n[root].num-n[n[root].son[0]].size);
9 else
10 return n[root].value;
11 }
inline int maxmin(int __a,int __b,int __bool)
{
if(__bool) return max(__a,__b);
else return min(__a,__b);
}
inline int pan(int __a,int __b,int __bool)
{
if(__bool) return (__a>=__b?1:0);
else return (__a<=__b?1:0);
}
inline int findin(int root,int data,int way)
{
if(!root) return inf+way;
if(pan(n[root].value,data,way)) return findin(n[root].son[way^1],data,way);
else return maxmin(n[root].value,findin(n[root].son[way],data,way),way);
}
看道板子题：p3369
完整代码：
1 #include<bits/stdc++.h>
2 #define inf 2147483647
3 using namespace std;
4 int sum=0,tree_root=0;
5 struct node{
6 int size,value,num,rand;
7 int son[2];
8 }n[1000001];
9 inline int maxmin(int __a,int __b,int __bool)
10 {
11 if(__bool) return max(__a,__b);
12 else return min(__a,__b);
13 }
14 inline void pushup(int root){n[root].size=n[n[root].son[0]].size+n[n[root].son[1]].size+n[root].num;}
15 inline void rotate(int &root,int way)
16 {
17 int copy=n[root].son[way^1];
18 n[root].son[way^1]=n[copy].son[way];
19 n[copy].son[way]=root;
20 pushup(root);pushup(copy);
21 root=copy;
22 }
23 inline void add(int &root,int data)
24 {
25 if (!root)
26 {
27 sum+=1;
28 root=sum;
29 n[root].size=1;
30 n[root].num=1;
31 n[root].value=data;
32 n[root].rand=rand();
33 return;
34 }
35 if (n[root].value==data)
36 {
37 n[root].num+=1;
38 n[root].size+=1;
39 return;
40 }
41 int d(data>n[root].value);
42 add(n[root].son[d],data);
43 if(n[root].rand<n[n[root].son[d]].rand)
44 rotate(root,d^1);
45 pushup(root);
46 }
47 inline void remove(int &root,int data)
48 {
49 if(!root) return;
50 if(data<n[root].value) remove(n[root].son[0],data);
51 else if(data>n[root].value) remove(n[root].son[1],data);
52 else
53 {
54 if((!n[root].son[0])&&(!n[root].son[1]))
55 {
56 n[root].num-=1,n[root].size-=1;
57 if(n[root].num==0) root=0;
58 }
59 else if(n[root].son[0]&&!n[root].son[1])
60 {
61 rotate(root,1);remove(n[root].son[1],data);
62 }
63 else if(!n[root].son[0]&&n[root].son[1])
64 {
65 rotate(root,0);remove(n[root].son[0],data);
66 }
67 else if(n[root].son[0]&&n[root].son[1])
68 {
69 int d=(n[n[root].son[0]].rand>n[n[root].son[1]].rand);
70 rotate(root,d);remove(n[root].son[d],data);
71 }
72 }
73 pushup(root);
74 }
75 inline int rank(int root,int data)
76 {
77 if(!root)
78 return 0;
79 if(n[root].value==data)
80 return n[n[root].son[0]].size+1;
81 if(n[root].value<data)
82 return n[n[root].son[0]].size+n[root].num+rank(n[root].son[1],data);
83 if(n[root].value>data)
84 return rank(n[root].son[0],data);
85 }
86 inline int find(int root,int data)
87 {
88 if(!root)
89 return 0;
90 if(n[n[root].son[0]].size>=data)
91 return find(n[root].son[0],data);
92 else if(n[n[root].son[0]].size+n[root].num<data)
93 return find(n[root].son[1],data-n[root].num-n[n[root].son[0]].size);
94 else
95 return n[root].value;
96 }
97 inline int pan(int __a,int __b,int __bool)
98 {
99 if(__bool) return (__a>=__b?1:0);
100 else return (__a<=__b?1:0);
101 }
102 inline int findin(int root,int data,int way)
103 {
104 if(!root) return inf+way;
105 if(pan(n[root].value,data,way)) return findin(n[root].son[way^1],data,way);
106 else return maxmin(n[root].value,findin(n[root].son[way],data,way),way);
107 }
108 int main()
109 {
110 int n,opt,x;
111 scanf("%d",&n);
112 for(register int i=0;i<n;++i)
113 {
114 scanf("%d%d",&opt,&x);
115 if(opt==1) add(tree_root,x);
116 else if(opt==2) remove(tree_root,x);
117 else if(opt==3) printf("%d\n",rank(tree_root,x));
118 else if(opt==4) printf("%d\n",find(tree_root,x));
119 else if(opt==5) printf("%d\n",findin(tree_root,x,1));
120 else if(opt==6) printf("%d\n",findin(tree_root,x,0));
121 }
122 return 0;
123 }
个人比较喜欢压行（60行平衡树见过吗？？）
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #define inf 2147483647
5 using namespace std;
6 int sum=0,tree_root=0;
7 struct node{int size,value,num,rand,son[2];}n[500001];
8 inline int maxmin(int __a,int __b,int __bool){if(__bool) return max(__a,__b);else return min(__a,__b);}
9 inline void pushup(int root){n[root].size=n[n[root].son[0]].size+n[n[root].son[1]].size+n[root].num;}
10 inline void rotate(int &root,int way){
11 int copy=n[root].son[way^1];
12 n[root].son[way^1]=n[copy].son[way];n[copy].son[way]=root;
13 pushup(root);pushup(copy);root=copy;}
14 inline void add(int &root,int data){
15 if (!root){
16 sum+=1;root=sum;
17 n[root].size=1;n[root].num=1;n[root].value=data;n[root].rand=rand();
18 return;}
19 if(n[root].value==data){n[root].num+=1,n[root].size+=1;return;}
20 int d(data>n[root].value);add(n[root].son[d],data);
21 if(n[root].rand<n[n[root].son[d]].rand) rotate(root,d^1);
22 pushup(root);}
23 inline void remove(int &root,int data){
24 if(!root) return;
25 if(data<n[root].value) remove(n[root].son[0],data);
26 else if(data>n[root].value) remove(n[root].son[1],data);
27 else {
28 if((!n[root].son[0])&&(!n[root].son[1])){n[root].num-=1,n[root].size-=1; if(n[root].num==0) root=0;}
29 else if(n[root].son[0]&&!n[root].son[1]){rotate(root,1);remove(n[root].son[1],data);}
30 else if(!n[root].son[0]&&n[root].son[1]){rotate(root,0);remove(n[root].son[0],data);}
31 else if(n[root].son[0]&&n[root].son[1]){
32 int d=(n[n[root].son[0]].rand>n[n[root].son[1]].rand);
33 rotate(root,d);remove(n[root].son[d],data);}}
34 pushup(root);}
35 inline int rank(int root,int data){
36 if(!root) return 0;
37 if(n[root].value==data) return n[n[root].son[0]].size+1;
38 if(n[root].value<data) return n[n[root].son[0]].size+n[root].num+rank(n[root].son[1],data);
39 if(n[root].value>data) return rank(n[root].son[0],data);}
40 inline int find(int root,int data){
41 if(!root) return 0;
42 if(n[n[root].son[0]].size>=data) return find(n[root].son[0],data);
43 else if(n[n[root].son[0]].size+n[root].num<data) return find(n[root].son[1],data-n[root].num-n[n[root].son[0]].size);
44 else return n[root].value;}
45 inline int pan(int __a,int __b,int __bool){if(__bool) return (__a>=__b?1:0);else return (__a<=__b?1:0);}
46 inline int findin(int root,int data,int way){
47 if(!root) return inf+way;
48 if(pan(n[root].value,data,way)) return findin(n[root].son[way^1],data,way);
49 else return maxmin(n[root].value,findin(n[root].son[way],data,way),way);}
50 int main(){
51 int n,opt,x;
52 scanf("%d",&n);
53 for(register int i=0;i<n;++i){
54 scanf("%d%d",&opt,&x);
55 if(opt==1) add(tree_root,x);
56 else if(opt==2) remove(tree_root,x);
57 else if(opt==3) printf("%d\n",rank(tree_root,x));
58 else if(opt==4) printf("%d\n",find(tree_root,x));
59 else if(opt==5) printf("%d\n",findin(tree_root,x,1));
60 else if(opt==6) printf("%d\n",findin(tree_root,x,0));}return 0;}