Treap

缘起

接【1】，我们给出oj中常用的另一种平衡树——Treap，

分析

Treap译为树堆. Treap树算是一种简单的优化策略，这名字大家也能猜到，树和堆的合体，其实原理比较简单，在树中维护一个”优先级“，”优先级“， 采用随机数的方法生成优先级，但是”优先级“必须满足根堆的性质，当然是“大根堆”或者“小根堆”都无所谓。下面就是一棵treap

可以看到, 每个treap节点有两个域 一个是key值，一个是优先级. 其中

  1. key满足BST。
  2. 优先级满足小根堆（其实大根堆也行）。

这其实就是Treap的定义. 一言以蔽之，treap是指有一个随机附加域满足堆的性质的BST。而treap引入的缘起就是因为BST的最坏O（N）的查询. 而treap怎么做到不会变到最坏情况呢? 显然就是随机的优先级必须要成堆的限制（treap和串匹配的Karp-Rabin算法异曲同工, 可以讲有种乱拳打死老师傅&浑水摸鱼的赶脚）. 可以说treap的性能介于BST和AVL之间.

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;

const int MAX_N = 15;

struct TreapNode
{
	int lSon,rSon,size,cnt,val,priority; // lSon是左孩子索引, rSon是右孩子索引, size是树的节点个数, cnt是本节点的重复次数，val是本节点的值，priority是本节点的优先级
} treap[MAX_N]; // 索引0不存放数据

int tot; // 节点总数

void update(int k) // 更新以treap[k]为根节点的节点数目大小
{
	treap[k].size = treap[treap[k].lSon].size + treap[treap[k].rSon].size+ treap[k].cnt;
}

void leftrotate(int &k) // 左旋, 参见图1
{
	int r = treap[k].rSon;
	treap[k].rSon = treap[r].lSon;
	treap[r].lSon = k;
	treap[r].size = treap[k].size;
	update(k);
	k = r;
}

void rightrotate(int &k) // 右旋, 参见图2
{
	int l = treap[k].lSon;
	treap[k].lSon = treap[l].rSon;
	treap[l].rSon = k;
	treap[l].size = treap[k].size;
	update(k);
	k = l;
}

void insert(int &k, int x) // 往以treap[k]为根节点的treap中加入x
{
	if (!k) // 如果是空树，或者已经找到了要插入的位置了
	{
		k = ++tot;
		treap[k].cnt = treap[k].size = 1;
		treap[k].val = x;
		treap[k].lSon = treap[k].rSon = 0;
		treap[k].priority = rand(); // 随机优先值
		return;
	}
	treap[k].size++;
	if (x < treap[k].val)
	{
		insert(treap[k].lSon, x); // 往左子树插入
		if (treap[treap[k].lSon].priority < treap[k].priority) // 如果插完左子树之后发现左子树和k之间违背了小根堆定义的话, 就要调整
		{
			rightrotate(k); // 右旋, 参见图2，注意，切记插入之前已经是一棵合法的Treap, l是新增的顶点不断的一路旋转翻上来的. 所以k的优先级 <=P和R的优先级. 所以右旋之后的bst就满足treap的定义了而不需要担心右旋之后, k的优先级>P或者R的优先级.
		}
	}
	else if (x > treap[k].val)
	{
		insert(treap[k].rSon, x);
		if (treap[treap[k].rSon].priority <treap[k].priority) leftrotate(k);
	}
	else
	{
		treap[k].cnt++; // 仅仅重复计次+1
	}
}

void del(int &k, int x, bool &flag) // 在以treap[k]为根节点的treap中删除关键字x,flag表示到底发没发现关键字x,如果没发现的话,各个节点的size就不必减1了
{
	if (!k) // 如果没找到
	{
		flag = false;
		return;
	}
	if (treap[k].val == x) // 找到了
	{
		flag = true;
		if (treap[k].cnt == 1) // 如果仅有一个，删完了就没了
		{
			if (!treap[k].lSon || !treap[k].rSon)
			{
				k = treap[k].lSon + treap[k].rSon; // 如果没有左孩子或者右孩子，则简单嫁接即可. 不会影响treap的堆性质
			}
			else if(treap[treap[k].lSon].priority > treap[treap[k].rSon].priority) // 如果左孩子的优先级>右孩子的优先级的话 则应该对k左旋
			{
				leftrotate(k); // 注意, k已经指向了右孩子, 原先的根节点已经变成了左孩子
				del(treap[k].lSon, x, flag); // 所以相当于是不断的将要删除的k向下滚动.
			}
			else // 如果右孩子的优先级>=左孩子的优先级，则k应该由左孩子来当
			{
				rightrotate(k);
				del(treap[k].rSon, x, flag);
			}
		}
		else // 有多，不怕删
		{
			treap[k].cnt--;
			treap[k].size--;
		}
	}
	else if(treap[k].val > x)
	{
		del(treap[k].lSon, x, flag); // 跑到左子树上删除
		if (flag) // 这就是记录flag的作用——因为每个节点维护了节点的size，所以需要flag
		{
			treap[k].size--;
		}
	}
	else
	{
		del(treap[k].rSon, x, flag);
		if (flag)
		{
			treap[k].size--;
		}
	}
}

int _rank(int k, int x) // 询问关键字x在以treap[k]为根节点的子树中排名几何?(因为treap中可能不止有一个x(或者x本不存在于treap中),如果这样,输出的是x最靠前的排名,比如1,2,2,3中x=2的排名,输出就是第二名而不是第三名,但是话说回来,要输出第三名也很容易~)
{
	if (!k) return 0; // 空树或者没找到
	if (treap[k].val ==x)
	{
		return treap[treap[k].lSon].size+1;
	}
	else if (treap[k].val > x)
	{
		return _rank(treap[k].lSon, x);
	}
	else
	{
		treap[k].cnt + treap[treap[k].lSon].size+_rank(treap[k].rSon, x);
	}
}

int query(int k, int x) // 返回在以treap[k]为根节点的子树中排名为x的关键字
{
	if (!k) return 0; // 如果是空树, 
	if (x<=treap[treap[k].lSon].size) return query(treap[k].lSon, x);
	else if (x > treap[k].cnt+ treap[treap[k].lSon].size) return query(treap[k].rSon, x - treap[k].cnt- treap[treap[k].lSon].size);
	else return treap[k].val;
}

int pred(int k, int x, int pre_k) // 取得以treap[k]为根节点的子树关于x的前驱(这里x未必是treap中的元素,所以前驱的理解与sbt那里一样就是比x严格小的最大的在treap中的关键字)，算法与SBT也类似
{
	if (!k)
	{
		return treap[pre_k].val;
	}
	if (treap[k].val <x)
	{
		return pred(treap[k].rSon,x, k);
	}
	else // treap[k].val >= x, 则k不会是前驱, 前驱不变, 依旧是 pre_k
	{
		return pred(treap[k].lSon, x, pre_k);
	}
}

int succ(int k, int x, int succ_k) // 以treap[k]为根的子树中>x的最小值
{
	if (!k)
	{
		return treap[succ_k].val;
	}
	if (treap[k].val > x)
	{
		return succ(treap[k].lSon, x, k);
	}
	else
	{
		return succ(treap[k].rSon, x, succ_k);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	srand((int)(time(0)));
	int a[10]={1,5,2,5,6,3,7,8,7,2}, root = 0, i;
	for (i = 0; i < 10; i++)
	{
		insert(root,a[i]);
	}
	int x;
	bool flag=false;
	puts("输入你要查询的数x,程序将输出它的排名");
	scanf_s("%d",&x);
	printf("%d在加入treap的这些关键字中排名%d\n",x,_rank(root,x));
	//测试query模块
	puts("输入你想查询的排名,程序将输出这一排名的关键字");
	scanf_s("%d",&x);
	printf("treap中排名%d的关键字是%d\n",x,query(root,x));
	//测试pred模块
	puts("输入数x,程序将输出它的前驱");
	scanf_s("%d",&x);
	printf("%d的前驱关键字是%d\n",x,pred(root,x,0));
	//测试succ模块
	puts("输入数x,程序将输出它的后继");
	scanf_s("%d",&x);
	printf("%d的后继关键字是%d\n",x,succ(root,x,0));
	//测试del模块
	for ( i = 0; i < 5; i++)	
		del(root,a[i],flag);	
	del(root,9,flag);//测试删除一个本不存在的关键字
	for (   ; i < 10; i++)	
		del(root,a[i],flag);	
	return 0;
}

参考

【1】https://yfsyfs.github.io/2019/06/04/SBT/

附录

​ 图1

​ 图2