欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

平衡树学习笔记

程序员文章站 2022-06-20 08:31:41
> 平 衡 树 学 习 笔 记 < 目录 ) 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;}