#数据结构 #平衡树 #题解

题目来源
请读者先自行阅读题目

概述

我们现在要对一个数列进行在线的加入、删除、查询功能，如果每加入一个数就对这串数进行排序是很明显不现实的，这样的时间复杂度是，所以我们需要一种新的数据结构进行这样的操作，于是人们发明了平衡树。各种平衡树有各自的优点与缺点，虽然理论上所有平衡树的一次操作的复杂度是的，但是根据事实情况不同有不同的选择方案。如在实际应用中常用的是红黑树（贼难写，但是效率可以说是最高的）和B树。

那今天呢我们来讲一种可以说是最好写的平衡树——Treap，这是一种重量平衡树。注意这里讲的是无旋式Treap，也就是FHQ Treap，相较于旋转式的Treap，它更好写，效率也更高。~~我瞎说的，其实老师就没有讲旋转的Treap~~

数据结构

如果不了解BST(Binary Search Tree)的同学可以~~趋势了~~离开了。
如果人品差到极致的同学其实 ~~也没必要活着了~~ 也可以离开了(要是真能差到极致我也是佩服)

Treap的基本原理：

每个节点有两个数据，一个是存储值的，一个是存储优先级的
Treap = Tree + Heap

是什么意思呢，就是对于每个新建的结点赋予一个随机的优先级，然后最后让这个二叉树既满足堆的性质又满足二叉平衡树的性质，可以证明，这两个参数的加持下只能够形成一个唯一的Treap (如果你说两个结点优先级都一样，好吧你赢了)。~~证明的话小学生都会，我就不说了~~

由于这样的随机性，它的时间复杂度期望也是级别的，但是由于其不稳定性，所以实际应用应该也很少吧？如果真的有人能随机出个点形成一条链的话，你可能是造了什么孽吧啊啊啊

然后我们回到它的具体实现上，这个地方就能体现FHQ Treap的高明之处了。

我们先来看看FHQ Treap结点的定义：

//本文章是由指针实现的数据结构
//感觉使用指针的话很有年代感
//指针比较消耗空间
mt19937 mt(random_device{}());
#define siz(x) (x? x -> siz : 0) //为了防止空指针使用时RE
struct node {
  node *ls, *rs; //做儿子和右儿子
  int val, prio, siz; //值，优先级和以自己为根的树的大小（后面会用）
  node(int val = 0): val(val) { //初始化
    ls = rs = nullptr; //左右儿子初始化为空
    val = 0;
    prio = mt(); //随机优先级
    siz = 1; //大小要初始化为1，务必注意
  }
  void upd() { //操作时要更新
    siz = siz(ls) + siz(rs) + 1;
  }
};

FHQ Treap有两个基本操作：Merge 和 Split 。Merge就是将两个FHQ Treap合在一起，Split也就是从一个地方分开，能做到把前几个数和后几个数（比n小的和比n大的分开是一个道理）分成两个树（BST中序遍历不就是本来的序列吗，这样就相当于把原本的序列切成两半然后再形成两个平衡树）。这两个操作是互逆的。

接下来讲操作（本文使用小根堆实现）

Merge(u, v)

假设现在要合并这两棵树（一个结点左边是值，右边是优先级）：

FHQ Treap合并的思路是这样的，首先我们严格要求左边这棵树点值的最大值必须要小于右边这棵树点值的最小值，这样就能保证每次操作都能把一棵树完全放到另一棵树的一边。

合并的过程是递归的，从两个点的根结点开始，如果u的优先级比v的小，那么u肯定是v这个树的父节点，又因为u中所有结点都是小于v中的，所以v肯定全部都在u的右儿子中，因此我们将u的右儿子与v合并。反之则将u与v的左儿子合并，很好理解。如果最后有一边是空了，那么返回另一个就行。

具体操作如下

所以v在u的右子树上，将递归到u的右子树与v合并
所以右边的树在上面，这个子树的根就是，然后继续递归的那棵树和的左子树

这里将和连接起来了是方便理解与观看，实际更新儿子是在子树递归完后更新的（具体见后面的代码）

然后我们继续合并这两个子树，由于优先级所以显然是根节点。

然后另外一个树变成空节点了，于是直接连接和即可

于是我们成功合并了两棵子树！

接下来我们来看看代码：

//需要u小于v
node* merge(node* u, node* v) { //合并以u, v为根节点的两个Treap，返回新的根
  if (!u) return v; //空的话返回另一个
  if (!v) return u;
  if (u -> prio < v -> prio) { //比较优先级
	  //u的优先级比v小，说明u应该为根
	  //因为v中所有的数都比u大，所以u肯定在v的右边
    u -> rs = merge(u -> rs, v); //合并右子树和v
    u -> upd(); 
    //更新子树的大小，通常用于按排列进行split和求第k小(大)时或其他问题时会用到
    //如果真的有题目用不到upd的时候也可以不写，但是建议写
    //为什么这样更新是对的？
    //首先是在merge更新完后再更新，保障了从下到上更新
    //但是你会发现在合并到最下面的结点时不会upd()
    //所以siz必须要初始化为1
    //并且在分裂的时候任何结点都会更新
    //所以不会有问题
    return u;
  } else {
	  //同理，而且因为v在上面，所以要赋值给v->ls而不是u
    v -> ls = merge(u, v -> ls);
    v -> upd();
    return v;
  }
}

Split(u, v, l, r)

ValSplit

我们首先来讲按值来分裂。

由于画图对逻辑上理解好像并没有什么帮助，反而是递归更能让人理解其运行的内在逻辑，所以我不画图了。

~~绝对不是因为我懒！！！~~

什么是分裂呢，前面已经说过了，近视的同学回去再找找。

我们想现在要把一个完整的Treap从中间拆成两个树，我们就倒着想合并的过程（这里不太好用语言描述，请读者自己想象）。

而我们伟大的先辈FHQ同志就是这么想的，我从点开始分裂，不超过的分给一个树，超过的分给另一个树。那么如果则和它的左子树都是属于的且为的根(因为的优先级肯定是最小的)，反之同理。

那我们继续想，接下来只需要将的右子树再进行同样的操作分成和，并且将作为的右子树，再更新的值为即可。

这里可以简化一下，直接将作为进行递归即可。

上代码：

void valsplit(node* u, int v, node* &l, node* &r) {
  if (!u) {
    l = r = nullptr; //如果u是空结点，将l和r赋值为0
    //注意这里很重要！如果不赋值为0，siz会出问题（亲身经历）
    return;
  }
  if (u -> val <= v) { //就像上面说的一样
    l = u; //l赋值为u
    valsplit(u -> rs, v, u -> rs, r); 
    //直接将u -> rs作为l，这样分出来的左子树自然就在u -> rs上了
  } else { // 同理
    r = u;
    valsplit(u -> ls, v, l, u -> ls);
  }
  u -> upd(); // 更新大小，作用待会见
}

RankSplit

函数名字都是我瞎取的

这次不是按值来分树，而是按排名（或者说数量）来分。

这时就要用到了。如果看懂了的同学想一想应该也能知道怎么写。

看代码：

void RankSplit(node* u, int k, node* &l, node* &r) {
	if (!u) {
		l = r = nullptr;
		return;
	}
	if (siz(u -> ls) < k) { // siz(u -> ls) + 1 <= k
		l = u;
		RankSplit(u -> rs, k - siz(u -> ls) - 1, u -> rs, r); //这里递归的排名也要减
	} else { //自己思考思考
		r = u;
		RankSplit(u -> ls, k, l, u -> ls);
	}
	u -> upd();
}
//注：
//这里如果siz(u -> ls) + 1 == k
//可以直接l = u; r = u -> rs; u -> rs = 0;

SuperMerge(u, v)

在学会了merge和split后你是否希望做到merge任意两个Treap呢？（反正我还没遇到过）

merge只能u小于v的原因是要将一个完全放到另一个的一边的子树里。但是现在你学会了split，是否可以使用split来实现supermerge呢？

见代码：

node* SuperMerge(node* u, node* v) {
	if (!u) return v;
	if (!v) return u;
	if (u -> prio > v -> prio) swap(u, v); //使得u一定是根，方便操作。
	node *l, *r;
	Split(v, u -> val, l, r);
	u -> ls = SuperMerge(u -> ls, l);
	//进行递归，这里之所以还用SuperMerge是因为之确保了l<u并不确保u->ls和l的关系
	u -> rs = SuperMerge(u -> rs, r);
	u -> upd();
	return u;
}

kthn(u, k)

现在我们写最后一个基础函数，也是最简单最容易理解的一个，求第k小的数。

我们现在有siz也知道了怎么递归，我们其实可以自己写出kthn函数

（我当时就是自己写出来的求第k小函数，和使用较广方法的一样）

代码如下：

int kthn(node* u, int k) {
	//这里也可以返回u，类型变为node* 即可
	if (siz(u -> ls) + 1 == k) return u -> val; //就是这个点
	if (siz(u -> ls) >= k) return kthn(u -> ls, k); //在左边
	return kthn(u -> rs, k - siz(u) - 1); //在右边
}

具体操作

基础函数和对Treap的合并分裂都学会了，我们来看看这道题。

插入

插入比较简单，我们新建一个结点，将其看作是一个一个大小的Treap，然后将现有的Treap按新结点的值分开再从中间插进去合并即可。

void insert(int x) {
	node *l, *r, *add;
	add = new node(x); //新建节点
	ValSplit(root, x, l, r); //按值分开
	root = Merge(Merge(l, add), r); //再合在一起
}

删除

通过分裂操作，我们可以将小于的数，等于的数，大于的数分开，但是只删除一个怎么办呢？我们只需要将全部等于的树的根节点的左右儿子合并最后再合并在一起就可以了，这样自然就少了一个。

真是天才的做法！

inline void del(int x) {
  node *l, *r, *p, *tmp;
  valsplit(root, x, l, r);
  valsplit(l, x - 1, l, p);
  tmp = p;
  p = merge(p -> ls, p -> rs);
  delete tmp;
  root = merge(merge(l, p), r);
}

查询排名

看代码自己理解

void getrank(int x) {
  node *l, *r;
  valsplit(root, x - 1, l, r);
  printf("%d\n", siz(l) + 1);
  merge(l, r); //因为树没有变过，所以不用更新root
}

查询排名为的数

更简单了，直接用函数

求的前趋

只需要将小于的数分裂出来再求分裂出来的左边的树求第siz个的大小。

代码:

void lema(int x) { //less than max 什么神奇Chinglish
  node *l, *r;
  valsplit(root, x - 1, l, r);
  if (!l) {
    puts("-1");
    return;
  }
  printf("%d\n", kthn(l, siz(l))); //第siz大的自然是前趋了
  merge(l, r);
}

求的后继

更简单了，同前趋

void grmi(int x) { // greater min
  node *l, *r;
  valsplit(root, x, l, r);
  if (!r) {
    puts("-1");
    return;
  }
  printf("%d\n", kthn(r, 1));
  merge(l, r);
}

后记

对于Treap，我们需要一种递归思维。我们不能只通过图去理解整个流程，递归是一种方式，我们要用函数式的思想去理解，它是一种规律的操作而不是一种过程。只有当你真正理解了这种规律，你就可以说你对这种数据结构了如指掌了。

嘎嘎嘎嘎嘎，写的太多了，累啊累啊累啊

Huasushis 's Blog

洛谷P3369【模板】普通平衡树

概述