JZTXT

平衡树

发布时间 2023-12-08 20:59:23作者: 睡不醒的凪

平衡树

平衡树有好多种，边学边写吧~。

目录

序号 类型
1 Treap
2 Splay
3 FHQ Treap
4 红黑树
5 替罪羊树
6 Link Cut Tree

前置芝士

二叉搜索树 BST

简介

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

操作

二叉搜索树支持 6 个基本操作：

  • 插入
  • 删除
  • 按排名查值
  • 按值查排名
  • 查前驱（小于它的最大值）
  • 查后继（大于它的最小值）

建树

没有什么复杂的操作，但是为了防止宇宙射线导致的越界，可以插入两个值为 $inf$ 和 $-inf$ 的节点。

插入

插入一个值 v，从根节点开始向下递归。

设现在所在节点为 now，分许多情况：

  1. 如果 now 为空，则在当前位置新建一个值为 v 的节点，并将 cnt 设为 1。
  2. 如果 $val_{now} == v$，那么将当前位置的 cnt 加一即可。
  3. 如果 $val_{now} > v$，递归 now 的左子树。
  4. 如果 $val_{now} < v$，递归 now 的右子树。

删除

参考

Treap

思想

Treap 实际是对于 BST 的一种实现方式，通过给予每个节点一个随机的优先级来保证其深度不过深，从而保证复杂度。

struct Treap {
	int rt, val[N], key[N], siz[N], son[N][2];
	ll sum[N];
	bool rev[N];
	
	inline void pushUp(const int& u) {
		sum[u] = sum[son[u][0]] + sum[son[u][1]] + val[u];
		siz[u] = siz[son[u][0]] + siz[son[u][1]] + 1;
	}
	inline void pushRev(const int& u) {
		if (u == 0) { return; }
		rev[u] ^= 1; std::swap(son[u][0], son[u][1]);
	}
	inline void pushDown(const int& u) {
		if (rev[u]) {
			pushRev(son[u][0]); pushRev(son[u][1]);
			rev[u] = false;
		}
	}
	
	void split(int u, int k, int& l, int& r) {
		if (u == 0) { l = r = 0; return; }
		pushDown(u);
		if (siz[son[u][0]] < k) {
			l = u; split(son[u][1], k - siz[son[u][0]] - 1, son[u][1], r);
		} else {
			r = u; split(son[u][0], k, l, son[u][0]);
		}
		pushUp(u);
	}
	int merge(int l, int r) {
		if (l == 0 || r == 0) { return l | r; }
		pushDown(l); pushDown(r);
		if (key[l] < key[r]) {
			son[l][1] = merge(son[l][1], r); pushUp(l); return l;
		} else {
			son[r][0] = merge(l, son[r][0]); pushUp(r); return r;
		}
	}
} tr;