平衡树

发表于 更新于 分类于 阅读次数： Changyan：

平衡树

欢迎来到二叉搜索树的世界，在这里，你将会见到：treap,红黑树，splay，sbt，AVL….

对于对二叉搜索树的操作，我们可以将其分成了：

  • 有旋转（AVL,Splay,红黑树）
  • 无旋转（替罪羊树，fhq Treap…）

下面进入本次的正题：平衡树Treap:

Treap

前置知识：

1.BST(Binary Search Tree)二叉搜索树

BST： 当前节点的左子树中的任何一个点的权值都是严格小于当前结点的权值，右子树反之

BST的中序遍历一定是一个有序序列

BST的本质：动态维护一个有序序列

2.Heap 堆（Treap使用的是大根堆的性质）

Heap，大根堆，即一颗所有根节点的权值大于所有其儿子节点的权值的数据结构.如图便是一个大根堆：

平衡树：

平衡树是一颗基于BST和Heap的数据结构

Treap解决的问题：

一颗随机的BST期望高度是logn，这样在进行插入和查询的时候的时间复杂度便是O(logn)级别。但是，如果随意的插入，二叉搜索树有可能退化成链表，其各种操作时间复杂度也就会退化成O(n)：：

但是我们期望中的BST应该是：

因此，就诞生出了平衡树：对于每个点，我们不仅在权值上维护BST的性质，我们还维护一个val值，这个值是由随机生成的(越随机越好)，然后我们通过一些奇奇怪怪的操作来一直维护这一棵二叉搜索树维持第二张图的性质，即之后会提到的左旋和右旋。

平衡树的用途：在只考虑前四种用途的情况下，我们可以借助STL中的set容器来代替平衡树（实际上set就是一颗红黑树）

1.插入：递归找到位置并插入 ___STL set insert()

2.删除：将删除的位置变成叶子节点之后删除 __STL erase

3.找前驱/后继：中序遍历中的前一个位置和后一个位置____STL_ set ++

1
2
3
4
5
6
7
8
//找前驱伪代码
if(p->left):
    p=p->left
    while(p->right) p=p->right
    return p;
else:
    while(p->father>p) p=p->father
    return p;

4.找最大值和最小值：STL_set___/begin()___/end()-1

5.求某一个值得排名

6.求排名是k的数是哪个

7.比某个数小的最大值

8.比某个数大的最小值

下面我们边看代码，边来解析Treap的实现原理

附加例题：https://www.luogu.com.cn/problem/P3369

Treap的存储
1
2
3
4
5
6
Node{
	int l,r;
	int key,val; //key是二叉搜索树内用来排序的关键字，val是大根堆内的值，即排序优先级
    int cnt,size; //cnt存储的是当前权值的数的个数，size是以当前节点为根节点的树中数的个数
} tr[N];
int root,idx;  //root存储Treap的根节点，idx是内存分配的编号；
Treap的维护值的更新
1
2
3
void push_up(int &p){ //很类似与线段树，这个操作就是对于额外维护的信息，用子节点来更新父节点
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt; //我们额外维护的信息是树的大小，对于p节点的树的大小，等于左儿子为根的子树的大小+右儿子为根的子树的大小+p节点处的相同数值的数的个数
}
Treap的创建节点
1
2
3
4
5
6
7
void get_node(int key){  //创建一个权值为key的节点
    int u=++idx; //申请到一个内存的编号,便是我们要创建的这一个节点
    tr[u].key=key;
 	tr[u].val=rand(); //此处val越随机越好，因为这样可以保证不退化
    tr[u].cnt=tr[u].size=1; //此时当前节点的大小和节点形成子树的大小都是1
    return u; //最后再返回对应的内存池分配编号
}
Treap的左旋与右旋😇

这张图将会贯穿始终.

右旋操作即将根节点x的左儿子y旋转到根节点，然后y的右儿子“掉”到原来根节点x的左儿子上。我们可以在一系列操作在之后，加入y的val值大于x的val值了，那么为了维护val值满足大根堆的性质，我们可以对整棵树进行右旋操作

1
2
3
4
5
6
7
void zig(int &p){  //对p节点进行右旋操作
    int q=tr[p].l;  //找到左儿子，即左边这幅图中我们通过x找到y
    tr[p].l=tr[q].r; //将x的左儿子变成z，如图右边右旋之后z滑落到x的左边
    tr[q].r=p;  //右旋之后根节点y的右儿子是x
    p=q;  //右旋之后，q成为新的根节点
    push_up(tr[p].l),push_up(p); //由于x的形态还有y的形态都发生了变化，因此要分别对这两个点进行更新 
}

左旋操作：左旋操作即从图中的右边变成左边：

1
2
3
4
5
6
7
void zag(int &p){
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    push_up(tr[p].l),push_up(p);
}

一开始的建树：此时用了一个小小的trick，为了保证不出现边界问题，我们将原树先用负无穷和正无穷来建好框架，后面再往里面添加和删除即可：

1
2
3
4
5
6
7
8
void build(){
    get_node(-INF),get_node(INF);  
    root=1;
    tr[root].r=2;
    push_up(root);

    if(tr[1].val<tr[2].val) zag(root); //be careful!!!!!!!由于是随机生成的数，所以有可能需要左旋
}
插入操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//insert a value in position p 
void insert(int &p,int key){  //在p节点的子树中要插入权值为key的节点
    if(!p)  p=get_node(key);  //如果没有这个节点，就申请一块新的节点进行插入
  	else if(tr[p].key==key) tr[p].cnt++; //如果当前节点的值正好相等，就这个值的个数++
    else if(tr[p].key>key){
        insert(tr[p].l,key);  //BST的性质，比当前是数小，就在左子树中插入
        if(tr[tr[p].l].val>tr[p].val) zig(p);  //如果插入之后左子树的val值大，就右旋维护Treap
    }
    else{  //否则在右子树插入，做同样的维护
        insert(tr[p].r,key);
        if(tr[tr[p].r].val<tr[p].val) zag(p);
    }
    push_up(p);  //由于insert操作使得树的形态发生了变化，所以需要通过变化的子节点来更新一下父节点
}
删除操作,还是参考这张图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void remove(int &p,int key){
    if(!p) return ; //由于此数不在Treap中，所以无需操作
    if(tr[p].key==key){
        if(tr[p].cnt>1) tr[p].cnt--;  //说明有多个相同的值，值的计数-1即可
        else if(tr[p].l||tr[p].r){  //如果不是叶子节点，就需要通过旋转把根节点旋转到叶子节点上进行删除
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val){   
                zig(p);
                remove(tr[p].r,key);
            }
            else{
                zag(p);
                remove(tr[p].l,key);
            }            
        }
        else p=0;   //说明是叶子节点，直接删除即可
    }
    else if(tr[p].key>key) 
        remove(tr[p].l,key); //比根节点小，就在左子树中找到并删除
    else 
        remove(tr[p].r,key); //同理，在右子树中找到并删除
    push_up(p);  //最后再更新一遍父节点
}

对于下面的操作，只要明白Node中维护的cnt和size的含义就可以轻松写出来了

给定一个值来查找这个值在BST中序遍历中的排名：
1
2
3
4
5
6
7
//get rank by given value
int get_rank_by_key(int p,int key){
    if(!p) return 0; //the value not exists
    else if(key==tr[p].key) return tr[tr[p].l].size+1;  
    else if(key<tr[p].key) return get_rank_by_key(tr[p].l,key);
    else return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
给定一个中序遍历的排名，来求对应值：
1
2
3
4
5
6
7
//get value by given rank
int get_key_by_rank(int p,int rank){
    if(!p) return INF;
    else if(rank<=tr[tr[p].l].size) return get_key_by_rank(tr[p].l,rank);
    else if(rank<=tr[tr[p].l].size+tr[p].cnt) return tr[p].key;
    else return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
求在Treap中，比给定数大的最小的数
1
2
3
4
5
6
//get the greatest number less than key
int get_pre(int p,int key){
    if(!p) return -INF;
    else if(key<=tr[p].key) return get_pre(tr[p].l,key);
    else return max(tr[p].key,get_pre(tr[p].r,key));
}
在Treap中，求比给定数小的最大的数
1
2
3
4
5
6
//get the least number greater than key
int get_next(int p,int key){
    if(!p) return INF;
    else if(key<tr[p].key) return min(tr[p].key,get_next(tr[p].l,key));
    else return get_next(tr[p].r,key);
}

嗯。。。这里就结束了。这应该是目前为止遇到的第三难写的数据结构了…

附上例题的AC代码： （150+行，稍有不注意，眼角两行泪。一杯茶一包烟，百行代码调一天）

注意：因为一开始初始化了两个无穷节点，所以在查排名和获取排名的时候应该减去。

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
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define MAXN 100010
using namespace std;

const int INF=1e9+7;

struct Node{
    int l,r;  //左右指针指向左右儿子分配的内存编号
    int key,val; //记录权值和维护堆性质的val
    int cnt,size;  //当前数的个数，当前子树中数的个数
} tr[MAXN];
int root,idx=0;
int n;

//子节点更新父节点信息
void push_up(int &u){
    tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+tr[u].cnt;
}

//右旋
void zig(int &p){
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    push_up(tr[p].r),push_up(p);
}

//左旋
void zag(int &p){
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    push_up(tr[p].l),push_up(p);
}

//create new point
int get_node(int key){
    int u=++idx;  //get new area
    tr[u].key=key;
    tr[u].val=rand();
    tr[u].size=tr[u].cnt=1;
    return u;
}

//build the prime of the tree
void build(){
    get_node(-INF),get_node(INF);
    root=1;
    tr[root].r=2;
    push_up(root);
    
    if(tr[1].val<tr[2].val) zag(root); //be careful!!!!!!!
}

//insert a value in position p 
void insert(int &p,int key){
    if(!p)  p=get_node(key);
    else if(tr[p].key==key) tr[p].cnt++;
    else if(tr[p].key>key){ //insert into the left
        insert(tr[p].l,key);
        
        if(tr[tr[p].l].val>tr[p].val) zig(p);
    }
    else{
        insert(tr[p].r,key);
        
        if(tr[tr[p].r].val>tr[p].val) zag(p);
    }
    push_up(p);
}

//remove a value
void remove(int &p,int key){
    if(!p) return ;
    else if(tr[p].key==key){
        if(tr[p].cnt>1) tr[p].cnt--;
        else if(tr[p].l||tr[p].r){  //if not the leaf Node
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val){   //if the left son s bigger 
                zig(p);
                remove(tr[p].r,key);
            }    
            else{ 
                zag(p);
                remove(tr[p].l,key);
            }
        }
        else p=0;
    }
    else if(tr[p].key>key)
        remove(tr[p].l,key);
    else
        remove(tr[p].r,key);
    push_up(p);
}

//get rank by given value
int get_rank_by_key(int p,int key){
    if(!p) return 0; //the value not exists
    else if(key==tr[p].key) return tr[tr[p].l].size+1;
    else if(key<tr[p].key) return get_rank_by_key(tr[p].l,key);
    else return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}

//get value by given rank
int get_key_by_rank(int p,int rank){
    if(!p) return INF;
    else if(rank<=tr[tr[p].l].size) return get_key_by_rank(tr[p].l,rank);
    else if(rank<=tr[tr[p].l].size+tr[p].cnt) return tr[p].key;
    else return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}

//get the greatest number less than key
int get_pre(int p,int key){
    if(!p) return -INF;
    else if(key<=tr[p].key) return get_pre(tr[p].l,key);
    else return max(tr[p].key,get_pre(tr[p].r,key));
}

//get the least number greater than key
int get_next(int p,int key){
    if(!p) return INF;
    else if(key<tr[p].key) return min(tr[p].key,get_next(tr[p].l,key));
    else return get_next(tr[p].r,key);
}

int main(){
    build();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==1) insert(root,b);
        else if(a==2) remove(root,b);
        else if(a==3) printf("%d\n",get_rank_by_key(root,b)-1);
        else if(a==4) printf("%d\n",get_key_by_rank(root,b+1));
        else if(a==5) printf("%d\n",get_pre(root,b));
        else if(a==6) printf("%d\n",get_next(root,b));
    }
    return 0;
}

推荐一个超赞的数据结构可视化网站：https://visualgo.net/zh