# 【集训整理】 旋转treap模板

***

Treap是一种弱平衡的二叉搜索树，它同时符合二叉搜索树和堆的性质：

> 二叉搜索树：右子节点值>父节点>左子节点
>
> 堆：子节点的优先值比父节点值小

我们让每个节点的值符合二叉搜索树的性质，同时给每个节点赋一个随机的优先值，让优先值满足堆的性质。

由于优先值是随机的，一旦不满足堆性质就会产生旋转，所以就很难出现退化成链的情况，达到平衡的效果。

Treap分为旋转Treap和无旋treap两种，旋转treap的旋转操作分为右旋和左旋：

!\[image-20220703180723552]\(【集训整理】 旋转treap模板.assets/image-20220703180723552.png)

写成代码如下：

```
void left_rotate(int& id) { //左旋
	int tmp = rchild[id];
	rchild[id] = lchild[tmp];
	lchild[tmp] = id;
	id = tmp;
	push_up(lchild[id]);
	push_up(id);
}

void right_rotate(int& id) { //右旋
	int tmp = lchild[id];
	lchild[id] = rchild[tmp];
	rchild[tmp] = id;
	id = tmp;
	push_up(rchild[id]);
	push_up(id);
}
```

旋转操作其实只涉及两个点，交换下孩子即可。

树的储存，使用数组模拟结构体：

```
int lchild[maxn];
int rchild[maxn];
int val[maxn],prio[maxn];
int siz[maxn], cnt[maxn];
int tot, root;
```

`val`存值，`prio`存节点的优先值，`siz`记录某节点的子节点的数量，`cnt`记录某节点的值出现的次数，用于处理重复元素的情况。

创建节点：

```
int create(int v) {
	//创建节点，并给予随机优先值
	tot++;
	val[tot] = v;
	prio[tot] = rand();
	siz[tot] = 1;
	cnt[tot] = 1;
	return tot;
}
```

用rand函数给prio赋随机值。

更新siz的push\_up操作：

```
void push_up(int id) {
	//用于旋转后重新计算size
	siz[id] = siz[lchild[id]] + siz[rchild[id]] + cnt[id];
}
```

在旋转/插入后siz可能会变化，要push\_up从下到上更新。

初始化：

```
void build() { //初始化，插入一个正无穷和一个负无穷
	root = create(-inf);
	rchild[root] = create(inf);
	push_up(root);
}
```

初始化要先往里边塞一个正无限和一个负无限节点。

插入：

在二叉查找树上找位置插入，找到树缺位或已有节点修改。每次插完都要检测符不符合堆的性质，如果不符合就用旋转的方式进行平衡。

注意，每层插入递归结束后都要进行一次push\_up重新计算size值。

```
void insert(int& id, int v) {
	if (!id) { //找到树缺位（引用指向的变量（l/rchild）为0）
		id = create(v);
		return;
	}
	if (v == val[id]) cnt[id]++;
	else { //遍历查找树，知道找到他该在的位置
		if (v < val[id]) {
			insert(lchild[id], v);
			//每次插完都要检测符不符合堆的性质，不符合就平衡
			if (prio[id] < prio[lchild[id]]) right_rotate(id);
		}
		else {
			insert(rchild[id], v);
			if (prio[id] < prio[rchild[id]]) left_rotate(id);
		}
	}
	push_up(id); //插入后size会变，沿路更新
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/shu-ju-jie-gou/ji-xun-zheng-li-xuan-zhuan-treap-mu-ban.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.