平衡二叉树（Treap） - 老官童鞋gogo的博客

分类

2453 字

12 分钟

平衡二叉树（Treap）

2024-09-29

程设计科

/

算法与数据结构

数据结构

二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。

Treap简介#

特点与作用#

Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不同，创建的二叉搜索树也不同，在最坏的情况下（比如只有左子树或者只有右子树），会退化为线性。

若一个二叉搜索树插入的节点顺序时随机的，则得到的二叉搜索树在大多情况下是平衡的，即使存在一些极端的情况但这种情况发生的概率很小，因此以随机顺序创建的二叉搜索树，其期望高度为 $O(\log n)$ 。可以将输入的数据随机打乱，再创建二叉搜索树，但我们有时并不能事前得知所有待插入的节点，而Treap可以解决该问题。

基本结构#

Treap是一种平衡二叉树，它给每个节点都附加了一个随机数，使其满足堆的性质，而节点的值又满足二叉搜索树的有序性，其基本操作的期望时间复杂度为 $O(\log n)$ 相对于其他平衡二叉搜索树，Treap的特点是实现简单，而且可以基本实现随机平衡。

在Treap构建过程中，插入节点时会给每个节点都附加一个随机数作为优先级，该优先级满足堆的性质（最大堆或者最小堆均可，本文以最大堆为例，根的优先级大于左右子树的节点），数值满足二叉搜索树的性质（中序有序性，左子树大于根，右子树小于根）。

Treap操作#

左旋和右旋#

Treap需要两种操作：左旋和右旋。

右旋（ $zig$ ）：节点 $p$ 右旋时，会携带自己的右子树，向右旋转到 $q$ 的右子树位置， $q$ 的右子树被抛弃，此时 $p$ 右旋后左子树正好空闲，将 $q$ 的右子树放在 $p$ 的左子树位置，旋转后的树根为 $q$ 。
左旋（ $zag$ ）：节点 $p$ 左旋时，会携带自己的左子树，向左旋转到 $q$ 的左子树位置， $q$ 的左子树被抛弃，此时 $p$ 左旋后右子树正好空闲，将 $q$ 的左子树放在 $p$ 的右子树位置，旋转后的树根为 $q$ 。

所以，无论是左旋还是右旋，旋转后总有一棵子树被抛弃，一个指针空闲，正好配对。

右旋代码：

1
inline void zig(reg int &p)
2
{
3
  reg int q=tree[p].lc;
4
  tree[p].lc=tree[q].rc;
5
  tree[q].rc=p;
6
  tree[q].size=tree[p].size;
7
  Update(p);
8
  p=q;
9
  return;
10
}

左旋代码：

1
inline void zag(reg int &p)
2
{
3
  reg int q=tree[p].rc;
4
  tree[p].rc=tree[q].lc;
5
  tree[q].lc=p;
6
  tree[q].size=tree[p].size;
7
  Update(p);
8
  p=q;
9
  return;
10
}

左旋右旋后，节点所对应的子树大小也会发生变化，需要更新每个节点更新后所对应的子树个数

更新子树大小代码：

1
inline void Update(reg int p)
2
{
3
  tree[p].size=tree[tree[p].lc].size+tree[tree[p].rc].size+tree[p].num;
4
  return;
5
}

插入#

Treap的插入操作与二叉搜索树一样，首先根据有序性找到插入的位置，然后创建节点插入该位置。其中每个点都会有一个随机值，该值为优先级，会自下向上检查这一棵树是否满足堆的性质，若不满足会进行左旋或者右旋的操作。

新建节点代码：

1
inline int New(reg int val)
2
{
3
  tree[++cnt].val=val;
4
  tree[cnt].pri=rand();
5
  tree[cnt].num=tree[cnt].size=1;
6
  tree[cnt].rc=tree[cnt].lc=0;
7
  return cnt;
8
}

当我们要插入一个数时，从根节点 $rt$ 出发，如果节点 $p$ 为空，就直接创建新节点，将元素 $val$ 作为根节点，并赋值一个随机数作为优先级，否则会进行下面三种判断：

如果 $val$ 的值小于当前节点 $p$ 的值，就在它的左子树递归插入。回溯的时候根据优先级进行左旋或者右旋。
如果 $val$ 的值大于当前节点 $p$ 的值，就在它的右子树递归插入。回溯的时候根据优先级进行左旋或者右旋。
如果 $val$ 的值等于当前节点 $p$ 的值，就将当前节点的 $num$ 的值加一，在这里 $num$ 表示相同元素的数量。如果只要保留不重复的元素就什么也不做。

插入代码：

1
inline void Insert(reg int &p,reg int val)
2
{
3
  if(!p)
4
  {
5
    p=New(val);
6
    return;
7
  }
8
  tree[p].size++;
9
  if(val==tree[p].val)
10
  {
11
    tree[p].num++;
12
    return;
13
  }
14
  else if(val<tree[p].val)
15
  {
16
    Insert(tree[p].lc,val);
17
    if(tree[p].pri<tree[tree[p].lc].pri)
18
      zig(p);
19
  }
20
  else
21
  {
22
    Insert(tree[p].rc,val);
23
    if(tree[p].pri<tree[tree[p].rc].pri)
24
      zag(p);
25
  }
26
  return;
27
}

删除#

首先找到删除的节点，将该节点向优先级大的子节点旋转，一直旋转到叶子，最后删除叶子。

具体来说，我们要删除一个元素 $val$ ，首先从根节点开始，会出现下面的三种情况：

如果 $val$ 的值小于当前节点 $p$ 的值，则在 $p$ 的左子树中递归删除。
如果 $val$ 的值大于当前节点 $p$ 的值，则在 $p$ 的右子树中递归删除。
如果 $val$ $v a l$ 的值等与当前节点 $p$ $p$ 的值，则：
1. 若当前节点 $p$ 只有左子树或者是右子树，就将当前节点 $p$ 赋值为其儿子的状态，。
2. 若当前节点 $p$ 左儿子的优先级大于右儿子的优先级，则 $p$ 左旋。继续在右子树中递归删除。
3. 若当前节点 $p$ 左儿子的优先级小于右儿子的优先级，则 $p$ 右旋。继续在左子树中递归删除。

代码：

1
inline void Delete(reg int &p,reg int val)
2
{
3
  if(!p)
4
    return;
5
  tree[p].size--;
6
  if(val==tree[p].val)
7
  {
8
    if(tree[p].num>1)
9
    {
10
      tree[p].num--;
11
      return;
12
    }
13
    if(!tree[p].lc||!tree[p].rc)
14
      p=tree[p].lc+tree[p].rc;
15
    else if(tree[tree[p].lc].pri>tree[tree[p].rc].pri)
16
    {
17
      zig(p);
18
      Delete(tree[p].rc,val);
19
    }
20
    else
21
    {
22
      zag(p);
23
      Delete(tree[p].lc,val);
24
    }
25
    return;
26
  }
27
  if(val<tree[p].val)
28
    Delete(tree[p].lc,val);
29
  else
30
    Delete(tree[p].rc,val);
31
  return;
32
}

前驱与后继#

首先理解什么是前驱、后继：

前驱结点：节点 $val$ 值小于该节点 $val$ 值并且值最大的节点
后继节点：节点 $val$ 值大于该节点 $val$ 值并且值最小的节点

在Treap中求一个节点 $val$ 的前驱时，首先从树根开始，若当前节点的值小于 $val$ ，则用变量 $res$ 暂存该节点的值，在当前节点的右子树中寻找，否则在当前节点的左子树中寻找，直到当前节点为空，范围 $res$ ，即为 $val$ 的前驱。

在Treap中求一个节点 $val$ 的后继时，首先从树根开始，若当前节点的值大于 $val$ ，则用变量 $res$ 暂存该节点的值，在当前节点的左子树中寻找，否则在当前节点的右子树中寻找，直到当前节点为空，返回 $res$ ，即为 $val$ 的后继。

求前驱代码：

1
inline int GetPre(reg int val)
2
{
3
  reg int p=rt;
4
  reg int res=0;
5
  while(p)
6
  {
7
    if(tree[p].val<val)
8
    {
9
      res=tree[p].val;
10
      p=tree[p].rc;
11
    }
12
    else
13
      p=tree[p].lc;
14
  }
15
  return res;
16
}

求后继代码：

1
inline int GetNext(reg int val)
2
{
3
  reg int p=rt;
4
  reg int res=0;
5
  while(p)
6
  {
7
    if(tree[p].val>val)
8
    {
9
      res=tree[p].val;
10
      p=tree[p].lc;
11
    }
12
    else
13
      p=tree[p].rc;
14
  }
15
  return res;
16
}

根据 $val$ 查找排名#

从树根出发，如果当前要查找的 $val$ 值大于当前节点 $p$ 的值，就向右递归搜索，将答案加上当前节点 $p$ 左儿子的子树大小与当前节点 $p$ 的元素个数。如果当前要查找的 $val$ 值小于当前节点 $p$ 的值，就向左递归搜索。如果两个值相等，就返回当前节点 $p$ 的左儿子子树大小 $+1$ 。

代码：

1
inline int GetRankByVal(reg int p,reg int val)
2
{
3
  if(!p)
4
    return 1;
5
  if(tree[p].val==val)
6
    return tree[tree[p].lc].size+1;
7
  if(val<tree[p].val)
8
    return GetRankByVal(tree[p].lc,val);
9
  else
10
    return GetRankByVal(tree[p].rc,val)+tree[tree[p].lc].size+tree[p].num;
11

12
}

根据排名查找 $val$ 值#

从树根出发，如果当前要查找的排名 $rank$ 小于当前节点 $p$ 左子树大小，就向左子树递归搜索。如果当前要查找的排名 $rank$ 小于等于当前节点p的左子树的大小与当前节点 $p$ 的元素数量之和，就返回当前节点的 $val$ 值。如果当前要查找的排名 $rank$ 大于当前节点 $p$ 的左子树大小与当前节点 $p$ 的元素数量之和，就向右子树递归搜索，此时搜索的 $rank$ 值要减去当前节点 $p$ 的左子树大小和当前节点 $p$ 的元素数量和。

代码：

1
inline int GetValByRank(reg int p,reg int rank)
2
{
3
  if(!p)
4
    return 0;
5
  if(tree[tree[p].lc].size>=rank)
6
    return GetValByRank(tree[p].lc,rank);
7
  if(tree[tree[p].lc].size+tree[p].num>=rank)
8
    return tree[p].val;
9
  return GetValByRank(tree[p].rc,rank-tree[tree[p].lc].size-tree[p].num);
10
}

代码#

来源：洛谷：P3369 【模板】普通平衡树、洛谷：P6136 【模板】普通平衡树（数据加强版）

1
#include<iostream>
2
#include<cstdio>
3
#include<cstdlib>
4
#include<algorithm>
5
#include<cstring>
6
#include<cmath>
7
#include<vector>
8
#include<queue>
9
#include<map>
10
#include<set>
11
#include<ctime>
12
using namespace std;
13
#define LL long long
14
#define uLL unsigned long long
15
#define reg register
16
#define PI acos(-1.0)
17
#define pb(x) push_back(x)
18
#define mp(a,b) make_pair(a,b)
19
#define fi first
20
#define se second
21
#define pr(x) cerr<<#x<<"="<<(x)<<endl
22
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
23
#define inf 100000000
24
#define N 1000
25
#define M 4000001
26
template<class T>inline void read(T &x)
27
{
28
    x=0;register char c=getchar();register bool f=0;
29
    while(!isdigit(c))f^=c=='-',c=getchar();
30
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
31
    if(f)x=-x;
32
}
33
template<class T>inline void print(T x)
34
{
35
    if(x<0)putchar('-'),x=-x;
36
    if(x>9)print(x/10);
37
    putchar('0'+x%10);
38
}
39
struct Node
40
{
41
  int lc,rc,val,pri,num,size;
42
}tree[M];
43
int cnt,rt,n,m,Last,ans;
44
inline int New(reg int val)
45
{
46
  tree[++cnt].val=val;
47
  tree[cnt].pri=rand();
48
  tree[cnt].num=tree[cnt].size=1;
49
  tree[cnt].rc=tree[cnt].lc=0;
50
  return cnt;
51
}
52
inline void Update(reg int p)
53
{
54
  tree[p].size=tree[tree[p].lc].size+tree[tree[p].rc].size+tree[p].num;
55
  return;
56
}
57
inline void zig(reg int &p)
58
{
59
  reg int q=tree[p].lc;
60
  tree[p].lc=tree[q].rc;
61
  tree[q].rc=p;
62
  tree[q].size=tree[p].size;
63
  Update(p);
64
  p=q;
65
  return;
66
}
67
inline void zag(reg int &p)
68
{
69
  reg int q=tree[p].rc;
70
  tree[p].rc=tree[q].lc;
71
  tree[q].lc=p;
72
  tree[q].size=tree[p].size;
73
  Update(p);
74
  p=q;
75
  return;
76
}
77
inline void Insert(reg int &p,reg int val)
78
{
79
  if(!p)
80
  {
81
    p=New(val);
82
    return;
83
  }
84
  tree[p].size++;
85
  if(val==tree[p].val)
86
  {
87
    tree[p].num++;
88
    return;
89
  }
90
  else if(val<tree[p].val)
91
  {
92
    Insert(tree[p].lc,val);
93
    if(tree[p].pri<tree[tree[p].lc].pri)
94
      zig(p);
95
  }
96
  else
97
  {
98
    Insert(tree[p].rc,val);
99
    if(tree[p].pri<tree[tree[p].rc].pri)
100
      zag(p);
101
  }
102
  return;
103
}
104
inline void Delete(reg int &p,reg int val)
105
{
106
  if(!p)
107
    return;
108
  tree[p].size--;
109
  if(val==tree[p].val)
110
  {
111
    if(tree[p].num>1)
112
    {
113
      tree[p].num--;
114
      return;
115
    }
116
    if(!tree[p].lc||!tree[p].rc)
117
      p=tree[p].lc+tree[p].rc;
118
    else if(tree[tree[p].lc].pri>tree[tree[p].rc].pri)
119
    {
120
      zig(p);
121
      Delete(tree[p].rc,val);
122
    }
123
    else
124
    {
125
      zag(p);
126
      Delete(tree[p].lc,val);
127
    }
128
    return;
129
  }
130
  if(val<tree[p].val)
131
    Delete(tree[p].lc,val);
132
  else
133
    Delete(tree[p].rc,val);
134
  return;
135
}
136
inline int GetPre(reg int val)
137
{
138
  reg int p=rt;
139
  reg int res=0;
140
  while(p)
141
  {
142
    if(tree[p].val<val)
143
    {
144
      res=tree[p].val;
145
      p=tree[p].rc;
146
    }
147
    else
148
      p=tree[p].lc;
149
  }
150
  return res;
151
}
152
inline int GetNext(reg int val)
153
{
154
  reg int p=rt;
155
  reg int res=0;
156
  while(p)
157
  {
158
    if(tree[p].val>val)
159
    {
160
      res=tree[p].val;
161
      p=tree[p].lc;
162
    }
163
    else
164
      p=tree[p].rc;
165
  }
166
  return res;
167
}
168
inline int GetRankByVal(reg int p,reg int val)
169
{
170
  if(!p)
171
    return 1;
172
  if(tree[p].val==val)
173
    return tree[tree[p].lc].size+1;
174
  if(val<tree[p].val)
175
    return GetRankByVal(tree[p].lc,val);
176
  else
177
    return GetRankByVal(tree[p].rc,val)+tree[tree[p].lc].size+tree[p].num;
178

179
}
180
inline int GetValByRank(reg int p,reg int rank)
181
{
182
  if(!p)
183
    return 0;
184
  if(tree[tree[p].lc].size>=rank)
185
    return GetValByRank(tree[p].lc,rank);
186
  if(tree[tree[p].lc].size+tree[p].num>=rank)
187
    return tree[p].val;
188
  return GetValByRank(tree[p].rc,rank-tree[tree[p].lc].size-tree[p].num);
189
}
190
int main()
191
{
192
  srand(time(NULL));
193
  read(n),read(m);
194
  for(int i=1;i<=n;i++)
195
  {
196
    reg int a;
197
    read(a);
198
    Insert(rt,a);
199
  }
200
  for(reg int i=1;i<=m;i++)
201
  {
202
    reg int opt,x;
203
    read(opt),read(x);
204
    x^=Last;
205
    if(opt==1)  Insert(rt,x);
206
    else if(opt==2)  Delete(rt,x);
207
    else if(opt==3)  {Last=GetRankByVal(rt,x);ans^=Last;}
208
    else if(opt==4)  {Last=GetValByRank(rt,x);ans^=Last;}
209
    else if(opt==5)  {Last=GetPre(x);ans^=Last;}
210
    else if(opt==6)  {Last=GetNext(x);ans^=Last;}
211
  }
212
  printf("%d",ans);
213
  return 0;
214
}

平衡二叉树（Treap）

https://www.laoguantx.cn/posts/treap/

作者

老官童鞋gogo

发布于

2024-09-29

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

可持久化线段树

增广矩阵与解线性方程组

Treap简介#

特点与作用#

基本结构#

Treap操作#

左旋和右旋#

插入#

删除#

前驱与后继#

根据valvalval查找排名#

根据排名查找valvalval值#

代码#

根据 $val$ 查找排名#

根据排名查找 $val$ 值#