平衡树总结

BST:

概念:

BST(Binary Search Tree):二叉排序树或者是一棵空树,或者是具有下列性质的二叉树

  • 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;

  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;

  • 左、右子树也分别为二叉排序树。

应用:

在BST上可以进行这样的操作:

  1. 插入 \(x\)
  2. 删除 \(x\) 数(若有多个相同的数,因只删除一个)
  3. 查询 \(x\) 数的排名(排名定义为比当前数小的数的个数 +1+1 。若有多个相同的数,因输出最小的排名)
  4. 查询排名为 $ x$ 的数
  5. \(x\) 的前驱(前驱定义为小于 \(x\),且最大的数)
  6. \(x\) 的后继(后继定义为大于 \(x\),且最小的数)

实现:

(1.2操作略,s为子树大小)

3.求排名

1
2
3
4
5
6
7
8
int rank(int x,node* o=root)
{
if (!o) return INT_MAX;
int s=o->ch[0]?o->ch[0]->s:0;
if (o->v==x) return s+1;
if (o->v>x) return rank(x,o->ch[0]);
if (o->v<x) return rank(x,o->ch[1])+s+o->cnt;
}

4.求第k大

1
2
3
4
5
6
7
8
int kth(int k,node* o=root)
{
if (!o) return INT_MIN;
int s=o->ch[0]?o->ch[0]->s:0;
if (k>s && k<=s+o->cnt) return o->v;
if (k<=s) return kth(k,o->ch[0]);
return kth(k-s-o->cnt,o->ch[1]);
}

5.求前驱

1
2
3
4
5
6
7
8
//全局变量prec
void pre(int x,node* o=root)
{
if (!o) return;
if (o->v>prec && o->v<x) prec=o->v;
if (o->v>=x) pre(x,o->ch[0]);
else pre(x,o->ch[1]);
}

6.求后继

1
2
3
4
5
6
7
8
//全局变量succ
void suc(int x,node* o=root)
{
if (!o) return;
if (o->v<succ && o->v>x) succ=o->v;
if (o->v<=x) suc(x,o->ch[1]);
else suc(x,o->ch[0]);
}

平衡树

随机数据下,树期望高度为\(O(\log n)\)。所以,当树平衡时,所有这些操作时间都为\(O(\log n)\)。但树不一定平衡:按递增或递减顺序插入元素,树就会退化成一条链。在实际应用中,树几乎不会非常平衡。所以,朴素BST表现不佳。

易知,元素相同的BST可能有多种形态(朴素BST的形态与插入顺序有关)。我们我们采用一些方式来使BST的形态发生变化,但仍然为合法BST。这样树就变得平衡。

常见的BST有Splay,Treap,替罪羊树,红黑树,SBT等。

还有权值线段树、01trie、跳表等

大多数BST基于旋转操作。

旋转:

令一个节点换到它的父亲位置上。为了维护BST性质,节点的子节点的位置也会跟着发生变化。 (这里原来有图片,但是挂了)

令x为被旋转节点,y为其父亲,则:

  1. x变到原来y的位置

  2. y与x的位置关系与原来x与y的位置关系相反(如:x为y的左儿子,则后来y为x的右儿子)

  3. y非x的儿子不变,x的与x.y共线的儿子不变

  4. 原来x位置的节点变成了x的与x.y不共线的儿子

代码实现大概是这个样子(建议假设x是左儿子来理解,此时k==0):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//数组版:
inline void rotate(int x)
{//把x旋转到爸爸的位置
int y=f[x],z=f[y],k=(c[y][1]==x),w=c[x][!k];//k是x相对y的位置,w是x的不与x.y共线的儿子
c[z][c[z][1]==y]=x;//x变到原来y的位置
c[x][!k]=y;//x为y的左儿子,则后来y为x的右儿子
c[y][k]=w;//原来x位置的节点变成了x的与xy不共线的儿子
if(w)f[w]=y;//更新父亲,下同
f[y]=x;f[x]=z;
pushup(y);pushup(x);//只有x.y的子树信息发生改变
}
//指针版:
void rotate(node* &o,int d)
{//o为根,d=0表示右儿子左旋,d=1表示左儿子右旋。此版本未维护父亲指针。
node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->pushup();
k->pushup();
o=k;
}

数组和指针操作明显不同是因为我学习时抄的模板不是一个人写的

Treap

  • Treap=Tree+Heap

treap的每个节点有一个随机的优先级。对于键值而言,它是BST;对于优先级而言,它是堆(即,每棵子树中,根的优先级总是最大的)。因为优先级随机,所以树期望平衡。虽然基于随机,但不容易被卡掉,跑得也很快。

我采用刘汝佳式的指针写法,节点定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node
{
int v,cnt,rank,s;//cnt是重复元素个数,rank为优先级,s为子树大小。
node *ch[2];
node(int v):v(v),cnt(1),s(1),rank(rand()){ch[0]=ch[1]=0;}
void pushup()
{
s=cnt;
if (ch[0]) s+=ch[0]->s;
if (ch[1]) s+=ch[1]->s;
}
int cmp(int x)
{
if (x==v) return -1;
return v<x;
}
}*root;

insert

insert操作基本思想为dfs找到新节点应该在的位置并新建该节点,然后回溯判断是否违反堆性质并通过旋转维护堆性质。(注意对重复元素的处理)

1
2
3
4
5
6
7
8
9
void insert(node* &o,int v)
{
if (!o) {o=new node(v);return;}
int d=o->cmp(v);
if (d==-1) {++o->cnt;++o->s;return;}
insert(o->ch[d],v);
if (o->ch[d]->rank>o->rank) rotate(o,d^1);
o->pushup();
}

remove

当要删除的节点只有一个儿子时,删除操作很简单:直接用这个儿子代替它即可。remove操作正是基于这样的理念:将要删除的节点向下转到有至少一棵子树为空,然后删除。若有子树非空,则用非空的儿子代替它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void remove(node* &o,int v)
{
//if (!o) return;
int d=o->cmp(v);
if (d==-1)
{
if (o->cnt>1) {--o->cnt;--o->s;return;}
if (!(o->ch[0])) {node* k=o;o=o->ch[1];delete k;}
else if (!(o->ch[1])) {node* k=o;o=o->ch[0];delete k;}
else
{
int d2=o->ch[0]->rank>o->ch[1]->rank;
rotate(o,d2);
remove(o->ch[d2],v);
}
}
else remove(o->ch[d],v);
if (o) o->pushup();
}

完整实现如下:

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<ctime>
struct node
{
int v,cnt,rank,s;
node *ch[2];
node(int v):v(v),cnt(1),s(1),rank(rand()){ch[0]=ch[1]=0;}
void pushup()
{
s=cnt;
if (ch[0]) s+=ch[0]->s;
if (ch[1]) s+=ch[1]->s;
}
int cmp(int x)
{
if (x==v) return -1;
return v<x;
}
}*root;
void rotate(node* &o,int d)
{
node* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o->pushup();
k->pushup();
o=k;
}
void insert(node* &o,int v)
{
if (!o) {o=new node(v);return;}
int d=o->cmp(v);
if (d==-1) {++o->cnt;++o->s;return;}
insert(o->ch[d],v);
if (o->ch[d]->rank>o->rank) rotate(o,d^1);
o->pushup();
}
void remove(node* &o,int v)
{
int d=o->cmp(v);
if (d==-1)
{
if (o->cnt>1) {--o->cnt;--o->s;return;}
if (!(o->ch[0])) {node* k=o;o=o->ch[1];delete k;}
else if (!(o->ch[1])) {node* k=o;o=o->ch[0];delete k;}
else
{
int d2=o->ch[0]->rank>o->ch[1]->rank;
rotate(o,d2);
remove(o->ch[d2],v);
}
}
else remove(o->ch[d],v);
if (o) o->pushup();
}
int rank(int x,node* o=root)
{
if (!o) return INT_MAX;
int s=o->ch[0]?o->ch[0]->s:0;
if (o->v==x) return s+1;
if (o->v>x) return rank(x,o->ch[0]);
if (o->v<x) return rank(x,o->ch[1])+s+o->cnt;
}
int kth(int k,node* o=root)
{
if (!o) return INT_MIN;
int s=o->ch[0]?o->ch[0]->s:0;
if (k>s && k<=s+o->cnt) return o->v;
if (k<=s) return kth(k,o->ch[0]);
return kth(k-s-o->cnt,o->ch[1]);
}
int prec,succ;
void pre(int x,node* o=root)
{
if (!o) return;
if (o->v>prec && o->v<x) prec=o->v;
if (o->v>=x) pre(x,o->ch[0]);
else pre(x,o->ch[1]);
}
void suc(int x,node* o=root)
{
if (!o) return;
if (o->v<succ && o->v>x) succ=o->v;
if (o->v<=x) suc(x,o->ch[1]);
else suc(x,o->ch[0]);
}
int main()
{
//freopen("phs.in","r",stdin);
//freopen("phs.out","w",stdout);
srand(time(0));
int n;
int opt,x;
scanf("%d",&n);
while (n--)
{
scanf("%d%d",&opt,&x);
switch (opt)
{
case 1:insert(root,x);break;
case 2:remove(root,x);break;
case 3:printf("%d\n",rank(x));break;
case 4:printf("%d\n",kth(x));break;
case 5:prec=INT_MIN;pre(x);printf("%d\n",prec);break;
case 6:succ=INT_MAX;suc(x);printf("%d\n",succ);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}