平衡树学习笔记

2019-11-28 16:01:21来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

> 平 衡 树 学 习 笔 记 <


 

目录

  ) 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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++ 基础语法 快速复习笔记(1)

下一篇:线段树