平衡树学习笔记
2019-11-28 16:01:21来源:博客园 阅读 ()
> 平 衡 树 学 习 笔 记 <
目录
) 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;}压行平衡树
原文链接:https://www.cnblogs.com/zythonc/p/11952589.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:线段树
- 如何0基础学习C/C++? 2020-06-06
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- vtk学习记录(三)——初识vtkRenderer 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- C++基础 学习笔记六:复合类型之数组 2020-04-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash