无旋 Treap

Gyf117 · 2026-07-02 19:41:45 · 算法·理论

Treap

看这个词不难想到 Tree（二叉搜索树）和 Heap（堆）。

Treap 就是一种结合了二叉搜索树与堆的优点的一种数据结构。

Treap 通过二叉搜索树维护操作，通过随机堆的值来维持平衡。（如下图）

节点里的数是值，满足二叉搜索树的性质（即左子树所有值均小于当前节点，右子树所有值均大于当前节点）。节点旁黄色的是随机权值（这里为了方便阅读，写成小值），满足堆（本文为小根堆）的性质。

Treap 分为有旋与无旋两种，本文主要介绍无旋 Treap。

无旋 Treap

无旋 Treap 通过分裂与合并操作实现。

这里以P3369 【模板】普通平衡树为例题讲解。

首先是节点，要存储当前点的值以及随机权值，并且维护一个字树大小。

struct Node {
  int ls, rs; // 左右儿子
  int v; // 值
  int k; // 随机权值
  int sz; // 子树大小
} tr[N];

以及新建节点

int idx;
int add(int v) { // 新建一个值为 v 的节点并返回编号
  int p = ++ idx;
  tr[p].v = v; // 随机权值
  tr[p].k = rand();
  tr[p].sz = 1;
  return p;
}

还有上传

void pushup(int p) {
  tr[p].sz = tr[tr[p].ls].sz + tr[tr[p].rs].sz + 1;
}

上面的都较为简单不做讲解。

接下来是分裂操作。

现在有一棵以 p 为根的树，要按值分裂成左右两棵，根为 x, y，左边的树的值都小于等于 v，右边的树的值都大于 v。

如果 p 的值 \le v，那么说明 p 及其左子树一定在左边的那棵树，且 p 一定是左边的树的根，那么令 x = p，右子树中可能还有 \le v 的，递归处理右子树，并将右子树的分裂出的左边的树的根放到 p 的右儿子。

如果 p 的值 > v，那么说明 p 及其右子树一定在右边的那棵树，且 p 一定是右边的树的根，那么令 y = p，左子树中可能还有 > v 的，递归处理左子树，并将左子树的右边的树放到 p 的左儿子。

可以发现，这样分裂出的两棵树的边一定是初始时的边或者是祖先连向儿子，所以满足堆的性质。

最后更新一下 p 的子树大小即可。

pair<int, int> split(int p, int v) { // pair 表示 x, y
  if (!p) { // 当前节点为空，分裂出的两棵树也都为空
    return make_pair(0, 0);
  }
  pair<int, int> res;
  if (tr[p].v <= v) {
    res = split(tr[x].rs, v); // 递归右子树
    tr[x].rs = res.first; // 将右儿子改为右子树的分裂出的左边的树的根
    res.first = p; // 将 x 改为 p
  } else {
    y = p;
    res = split(tr[y].ls, v); // 递归左子树 
    tr[y].ls = res.second; // 将左儿子改为左子树的分裂出的右边的树的根
    res.second = p; // 将 y 改为 p
  }
  pushup(p); // 更新 p 的 sz
  return res;
}

理解后可以换成下面这种写法

void split(int p, int v, int &x, int &y) { // 这个引用写法类似将 x, y 返回后赋值
  if (!p) { // 当前节点为空，分裂出的两棵树也都为空
    x = 0;
    y = 0;
    return;
  }
  if (tr[p].v <= v) {
    x = p; // 将 x 改为 p
    split(tr[x].rs, v, tr[x].rs, y); // 递归右子树，并将右儿子改为右子树的分裂出的左边的树的根
  } else {
    y = p; // 将 y 改为 p
    split(tr[y].ls, v, x, tr[y].ls); // 递归左子树，并将左儿子改为左子树的分裂出的右边的树的根
  }
  pushup(p); // 更新 p 的 sz
}

模拟一下，现在要将下面这棵树按 v = 5 分开（当前根用 rt 表示，最终分裂出的根用 x_0, y_0 表示，这里节点的编号与值相等）。

首先递归 p = 4，x 为 x_0，y 为 y_0。