平衡树

建议在清楚二叉搜索树的所有操作之后食用本文。本文将略过部分基础知识

本文主要会讲到4中较常用的平衡树：

• Treap

• FHQ-Treap（无旋Treap）

• Splay

• WBLT

其实WBLT不怎么常用，但是我个人最喜欢用

我将会在另一篇文章中讲述其他的平衡树，如AVL，红黑树，替罪羊树等。

可持久化我还会放在另一篇文章中讲述，敬请期待。

Treap

Treap也就是 Tree + Heap，在满足二叉搜索树的前提下，通过维护二叉堆的性质来保证其复杂度不会太大，一般我们认为是 (O(log n)) 的单次操作复杂度。但是毕竟是随机的，还是可能会炸，此乃后话。

先声明一点名词：

• 权值：也就是数据，每一个结点保存的数据。

• 优先度：用于维护二叉堆性质，是新建结点的时候随机生成的。

图中我会以二元组的形式给出，格式为 权值，优先度

我一般习惯用大根堆，且优先度为非负数，这样要方便一点

这是一颗很简单的树，我们现在来考虑各种操作。

不过，我还是给出树的声明：

其他的树定义类似！

typedef unsigned int uint;
template
class Treap {
private:
    int lc[N], rc[N]; // 左右节点
    uint pri[N]; // 优先度，定义为非负整数！
    int val[N]; // 权值
    int cnt[N]; // 计数器
    int siz[N]; // 以当前结点为根的子树的结点个数（用于查找kth和rank）
    int root, usage; // 根节点和使用的结点个数
    // int fa[N]; // 记录父亲结点，如果需要的话
public:
    // ...
}

旋转

这里我们记住一张图即可：

从左到右是右旋，从右到左是左旋。

可以发现，这种旋转并不会改变中序遍历的结果（不会影响二叉搜索树的性质）。但是可以影响二叉堆的性质。所以我们可以以此维护二叉堆的性质。

由于我们需要改变 q 或者 p 父节点对其的指向，我们采用引用的方式修改父节点。

后面的Splay也会有旋转的操作，但是两者需要的旋转方式不一样。

这里是将子节点旋转到当前结点 p 上，而splay中的旋转在实现的时候是把当前节点 p 转到父结点上，别混淆了！

void leftRotate(int &p) { // 定义左旋操作
    int q = rc[p];
    rc[p] = lc[q], lc[q] = p;
    p = q; // 更新父节点对此结点的信息
    update(lc[p]), update(p); // 更新结点信息。p已经改变过了！
}

void rightRotate(int &p) { // 定义右旋操作，与上面类似，只是变化了一下lc和rc！
    int q = lc[p];
    lc[p] = rc[q], rc[q] = p, p = q;
    update(rc[p]), update(p);
}

是不是该说一下 update 是个啥？

直接看代码吧：

void update(p) {
    siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p];
}

插入

与二叉搜索树的插入类似。如果遇到已经插入过的结点可以选择新建结点，或者增加标记（++cnt[p]），这里选择后者。

我们先来看新建结点的过程：

int newNode(int x, uint prio = 0) {
    ++usage;
    lc[usage] = rc[usage] = 0;
    pri[usage] = prio ? prio : rand();
    val[usage] = x;
    cnt[usage] = siz[usage] = 1;
    return usage;
}

这只是新建一个空结点的操作而已……接下来我们才涉及到插入部分。

新建结点的操作每一种树都很类似，注意灵活修改！

首先我们还是正常的插入，例如我们在刚开始的例子的基础上插入了 (6, 8)

那么根据二叉搜索树的插入方式，插入后应该如下：

很明显，此时不满足二叉堆的性质，我们需要通过旋转的方法来维护。

不难得知，我们需要对 (7, 7) 做一次右旋操作，以使 (6, 8) 成为 (7, 7) 的父节点，从而满足二叉堆的性质。

结果如下：

接着，由于我们一定是在最底部插入的结点，所以我们只需要在回溯的时候一路向上维护二叉堆的性质即可。

代码如下：

void insert(int &p, int x) { // 由于旋转操作需要来自父节点的引用，新建节点也是！
    if (!p) {
        p = newNode(x); // 新建结点
        return;
    }

    if (val[p] == x) { // 有相同结点，增加引用即可
        ++cnt[p], ++siz[p];
        return;
    } else if (val[p] > x) { // 进入左树
        insert(lc[p], x);
        if (pri[p] 

删除

首先我们先找到需要修改的结点：

void remove(int &p, int x) {
    if (!p) return; // 没有找到要删除的结点
    if (x != val[p]) {
        remove(x 

然后我们考虑两种情况：

• 如果计数大于1，那么我们减少计数，结束即可：

  if (cnt[p] > 1) {
      --cnt[p], --siz[p];
      return;
  }
  

• 如果计数等于1，那么我们不断再保证二叉堆的性质的情况下不断向下旋转。直到没有子节点，那么我们可以直接 p = 0，删除即可。

  if (lc[p] || rc[p]) {
      if (rc[p] == 0 || pri[lc[p]] > pri[rc[p]]) {
          rightRotate(p), remove(rp[p], val);
      } else {
          leftRotate(p), remove(lc[p], val);
      }
  } else {
      p = 0;
  }
  

依据逻辑把三个部分合起来即可。

其他操作

例如查找第k大，获取某个数的排名，获取前驱或者后驱。

和二叉搜索树的方法一致，这里就不过多讲述了。

代码链接

此处采用的是另一种写法！注意甄别！
Link

FHQ-Treap

首先我们了解一下这个东西和普通的Treap有啥不同：

• FHQ-Treap基于分裂和合并的操作，代替了旋转，使得可持久化更为容易

• 操作相对简单，时间复杂度的阶没有变化，还是 (O(log n))，但是常数要大一点

我们先来看最重要的分裂部分

分裂

分裂有两种形式

• 按权值 v 分裂：将小于等于 v 的所有节点分裂为一棵树，大于 v 的放在一棵树

• 按排名 k 分裂：将前 k 个数放在一棵树，其他的放在另一颗树。

两者十分类似，代码几乎一模一样，所以这里只细述按权值分裂。

我们还是拿最初的那张图为例子来讲：

假如我们要按权值 4 分裂，也就相当于分成如下两棵树：

按权值 3 分裂，也就相当于分成如下两棵树：

蓝色的表示新建的边，红色的表示断开的边

似乎有点感觉了？我们来细谈分裂的全过程

约定此处红色为左树（权值小于等于 v），蓝色为右树（权值大于 v），绿色为下一步进入的结点

x 结点指新入的结点需要拼接到的位置，y 同样

这里以按权值 3 分裂为例子：

肯定是从根节点开始，明显，根节点的权值 (gt 3)，所以根节点及其右子树的所有结点都应该放到蓝色树上：

接下来我们判断结点 (3, 8)，明显，节点的权值 (le 3)，所以此节点及其左子树都应该放在红色树上，下一步进入结点 (4, 6)

同样的判断，将 (4, 6) 放置在蓝树

下一步的结点为空，结束分裂。

通过观察，我们可以发现分裂后树的相对形态没有改变，所以我们可以尝试着直接在原树上直接分裂，避免复制结点的操作。

在我的代码中，sync 和其他人写的 pushdown 是一样的，只是我不习惯如此写……所以使用 sync 代替 pushdown，使用 update 代替 pushup……

代码如下：

void splitByVal(int p, int v, int &x, int &y) {
    if (!p) return (void)(x = y = 0);
    // sync(p); // 如果需要，下传标记！！
    if (val[p] 

而按照排名分裂十分类似，这里直接给出代码：

void splitByRand(int p, int k, int &x, int &y) {
    if (!p) return (void)(x = y = 0);
    // sync(p); // 如果需要，下传标记！！
    if (siz[lc[p]] 

合并

由于我们保证了左树的最大值一定不大于右树的最大值，所以我们只需要考虑优先度即可。

那么我们来演示上面分裂后的两棵树合并的过程。

此时 x, y 为左树和右树的当前结点。返回的是合并后的结点编号。

首先，y 的优先度较大，那么此时 y 作为父节点，转而合并 x 和 y 的左子树，作为 y 的左子树：

此时 x 的优先度较大，所以此时 x 作为父节点，合并 x 的右子树和 y，作为 x 的右子树。

此时 x 为空，直接接上即可。

至此，合并完成。

合并会遇到的两种情况这里都涉及到了，那么我们来看代码：

int merge(int x, int y) {
    if (!x | !y) return x | y;
    // sync(x), sync(y); // if need
    if (pri[x] > pri[y]) {
        rc[x] = merge(rc[x], y);
        return update(x), x;
    } else {
        lc[y] = merge(x, lc[y]);
        return update(y), y;
    }
    return -1; // NEVER REACH!
}

其他操作

其他操作很容易通过分裂和合并的操作完成，这里讲述思路即可。

• 插入：新建一个结点作为单独的一棵树，将原树按权值分裂，三者合并即可。

  void insert(int &root, int v) {
      int p = newNode(v);
      int x(0), y(0);
      splitByVal(root, v, x, y);
      root = merge(merge(x, p), y);
  }
  

• 删除：分裂成三棵树，中间的树结点的权值全部为 v，分别合并即可。

  void remove(int &root, int v) {
      int x(0), y(0), z(0), tmp(0);
      splitByVal(root, v - 1, x, tmp); // 分裂为 = v 的两棵树
      splitByVal(tmp, v, y, z); // 再分裂为 = v 和 > v 的两棵树
      // 以此避免判断没有v的情况
      root = merge(merge(x, lc[y]), merge(rc[y], z));
  }
  

• 第 k 大：按排名分裂即可。

• 查询排名：按权值分裂（为 (lt x) 和 (ge x) 的两棵树），使用左树的大小即可。

• 前驱或者后驱：分裂即可……

整体代码我就不给了，核心就这些了。

Splay

伸展树，由Tarjan（对，就是他）在1985年发明。它与正常的平衡树不同，不能保证每一次的操作在 (O(log n)) 的复杂度内，只能均摊下来 (O(log n))。所以说，尽量少用。

Splay最大的特点是每次对一个结点进行操作（读取，或者修改）之后，都会把他转到根节点上。

旋转

我们先来看旋转操作。

还是要记住上面给出的旋转的图，这样方便于理解。这里就不细讲了。

注意和Treap的旋转操作区分开来，这里的旋转是将当前结点旋转到其父节点的位置！

// 0 表示是父节点的左子节点，1表示为右子节点
#define side(x) ((x) == rc[fa[(x)]])
// 利用 side 获取对应的子节点
#define ch(x, k) ((k) ? rc[x] : lc[x])
// rotate x to it's fathers position!
void rotate(int x) {
    int y = fa[x], z = fa[y], k = side(x);
    ch(y, k) = ch(x, k ^ 1);
    if (ch(x, k ^ 1)) fa[ch(x, k ^ 1)] = y;
    ch(x, k ^ 1) = y, fa[y] = x, fa[x] = z;
    if (z) ch(z, y == rc[z]) = x;
    update(y), update(x);
}

在Splay的实现中，update 操作没有变化，还是 siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p]

伸展

伸展是Splay最最核心的操作，也就是把一个结点旋转到根节点（或者其他地方）。

但是仅仅是一路把当前结点向上旋转就可以了吗？并不是的。

如果仅仅是一路向上，那么会有上图的结果，此时我们只需要来回不断地操作，就可以卡成单次 (O(n)) 的复杂度，因此我们不能这么做，所以天才的Tarjan想到了另一种旋转的方法，用以保证其复杂度均摊在 (O(log n))。

对于每一次旋转我们分类讨论：

• 旋转一次可以到达目的地：直接旋转即可。

• 至少需要两次旋转：

  • 当前结点与其父节点为同侧：先转父节点，再转子节点。

  • 不同侧，直接两次向上转即可。

那么通过这个规则，我们就可以得到这样一张图：

是不是矮了一点 ^_

我们可以理解为通过这种规则旋转，每次至多可以减少二分之一的高度，最终下来，高度可以保证在 (O(log n)) 的样子。

所以，伸展的核心代码就可以写出来了：

target指的是向上不停转之后的最终父节点是什么，注意！

void splay(int x, int target) {
    // sync if need!
    // for (int i = x; i; i = fa[i]) stack[++top] = i;
    // while (top) sync(stack[top--]);

    while (fa[x] != target) {
        int y = fa[x], z = fa[y];
        if (z != target) rotate(side(x) == side(y) ? y : x);
        rotate(x);
    }
    if (!target) root = x;
}

其他操作

删除操作非常特殊，后文里会讲，还有，记得每一次无论是查找还是修改什么的，记得把目标节点Splay到根！！！

大部分和二叉搜索树一样。这里不细讲了。

不过这里建议一下Splay的写法细节：

• 写两个辅助函数，一个用于寻找对于排名的结点，一个用于寻找对于值的结点，都是返回的结点编号。

  int _findVal(int v) {
      int cur = root;
      while (cur) {
          // sync(cur); // if need
          if (val[cur] == v) return cur;
          else if (v = k) cur = lc[cur];
          else if (siz[lc[cur]] + 1 == k) return cur;
          else k -= siz[lc[cur]] + 1, cur = rc[cur];
      }
      return cur;
  }
  

• 其他的操作都一定程度上可以基于这两个操作（或者这两个操作的变换）。例如 remove。具体操作看注释

  void remove(int v) {
      int p = _findVal(v);
      if (!p) return;
      splay(p, 0); // 转到根节点
      if (--cnt[p]) return update(p), (void)0; // 减少计数即可
  
      // 如果只有一个子节点，直接作为根节点即可。
      if (!(lc[p] && rc[p])) {
          root = lc[p] | rc[p];
          fa[root] = 0; // 不需要更新！
          return;
      }
  
      // 否则寻找后驱
      int nxt = rc[p]; // sync(nxt); // if need
      while (lc[nxt]) nxt = lc[nxt]/*, sync(nxt) */;
      // 将后驱转到p的右节点的位置
      splay(nxt, p);
      // 此时 lc[nxt] 一定为空，考虑二叉搜索树的性质
      // 所以我们直接把nxt作为根节点，连接原本p的左子树即可。
      lc[nxt] = lc[p];
      update(root = fa[lc[p]] = nxt); // 更新信息
  }
  

其实主要是一些奇怪的操作需要……可恶。

WBLT

这是我最喜欢用的一种平衡树，而且借鉴FHQ-Treap的思路，可以实现类似的操作，这类似的操作这里不细讲。本文只讲述基本。

定义：

• 叶节点：没有子节点的节点。

• 内节点：有子节点的节点。

WBLT全称是 Weight Balanced Tree，有一点类似于 Size Balanced Tree，只是WBLT是一种 Leafy Tree，只有叶节点（没有子节点的结点）保存有信息。而其他的内节点都是用于辅助搜索的。

而且WBLT的每一个节点要么是满的，要么是空的。或者说要么左右儿子都有，要么都没有。再或者说内节点既有左节点也有右节点。这使得操作非常方便……

那么内节点如何辅助搜索？在WBLT中，内节点存储的是右节点的值。

语言描述太罗嗦，我们还是直接上图：

结构还是挺一目了然的。

真正保存着信息的其实只有红色圈起来的节点。

不难看出，总共有9个节点，总而言之，如果有 (n) 个数据，那么将会有 (2n – 1) 个节点。那么我们认为其空间复杂度为 (O(n))，只是常数为普通平衡树的两倍而已。

搜索

这或许是唯一一个需要从搜索开始讲述的平衡树了

例如我们需要搜索值 3，那么搜索路径应该是这样的。

由于WBLT内节点保存信息的特性，我们进入下一个节点可以分如下情况讨论：

• 到达叶子节点：如果当前节点的值等于所需节点的值，那么搜索成功，否则，没有搜到。

• 在内节点上：如果左子节点的值大于等于目标值，则进入左子树，否则进入右子树。

  其实看图不难发现，当前节点的值就是当前子树中的最大值，所以可以进行上述操作。

这个规则同样适用于其他的操作！请务必画下来试一下！

维护平衡

当然还是需要用到旋转的操作。

别忘了那张图！！！

但是在WBLT中旋转的实现又不一样了。

因为内节点并没有保存实际的信息，所以我们只需要 swap 三次，update 两次即可。

对了，我好像还没有讲过 update。

在WBLT中，有所变化：

void update(int p) {
    if (lc[p]) { // 防止更新叶节点
        // sync(p) // if need
        siz[p] = siz[lc[p]] + siz[rc[p]];
        val[p] = val[rc[p]];
    }
}

为了减少代码，采用了一点奇技淫巧：

#define ch(p, k) (k ? rc[p] : lc[p])
// k 0 left to here, k 1 right to her
// k是0则将左子节点旋转到此处，否则右节点旋转到此处。
// 但是这里没有旋转，只是交换节点而已，简化操作。
void rotate(int p, int k) {
    int q = ch(p, k); // sync(q); // sync if need
    if (!p || !q) return;
    swap(lc[q], rc[q]), swap(lc[p], rc[p]);
    swap(ch(q, k ^ 1), ch(p, k));
    fa[ch(p, k)] = p, fa[ch(q, k ^ 1)] = q;
    update(q), update(p);
}

那么我们考虑如何维护平衡：

其实一般来说，WBLT 常数本来就小，所以不需要那么严谨的旋转也可以很好的通过很多题。

// 非严谨写法！！！
void fix(int p) {
    const int ratio = 2;
    if (siz[lc[p]] * ratio 

但是为了严谨，肯定不能就这么水过去，万一有人卡WBLT的常呢？？

所以我们还是要稍微严谨一点。

这一部分感谢大佬的文章：抛弃随机，保持理性——Leafy Tree 到 WBLT – 听风响，闻虫鸣。 – 洛谷博客

在WBLT中，平衡是加权的（并不是严格平衡的），一般来说，我们令平衡因子为 (alpha)。

那么节点 x 平衡意味着 (alpha cdot siz[x] lt min{siz[lc_x], siz[rc_x]})

不难发现，(alpha) 应该 (le 0.5)。

如果所有节点都满足加权平衡，则这棵树是加权平衡的，并且其高度满足  (h le log_{frac 1{1-alpha}}n = O(log n))。而树高正保证了复杂度。

那么应该如何旋转？很明显，在非严谨写法中已经体现出了雏形了：哪一棵子树大就把那一棵子树转上来。

但是观察上图可以知道 b 所在的子树相对位置是不会变的，也就是说如果 (siz_a lt alpha cdot (siz_a + siz_b + siz_c))，并且 (siz_c ，旋转之后任然不满足加权平衡。

所以此时我们应该把 b 向上转一下，然后再进行类似的维护。

这里讲的相对感性，更严谨的证明请参考上面给出的文章

操作类似于：

相当于把 b 阉割成俩，然后分别和 a, c 在一起……

所以我们可以得出如下代码：

#define ch(p, k) (k ? rc[p] : lc[p])
void fix(int p, double ratio = 0.29) {
    int d;
    if (siz[lc[p]] 

插入

还是以上图为例。不妨假设我们需要插入 3，那么自然我们到了原来 3 所在的节点。那么我们如何变成两个呢？

很明显，将当前节点作为父节点，左右节点分别为当前节点的值和新增的值。

记得保证左节点不大于右节点的值

然后回溯更新即可。

void insert(int x) {
    if (!root) {
        root = newNode(x, 0);
        return;
    }

    int cur = root;
    while (true) {
        // sync(cur); // if needed
        if (!lc[cur]) { // new node down here!
            int y = val[cur];
            if (x > y) swap(x, y); // make sure x  val[lc[cur]]) ? rc[cur] : lc[cur];
    }

    while (cur) {
        update(cur), fix(cur);
        cur = fa[cur];
    }
}

删除

我们还是先找到要删除的值所对应的节点吧（任意一个）。

那么我们用其兄弟节点直接替代其父节点即可。

兄弟节点指的是其父节点的另一个子节点

听着很简答吧。在纸上画一下先！！

参考代码：

// 这一块的代码未经编译验证！！可能会有问题
void copyFrom(int p, int q) {
    lc[p] = lc[q], rc[p] = rc[q];
    fa[lc[p]] = fa[rc[p]] = p;
    val[p] = val[q], siz[p] = siz[q];
}

void remove(int p, int x) {
    if (!p) return;
    if (val[lc[p]] >= x) {
        if (siz(lc[p]) == 1 && val[lc[p]] == val) {
            // _del(rc[p]), _del(lc[p]); 标记回收节点，如果需要的话（记得别清空，copyFrom需要用！）
            copyFrom(p, lc[p]);
        } else {
            remove(lc[p], val), update(p), fix(p);
        }
    } else {
        if (siz(rp) == 1 && val(rp) == val) {
            // _del(lp), _del(rp);
            copyFrom(p, rc[p]);
        } else {
            remove(rc[p], val), update(p), fix(p);
        }
    }
}

当然，你也可以写成非递归的形式，这里就不展示了。

其他操作

其实我觉得其他操作都很简单，不想多说，掌握了二叉搜索树的算法，应该自然就会了。

这里就直接展示部分基础操作的代码吧。

// 统计所有 = val) cur = lc[cur];
        else cnt += siz[lc[cur]], cur = rc[cur];
    }
}

int kth(int k) {
    int cur(root);
    while (cur) {
        if (siz[cur] == 1) return k == 1 ? val[cur] : -1; // -1: not found!
        else if (siz[lc[cur]] >= k) cur = lc[cur];
        else k -= siz[lc[cur]], cur = lc[cur];
    }
}

int getpre(int val) {
    return kth(count(val));
}

int getpost(int val) {
    return kth(count(val + 1) + 1);
}

---

到这里，你应该学会了四种在OI中较为常用的平衡树了吧。

那么模板题肯定可以用四种方法过了吧：

• 【模板】普通平衡树 – 洛谷

• 【模板】普通平衡树（数据加强版） – 洛谷

• 【模板】文艺平衡树 – 洛谷

哦，文艺平衡树啊，并不是一种平衡树，它可以通过FHQ-Treap或者Splay实现，拓展的WBLT也可以实现（只是这里没有讲）。

---

附赠各种树速度比较（基于正常平衡树随机数据的操作）：

Splay

+ ?? 阳寿随机种子Treap

更加优化的Treap参考：treap怎样跑得更快 – zx2003 的博客 – 洛谷博客

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net