浅析FHQ-treap

fush · 2024-12-26 09:00:19 · 算法·理论

前言

本文无重大错误不再更新，更新会放在博客
fhq-treap 又名“无旋 treap”，有着码量小，易理解，可持久化等特点。
但 fhq-treap 的常数较大。
必要：

• 二叉搜索树
• 堆

选要：

• 旋转treap

  基础操作

  treap 的每个节点都有一个随机的优先级。
  treap 的权值要具有二叉搜索树的性质，优先级满足堆的性质。
  fhq-treap 有两个关键函数 slipt 和 merge，分别是分裂和合并。
  代码中均为小根堆。

  节点

  在 fhq-treap 中我们需要维护子树大小，节点权值，左右儿子，优先级（随机数，用于堆）。

  std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
  //需要 <random> 和 <chrono> 头文件，不要放在结构体内
  struct node{
  int size, val, rank, ls, rs;
  }d[N];
  int tot = 0, root = 0;
  int newnode(int val){
  d[++tot].val = val, d[tot].rank = rd();
  d[tot].size = 1, d[tot].ls = d[tot].rs = 0;
  return tot;
  }
  void getsize(int u){d[u].size = 1 + d[d[u].ls].size + d[d[u].rs].size;}

  分裂

  按权值分裂

  明显，我们会把一个树，把权值 \le k 的放在 L 树中，> k 的放在 R 树中。

  void SplitVal(int now, int val, int&L, int&R){
  if(!now)return void(L = R = 0);
  if(d[now].val <= val)L = now, SplitVal(d[now].rs, val, d[now].rs, R);
  else R = now, SplitVal(d[now].ls, val, L, d[now].ls);
  return getsize(now);
  }

  我们理解一下代码。
  我们现在遍历到了原树的 now 节点。
  如果节点是空的那么 L 和 R 树都是空的。

如果这个节点的权值 \le k：