WBLT

引入

Weight Balanced Leafy Tree，下称 WBLT，是一种平衡树，比起其它平衡树主要有实现简单、常数小的优点。它支持区间操作，而且可持久化。

Weight Balanced Leafy Tree 顾名思义是 Weight Balanced Tree 和 Leafy Tree 的结合。

Weight Balanced Tree 的每个结点储存这个结点下子树的大小，并且通过保持左右子树的大小关系在一定范围来保证树高。

Leafy Tree 维护的原始信息仅存储在树的 叶子节点 上，而非叶子节点仅用于维护子节点信息和维持数据结构的形态。我们熟知的线段树就是一种 Leafy Tree。

本文的树均指的是二叉的 Leafy Tree，即每个节点的子节点数目只能是 或者 。本文中的 ，指的是树的叶子节点的数目。叶子节点数目为 的树，总的节点数量是 ，因此，WBLT 占用的空间是 的。

基本结构及平衡维护

本节介绍 WBLT 的基本结构，定义树的 ‑平衡的概念，并解释如何通过旋转或合并的方式维护树的平衡。

节点信息

要实现一个基本的 WBLT，只需要记录每个节点的如下信息：

• lc[x]、rc[x]：左、右子节点；
• sz[x]：以 为根的子树中的叶子节点的数目。

利用 WBLT 实现平衡树，还需要在每个节点处记录与键值相关的信息：

• val[x]：节点 处的键值。

因为只有叶子节点实际存储键值，所以其他节点处存储的信息是由它们的子节点合并得到的，以方便后续查询。

比如，一种常用的合并方式就是将两个子节点的键值中较大的那个存储于该节点。这样，每个节点存储的就是以它为根的子树中，所有叶子节点的键值的最大值。基于此，节点信息的更新方法如下：

1
2
3
4

void push_up(int x) {
  sz[x] = sz[ch[x][0]] + sz[ch[x][1]];
  val[x] = val[ch[x][1]];
}

当然，如果需要，还可以实现相应的 push_down(x) 函数。

辅助函数

除了基本的节点信息维护外，WBLT 通常还需要实现如下辅助函数，用于内存管理：

• new_node()：新建节点；
• del_node(x)：删除节点 ；
• new_leaf(v)：新建以 为键值的叶子节点；
• join(x, y)：连接子树，即分别以 、 为左右子节点，新建节点 ；
• cut(x)：拆分子树，即获得节点 的两个子节点，并删除节点 。

如果 WBLT 的实现十分依赖于拆分和连接子树，会建立较多的新节点，并释放等量的旧节点。如果不及时回收旧的无用节点，会导致空间不再是线性的。以下是这些辅助函数的数组实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// Return a new empty node.
int new_node() {
  int x = top ? pool[--top] : ++id;
  sz[x] = val[x] = ch[x][0] = ch[x][1] = 0;
  return x;
}

// Release a node for later use.
void del_node(int& x) {
  pool[top++] = x;
  x = 0;
}

// Return a new leaf node of value v.
int new_leaf(int v) {
  int x = new_node();
  val[x] = v;
  sz[x] = 1;
  return x;
}

// Return a new node with subtrees x and y.
int join(int x, int y) {
  int z = new_node();
  ch[z][0] = x;
  ch[z][1] = y;
  push_up(z);
  return z;
}

// Return subtrees of x and release x.
auto cut(int& x) {
  int y = ch[x][0];
  int z = ch[x][1];
  del_node(x);
  return std::make_pair(y, z);
}

封装好这些辅助函数后，数组实现和指针实现在后续函数中就没有区别了。

平衡的概念

对于一个树，可以定义它在一个非叶节点 处的 平衡度 为

其中， 表示以 为根的子树， 表示子树的权重（它的叶子节点的数目），而 和 分别表示 的左右叶子节点。特别地，叶子节点处规定 。

对于 ，如果某个节点 处平衡度 ，就称该节点是 ‑平衡 的。如果树的每个节点处都是 ‑平衡的，就称树是 ‑平衡 的。这样的树的集合记作 。一个树是 ‑平衡 的，当且仅当它本身是 ‑平衡的，且它的左右子树都是 ‑平衡的或者它是叶子节点。

树是 ‑平衡的，有一个显然的好处是，它的高度是 的。这是因为，从叶子节点每向根移动一步，子树所包含的叶子节点数目就至少扩大到原来的 倍，因此只能移动 次。这就保证了在 ‑平衡的树中，单次查询的复杂度总是严格 的，且算法的常数与 （以 为底）正相关。当 位于下文提供的合理范围内时，这个常数大致为 。

WBLT 的平衡维护通常可以通过旋转或合并的方式进行。两种方式实现的 WBLT，单次插入、删除等操作，复杂度都是严格 的。但是，与固定优先级的 Treap 不同，WBLT 的结构并不具有唯一性，因此，两种方式维护得到的树的结构并不相同，虽然这并不影响它们的使用。当然，平衡的维护还可以采取类似 替罪羊树 的策略，利用重构达到均摊 的复杂度，但是这样就失去了 WBLT 可持久化和区间操作等优势，因而并不推荐。

下文分别介绍了通过旋转和合并维护平衡的方法，并实现了相应的平衡维护和合并操作的函数。封装好这些函数后，两种维护树平衡的方式在后续具体的平衡树的实现中再无区别。而且，无论使用哪种方式，单次维护平衡的操作的时间复杂度都是 的，单次合并树 和树 的复杂度都是 的。

通过旋转维护

WBLT 的旋转操作和 Treap 的旋转操作 完全相同，可以采取与 Treap 完全一致的旋转策略。当然，旋转本身同样可以看作是重新分配子树权重的过程，因此也可以利用拆分和连接子树完成。两种实现的结果是完全一致的，但是第二种实现更方便 WBLT 的持久化。

1
2
3
4
5
6
7
8
9

// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int y = ch[x][r];
  ch[x][r] = ch[y][!r];
  ch[y][!r] = x;
  push_up(x);
  push_up(y);
  x = y;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Rotate the subtree at x such that ch[x][r] is the new root.
void rotate(int& x, bool r) {
  int a, b, c, d;
  std::tie(a, b) = cut(x);
  if (r) {
    std::tie(c, d) = cut(b);
    x = join(join(a, c), d);
  } else {
    std::tie(c, d) = cut(a);
    x = join(c, join(d, b));
  }
}

假设在某个树的修改操作后，正在自下而上地恢复树的平衡。现在，左右子树 和 不再平衡，但是它们自身都是平衡的。不妨设右子树 过轻，即 。此时，树的形态如图中左侧的树所示。

一种朴素的平衡维护策略是将 旋转到根节点处，这样它原先的右子节点 就和 一起成为了新树的右子节点，而它原先的左子节点 成为了新树的左子节点。这相当于将原来的树左侧中 的权重移动到它的右侧。如果 的权重合适，这样的操作就可以恢复树的平衡。这样得到的树如图中右侧的树所示。

但是，如果 本身过重，这样的操作可能移动了太多的权重到右子树，从而使得新树中左子树过轻，即 。对于这种情形，因为子树 和子树 的权重都太小，只能考虑将 分拆为两个子树，分别与 和 连接，成为新树的两个子树。这相当于首先将节点 旋转到节点 处，再将它旋转到根节点处。同样，可以期待这样得到的树能够达到平衡，形态如图中上方的树所示。

这两种旋转的策略分别称为单旋和双旋。单旋和双旋策略的选取，主要取决于子树 相对于子树 的比重，即存在阈值 ，使得

• 当 时，应选取单旋策略；
• 当 时，应选取双旋策略。

难点在于阈值 的选择，这就需要做一些具体的计算。Blum 和 Mehlhorn 证明了，对于参数¹

能够通过上述单旋和双旋结合的策略，维护因为单次插入或删除而失衡的 WBLT 的平衡。

证明

需要证明的是，如果树在单次插入或删除后失衡，可以通过上述策略恢复它的平衡。结合上述图示，令

那么，有 。此处还有一个隐含条件，是关于 的取值范围的：

• 如果失衡是由插入单个元素引起的，那么，应该有

  

• 如果失衡是由删除单个元素引起的，那么，应该有

  

因为对于 ，总有 ，所以删除元素会导致比增添元素更严重的失衡，尤其是对于树的规模很小的情形。

接下来，恢复平衡的操作分为两种情形：

情形一： 没有过重，即 时，单旋

首先， 和 平衡。这是因为

左侧表达式在 时总大于 ，右侧表达式在 时总不大于 。

其次， 和 平衡。同样地，考虑

一方面，对于所有 ，有

另一方面，对于所有 ，除了删除元素且 的情形外，都有

所以，有

最后，考虑剩余的情形，即删除元素且 时。最可能失衡的情形发生在 且 时。树可以恢复平衡，当且仅当

而这总是成立的。这就完成了该情形的证明。注意，最后一种情形的证明利用了权重总是整数这一性质，并不能合并到之前的讨论中。

情形二： 过重，即 时，双旋

首先， 和 平衡。这是因为

左侧表达式在 时总大于 ，右侧表达式在 时总小于 。

然后， 和 平衡。这是因为对于 ，总是成立

最后， 和 平衡。类似其他的情形，考虑

一方面，对于所有 ，都有

另一方面，

右侧表达式不小于 ，当且仅当

如果失衡是由插入引起的，那么 ，显然成立。否则，情形有些复杂：

• 当 时，，且 对于所有 都成立；
• 当 时，最可能失衡的情形发生在 ， 且 时，此时 对于所有 都成立；
• 当 时，最可能失衡的情形发生在 ， 且 时，此时 对于所有 都成立。

最后两种情形的讨论，同样利用了所有节点的权重都是整数这一点。

综合两种情形，当 时，前述单旋和双旋结合的策略可以保证树的平衡。

从这个分析过程中可以看出，最难保持平衡的情形发生在从小规模的树中删除节点时。除了 之外，对于其他参数的选择的正确性证明，同样可以重复上述的过程，只是用到的一些不等式需要相应地调整。

随后，Hirai 和 Yamamoto 通过机器证明完整地确定了所有可行的 的范围，结果是一个相当复杂的二维图形：

他们在文章中推荐使用如下策略维持平衡：

• 当 时，判断失衡；
• 当 时，选取单旋策略，否则，选取双旋策略。

原因是，这是可行的参数范围内唯一可以用简单整数表示的策略，从而避免了浮点数运算造成的效率损失。他们推荐的策略相当于取 。实践中，可以根据具体情况，选择合适的参数。

参考实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Check whether a subtree of weight SX is too heavy
//     in a tree of weight SX + SY.
bool too_heavy(int sx, int sy) {
  // or sx > sy * 3;
  return sy < ALPHA * (sx + sy);
}

// Check if ch[x][!r] is too heavy so that a double rotation is needed.
bool need_double_rotation(int x, bool r) {
  // or sz[ch[x][!r]] > sz[ch[x][r]] * 2;
  return sz[ch[x][!r]] > sz[x] / (2 - ALPHA);
}

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  bool r = sz[ch[x][1]] > sz[ch[x][0]];
  if (!too_heavy(sz[ch[x][r]], sz[ch[x][!r]])) return;
  if (need_double_rotation(ch[x][r], r)) {
    rotate(ch[x][r], !r);
  }
  rotate(x, r);
}

实现了维护平衡的策略后，合并两树的算法就非常简单。仍然设 ，合并的策略如下：

• 如果右子树 是空的，直接返回左子树 ；
• 如果左右子树 和 已经平衡，即 ，直接连接两子树；
• 否则，将 的右子树 与 合并，将左子树 与它们合并的结果连接，并调整新树的平衡。

参考实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    int z = join(a, merge(b, y));
    balance(z);
    return z;
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    int z = join(merge(x, a), b);
    balance(z);
    return z;
  } else {
    return join(x, y);
  }
}

可以证明，这样可以维持合并后树的平衡，且这样操作的复杂度是 的。

平衡和复杂度的证明

只需要考虑 过轻的情形，即 。此时，先合并 和 ，再连接 和 。需要证明的是，只要在树根处调整树的平衡，就能够保证树的平衡。假设树 的左、右子树分别是 和 ，且 的左、右子树分别是 和 。在树根处调整平衡，可以分为三种情形：

情形一： 和 已经平衡，无需进一步调整，即

根据平衡的定义，子树 和 都是平衡的，且它们互相也是平衡的，那么整棵树也是平衡的。

情形二： 过轻且 没有过重，可以通过单旋恢复平衡，即 且

此时，因为 和 平衡，但 相较于 过轻，所以，子树 的权重满足

而 的权重则满足

由此， 和 互相平衡，只要

这要求

以及 和 互相平衡，只要

这要求

情形三： 过轻且 过重，可以通过双旋恢复平衡，即 且

类似情形二，有

由此， 和 互相平衡，只要

这要求

其次， 和 互相平衡，只要

这要求

最后， 和 互相平衡，只要

这要求

综合三种情形，只要

就能保证合并后的树可以利用单旋和双旋结合的策略调整到平衡。这显然包含正文给出的参数范围。

最后，简单说明一下该算法的复杂度为什么是 的。合并的流程中，如果 相较于 过轻，就尝试与 的右子树合并，这个过程一直持续到以 某个子孙节点为根的子树与 平衡为止。因为每向下加深一层，子树权重至少变为原来的 ，所以至多只要 次迭代，就能找到与 平衡的子树。因此，该合并算法调用 次平衡算法²，复杂度也就是 。

虽然并不明显，但是这个论证过程依赖于这样一个结论：不断取右子树的过程中， 不会在一次迭代前后，从相较于左侧的子树过轻，变为相较于它过重。这是因为能够与 平衡的子树权重范围位于 与 之间。因此，如果在一次迭代时，就从 过轻变成 过重，则 的子树的权重在该次迭代过程中至少缩小到了原来的 倍。但是，单次迭代，子树权重至多只能缩小到原来的 倍，但是在上述 的范围中，。这说明，前设情形是不可能的，某次迭代之后一定会有 与 的某个子树平衡的情形发生。

通过合并维护

合并两子树是指，保证左子树的键值总是不大于右子树的键值的情况下，建立新树，使其所有叶子节点的信息恰为左右子树叶子节点信息的并，且保证树的平衡。

为此，有如下策略³：（仍然设 ）

• 如果右子树 是空的，直接返回左子树 ；
• 如果左右子树 和 已经平衡，即 ，直接连接两子树；
• 否则，右子树 过轻，但如果 的左子树 和 可以平衡，即 ，就将 和 先合并，再合并 和 ；
• 否则， 和 都过轻，此时，需要首先合并 和 的左子树 ，再合并 的右子树 和 ，再将两次合并的结果 合并 为新树。

将这一策略与前文的平衡策略对比，可以看到后两种情形中节点的组合方式分别和前述平衡策略中单旋和双旋的结果相似，只是将子树的连接换作了合并。

可以证明，当

时，这样得到的树总是平衡的，且这样操作的复杂度是 的。也就是说，合并两个树的成本，与两个树的绝对大小无关，而只与它们的相对大小有关。

平衡和复杂度的证明

设合并权重分别为 和 的两棵子树时，需要直接连接两棵子树的次数为 。严格来说，需要证明当 时，存在常数 ，对于任意 ，都有

其中，；而且，对于所有 ，都有 。实际上，式子中的常数可以取作

这就说明了合并算法的复杂度是 的。

为了证明合并算法得到的树总是平衡的，且上述复杂度的表达式成立，需要使用归纳法。对于所有第一象限的格点 ，可以赋以 的字典序，这显然是该集合上的良序，可以沿着该顺序进行归纳。归纳起点是 ，此时，两子树都只有一个叶子节点，直接连接得到的子树必然是平衡的，且 ，符合上式。下面假设归纳进行到 ，且结论对于所有 之前的点都成立。这分为三种情形：

情形一：树 和 平衡，即

此时，直接连接得到树也是平衡的，且只调用树的连接算法一次，所以有 。

情形二：树 过轻，但是 并不过轻，即

此时，首先合并 和 ，然后合并 和 ，所以

由归纳假设，子树 已经是平衡的。对于第二步合并，其实可以直接证明证明 和 是平衡的：

因此，合并 和 其实是直接连接两个子树，有 。因此，最后得到的树也是平衡的。

现在估计 的大小。因为 且 ，所以，经放缩可知

这说明， 和 不平衡，只出现在 时，所以，有

最后一步的等式成立，是因为 。

因此，有

情形三：树 和 都过轻，即

此时，首先合并 和 ，再合并 和 ，最后合并 和 。因此，

类似前文情形，可以估计每一步合并时两个子树的权重比值。

因为 ，所以 。同时，利用平衡条件，有 。这说明

对于最后一项，有

反过来，有

利用这些不等式，可以说明最后得到的树必然是平衡的。利用归纳假设可知， 和 合并， 和 合并，都可以保证得到的树是平衡的。而且，其中第一步 和 合并实际上是直接连接两棵树。对于树 和树 的合并，又有两种子情形：

• 如果 ，那么它们的权重比值严格大于 ，故而可以直接连接，结果是平衡的；
• 否则，它们的权重比值必然严格小于 ，但是 ，所以 ，由前文给出的字典序判断，这种情形也可以应用归纳假设，结果也是平衡的。

进一步应用归纳假设可知：

三个不等式直接相加，会导致对数项前面的系数变成 ，无法完成归纳。因此，此处需要更为细致的估计。

当 时， 和 中必然有一项为 ，所以，有

否则，应该有

对于 ，有

而且，有

这就说明，对于后面这种情形，也有

整体的合并复杂度为

综合所有情形，有

因此，只要取 ，就可以完成复杂度的归纳。一个显然的选择为

这个常数说明，两个树合并时，直接连接子树的次数大致不会超过树高差值的二倍。