\(Treap = Tree + Heap\)

树堆（Treap），在数据结构中也称Treap，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。

                                                                                   ----百度百科

要了解Treap，就先要看看什么是二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

                                                                                   ----百度百科

Treap既有BST的性质，也有堆的性质，Treap的每个结点额外附加一个随机值（优先级），让他们按照关键码构成BST的同时也满足堆的性质（父节点优先级高于或低于子节点优先级），因为优先级是随机的，这样在绝大多数情况下我们得到的树都是平衡的，不容易被卡成链， 单次操作期望时间复杂度为O(logn)。

操作：

1.定义

struct Treap {

	int dat, val;

	int cnt, size, l, r;

} e[N];

dat 随机优先级； val BST关键码； cnt 当前结点数量； size 子树结点数量； l，r 左右儿子。

2.更新

void update(int p) {

	e[p].size = e[e[p].l].size + e[e[p].r].size + e[p].cnt;

}

更新结点size值。

3.新建结点

int newpoint(int val) {

	e[++tot].val = val;

	e[tot].dat = rand();

	e[tot].cnt = e[tot].size = 1;

	return tot;

}

4.建树

void build() {

	newpoint(-inf); newpoint(inf);

	root = 1; e[root].r = 2; update(root);

}

初始化两个结点，设置为无限大和无限小。

5.左右旋转

左右旋转是在保证BST性质前提下（中序遍历不变）将一个结点向上或者向下转，实质上是父节点变成了子节点，子节点变成了父节点。

左旋和右旋分别对应着将左儿子翻上来和将右儿子翻上来。



具体操作

void zig(int &p) {//左旋

	int q = e[p].l;

	e[p].l = e[q].r; e[q].r = p; p = q;

	update(e[p].r); update(p);

}

void zag(int &p) {//右旋

	int q = e[p].r;

	e[p].r = e[q].l; e[q].l = p; p = q;

	update(e[p].l); update(p);

}

//p引用的是旋转前的根结点

6.插入

插入一个值为val的结点，若存在关键码为val的结点，将此结点数量 + 1，若不存在，根据val大小和当前结点val大小向左右两边找，最后新建结点，返回时要维护堆性质。

void insert(int &p, int val) {

	if(p == 0) {

		p = newpoint(val); return ;

	}

	if(e[p].val == val) {

		e[p].cnt++; update(p);

		return ;

	}

	if(val < e[p].val) {

		insert(e[p].l, val);

		if(e[p].dat < e[e[p].l].dat) zig(p);

	} else {

		insert(e[p].r, val);

		if(e[p].dat < e[e[p].r].dat) zag(p);

	}

	update(p);

}

7.删除结点

删除一个值为法val的结点，先在树中查找值为val的结点：

1.若结点cnt(数量) 大于1，则可以直接减1，返回；

2.若结点数量为1，将其向下旋转，转到叶结点时直接删除；

注意：在向下旋转时应维护堆的性质，若是大根堆，选取子节点中dat大的结点与其交换。

void delet(int &p, int val) {

	if(p == 0) return ;

	if(val == e[p].val) {

		if(e[p].cnt > 1) {

			e[p].cnt--; update(p); return ;

		} else {

			if(e[p].l || e[p].r) {//不为叶结点

				if(e[e[p].l].dat > e[e[p].r].dat || !e[p].r)

					zig(p), delet(e[p].r, val);

				else

					zag(p), delet(e[p].l, val);

				update(p);

			} else p = 0;

		}//else

		return ;

	}

	if(val < e[p].val) delet(e[p].l, val);

	else delet(e[p].r, val);

	update(p);

}

8.排名

包括根据值查排名和根据排名查值。

1.根据值查排名(rankk();)我们只需要从根节点往下找，如果当前结点值较大，递归查询左儿子；如果当前结点值较小，递归查询右儿子，返回时要加上左子树结点数和当前节点的数量。

2.根据排名查值(arcrank();），同样，如果当前结点值较大， 递归查询左儿子； 如果当前结点值较小，递归查询右儿子，注意查询右儿子时应将排名减去左子树和当前结点的数量。

int rankk(int p, int val) {

	if(p == 0) return 0;

	if(val == e[p].val) return e[e[p].l].size + 1;

	if(val < e[p].val) return rankk(e[p].l, val);

	return rankk(e[p].r, val) + e[e[p].l].size + e[p].cnt;

}

int arcrank(int p, int k) {

	if(p == 0) return inf;

	if(k <= e[e[p].l].size) return arcrank(e[p].l, k);

        if(k <= e[p].cnt + e[e[p].l].size) return e[p].val;

	return arcrank(e[p].r, k - e[p].cnt - e[e[p].l].size);

}

9.查询前驱和后继

拿前驱来说，若查询v的前驱，分两种情况：

1.找到了值为v的结点，那么v的前驱就是v的左子树中值最大的点的值， 找到直接返回。

2.没有找到结点为v的值，需要不断比较，若当前结点值比v小且比找到的答案大，就更新答案。

后继与前驱类似。

int getper(int val) {

	int p = root, ans = 1;//初始化为无限小

	while(p) {

		if(val == e[p].val) {

			if(e[p].l) {

				p = e[p].l;

				while(e[p].r) p = e[p].r;

				ans = p;

			}

			break;

		}

		if(e[p].val < val && e[ans].val < e[p].val) ans = p;//比较，更新答案

		if(val < e[p].val) p = e[p].l;

		else p = e[p].r;

	}

	return e[ans].val;

}

int getnext(int val) {

	int p = root, ans = 2;//初始化为无限大

	while(p) {

		if(val == e[p].val) {

			if(e[p].r) {

				p = e[p].r;

				while(e[p].l) p = e[p].l;

				ans = p;

			}

			break;

		}

		if(e[p].val > val && e[ans].val > e[p].val) ans = p;

		if(val < e[p].val) p = e[p].l;

		else p = e[p].r;

	}

	return e[ans].val;

}

完整代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int N = 100005;

const int inf = (1 << 31) - 1;

int n, root, tot = 0;

struct Treap {

	int dat, val;

	int cnt, size, l, r;

} e[N];

void update(int p) {

	e[p].size = e[e[p].l].size + e[e[p].r].size + e[p].cnt;

}

int newpoint(int val) {

	e[++tot].val = val;

	e[tot].dat = rand();

	e[tot].cnt = e[tot].size = 1;

	return tot;

}

void build() {

	newpoint(-inf); newpoint(inf);

	root = 1; e[root].r = 2; update(root);

}

void zig(int &p) {

	int q = e[p].l;

	e[p].l = e[q].r; e[q].r = p; p = q;

	update(e[p].r); update(p);

}

void zag(int &p) {

	int q = e[p].r;

	e[p].r = e[q].l; e[q].l = p; p = q;

	update(e[p].l); update(p);

}

void insert(int &p, int val) {

	if(p == 0) {

		p = newpoint(val); return ;

	}

	if(e[p].val == val) {

		e[p].cnt++; update(p);

		return ;

	}

	if(val < e[p].val) {

		insert(e[p].l, val);

		if(e[p].dat < e[e[p].l].dat) zig(p);

	} else {

		insert(e[p].r, val);

		if(e[p].dat < e[e[p].r].dat) zag(p);

	}

	update(p);

}

void delet(int &p, int val) {

	if(p == 0) return ;

	if(val == e[p].val) {

		if(e[p].cnt > 1) {

			e[p].cnt--; update(p); return ;

		} else {

			if(e[p].l || e[p].r) {

				if(e[e[p].l].dat > e[e[p].r].dat || !e[p].r)

					zig(p), delet(e[p].r, val);

				else

					zag(p), delet(e[p].l, val);

				update(p);

			} else p = 0;

		}

		return ;

	}

	if(val < e[p].val) delet(e[p].l, val);

	else delet(e[p].r, val);

	update(p);

}

int rankk(int p, int val) {

	if(p == 0) return 0;

	if(val == e[p].val) return e[e[p].l].size + 1;

	if(val < e[p].val) return rankk(e[p].l, val);

	return rankk(e[p].r, val) + e[e[p].l].size + e[p].cnt;

}

int arcrank(int p, int k) {

	if(p == 0) return inf;

	if(k <= e[e[p].l].size) return arcrank(e[p].l, k);

	else if(k <= e[p].cnt + e[e[p].l].size) return e[p].val;

	return arcrank(e[p].r, k - e[p].cnt - e[e[p].l].size);

}

int getper(int val) {

	int p = root, ans = 1;

	while(p) {

		if(val == e[p].val) {

			if(e[p].l) {

				p = e[p].l;

				while(e[p].r) p = e[p].r;

				ans = p;

			}

			break;

		}

		if(e[p].val < val && e[ans].val < e[p].val) ans = p;

		if(val < e[p].val) p = e[p].l;

		else p = e[p].r;

	}

	return e[ans].val;

}

int getnext(int val) {

	int p = root, ans = 2;

	while(p) {

		if(val == e[p].val) {

			if(e[p].r) {

				p = e[p].r;

				while(e[p].l) p = e[p].l;

				ans = p;

			}

			break;

		}

		if(e[p].val > val && e[ans].val > e[p].val) ans = p;

		if(val < e[p].val) p = e[p].l;

		else p = e[p].r;

	}

	return e[ans].val;

}

int main() {

//	freopen("data.in", "r", stdin);

	scanf("%d", &n); build();

	while(n--) {

		int opt, x; scanf("%d%d", &opt, &x);

		switch(opt) {

			case 1:

				insert(root, x);

				break;

			case 2:

				delet(root, x);

				break;

			case 3:

				printf("%d\n", rankk(root, x) - 1);

				break;

			case 4:

				printf("%d\n", arcrank(root, x + 1));

				break;

			case 5:

				printf("%d\n", getper(x));

				break;

			case 6:

				printf("%d\n", getnext(x));

				break;

		}

	}

	return 0;

}

最新文章

1. Content has been consumed
2. python之路-Mysql&&ORM
3. 如何用Matlab将cell数据写入文件
4. c语言详解sizeof
5. 2016 ACM/ICPC Asia Regional Dalian Online 1006 /HDU 5873
6. IntelliJ IDEA 注册码
7. javascript 面向对象制作坦克大战 （一）
8. android驱动[置顶] 我的DIY Android之旅--驱动并控制你的Android开发板蜂鸣器
9. Java方法-字符串
10. 【BZOJ 1088 扫雷Mine】模拟
11. javascript生成自定义的arcgis simpletoolbar
12. OpenGL与vs编程——error C2440: “glMaterialfv”: 无法从“GLfloat”转换为“const GLfloat *”
13. GridView中添加行单击事件.md
14. ES6 中 Promise 详解
15. Arrays类
16. react官方脚手架搭建项目
17. 实例分析JAVA CLASS的文件结构
18. HBase（四）HBase集群Shell操作
19. 论文笔记：IRGAN——A Minimax Game for Unifying Generative and Discriminative Information
20. Vjudge - B - 这是测试你会不会排序

热门文章

1. 深入理解ClassLoader
2. Web自动化测试项目搭建（一） 需求与设计
3. Android教程2020 - RecyclerView显示多种item
4. <状压DP>solution-HDU5691_Sitting in Line
5. js实现表单的提交
6. 第一篇：CDH配置本地http服务
7. C语言中typedef用法
8. Webpack 一，打包JS
9. Codeforces_803
10. （七）mybatis批量操作，分页插件