Skip to content

WBLT

Introduction

Weight Balanced Leafy Tree, abbreviated as WBLT, is a balanced tree data structure. Compared to other balanced trees, it has the advantages of simple implementation and small constant factors. It supports interval operations and can be made persistent.

As the name suggests, Weight Balanced Leafy Tree is a combination of Weight Balanced Tree and Leafy Tree.

In a Weight Balanced Tree, each node stores the size of the subtree rooted at that node, and the tree height is controlled by maintaining the size ratio between left and right subtrees within a certain range.

In a Leafy Tree, the original information is stored only in the leaf nodes, while internal nodes are used only to maintain child node information and the structure of the data structure. The well-known segment tree is a type of Leafy Tree.

The trees discussed in this article refer to binary Leafy Trees, meaning each node can have either \(0\) or \(2\) child nodes. In this article, \(n\) refers to the number of leaf nodes in the tree. For a tree with \(n\) leaf nodes, the total number of nodes is \(2n-1\), so the space occupied by a WBLT is \(\Theta(n)\).

Basic Structure and Balance Maintenance

This section introduces the basic structure of WBLT, defines the concept of \(\alpha\)-balance for trees, and explains how to maintain tree balance through rotations or merging.

Node Information

To implement a basic WBLT, only the following information needs to be recorded for each node:

  • lc[x], rc[x]: left and right child nodes;
  • sz[x]: the number of leaf nodes in the subtree rooted at \(x\).

To implement a balanced tree using WBLT, additional key-value related information needs to be recorded at each node:

  • val[x]: the key value at node \(x\).

Since only leaf nodes actually store key values, the information stored at other nodes is merged from their child nodes for convenient subsequent queries.

For example, a common merging method is to store the larger of the two child nodes' key values at the node. Thus, each node stores the maximum key value among all leaf nodes in its subtree. Based on this, the node information update method is as follows:

Reference Code 
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]];
}

Of course, if needed, a corresponding push_down(x) function can also be implemented.

Helper Functions

In addition to basic node information maintenance, WBLT typically requires the following helper functions for memory management:

  • new_node(): create a new node;
  • del_node(x): delete node \(x\);
  • new_leaf(v): create a new leaf node with key value \(v\);
  • join(x, y): join subtrees, i.e., create a new node \(z\) with \(x\) and \(y\) as left and right children respectively;
  • cut(x): split subtree, i.e., obtain the two child nodes of node \(x\) and delete node \(x\).

If the WBLT implementation heavily relies on splitting and joining subtrees, many new nodes will be created and an equal number of old nodes will be released. If old unused nodes are not recycled promptly, the space will no longer be linear. Here are array implementations of these helper functions:

Reference Code 
 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);
}

After encapsulating these helper functions, there is no difference between array implementation and pointer implementation in subsequent functions.

Concept of Balance

For a tree, the balance factor at a non-leaf node \(x\) can be defined as

\[ \rho(x) = \dfrac{\min\{w(T_{\operatorname{left}(x)}),w(T_{\operatorname{right}(x)})\}}{w(T_x)}. \]

Here, \(T_x\) denotes the subtree rooted at \(x\), \(w(\cdot)\) denotes the weight of the subtree (the number of its leaf nodes), and \(\operatorname{left}(x)\) and \(\operatorname{right}(x)\) denote the left and right leaf nodes of \(x\) respectively. Specifically, for leaf nodes, \(\rho(x)=1/2\) is defined.

For \(\alpha\in(0,1/2]\), if the balance factor \(\rho(x)\ge\alpha\) at some node \(x\), the node is said to be \(\alpha\)-balanced. If every node in the tree is \(\alpha\)-balanced, the tree is said to be \(\alpha\)-balanced. The set of such trees is denoted \(BB[\alpha]\). A tree is \(\alpha\)-balanced if and only if it itself is \(\alpha\)-balanced, and its left and right subtrees are either \(\alpha\)-balanced or it is a leaf node.

An obvious advantage of an \(\alpha\)-balanced tree is that its height is \(O(\log n)\). This is because, moving from a leaf node toward the root, the number of leaf nodes contained in the subtree at least multiplies by \(1/(1-\alpha)\) each step, so only \(O(\log_{\frac{1}{1-\alpha}}n) = O(\log n)\) steps can be taken. This ensures that in an \(\alpha\)-balanced tree, the complexity of a single query is strictly \(O(\log n)\), and the algorithm's constant factor is positively correlated with \(\log(1/(1-\alpha))\) (base 2). When \(\alpha\) is within the reasonable range provided below, this constant is roughly \(2\sim 3.5\).

Balance maintenance in WBLT can usually be achieved through rotation or merging. For both implementation methods, the complexity of single operations like insertion and deletion is strictly \(O(\log n)\). However, unlike Treap with fixed priorities, the structure of WBLT is not unique; thus, the tree structures maintained by the two methods are different, although this does not affect their usage. Of course, balance maintenance can also adopt strategies similar to Scapegoat Tree, using reconstruction to achieve amortized \(O(\log n)\) complexity, but this loses the advantages of persistence and interval operations in WBLT, so it is not recommended.

The following sections introduce methods for maintaining balance through rotation and merging respectively, and implement corresponding balance maintenance and merging functions. After encapsulating these functions, the two methods for maintaining tree balance have no further differences in subsequent balanced tree implementations. Moreover, regardless of the method used, the time complexity of a single balance maintenance operation is \(O(1)\), and the complexity of merging trees \(T_1\) and \(T_2\) is \(O\left(\left|\log\dfrac{w(T_1)}{w(T_2)}\right|\right)\).

Notation Omitting Weights

To maintain tree balance, only subtree weight information needs to be retained. Therefore, for convenience, the following sections discussing balance maintenance will mix the notation of a tree and its weight. For example, the weight of subtree \(x\) is also denoted by \(x\), rather than \(w(x)\). Similarly, the tree obtained by merging subtrees \(x\) and \(y\) is also denoted by its weight, directly written as tree \(x+y\).

Maintenance via Rotation

The rotation operation in WBLT is identical to the rotation operation in Treap, and the same rotation strategy as Treap can be adopted. Of course, rotation itself can also be seen as a process of redistributing subtree weights, so it can also be accomplished using subtree splitting and joining. The results of both implementations are completely identical, but the second implementation is more convenient for persistence of WBLT.

Reference Code 
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));
  }
}

Suppose after some tree modification operation, balance is being restored bottom-up. Now, the left and right subtrees \(x\) and \(y\) are no longer balanced, but they themselves are balanced. Assume without loss of generality that the right subtree \(y\) is too light, i.e., \(y<\alpha(x+y)\). At this point, the tree shape is as shown in the left tree in the figure.

A naive balance maintenance strategy is to rotate \(x\) to the root, so its original right child \(w\) together with \(y\) become the new tree's right child, and its original left child \(z\) becomes the new tree's left child. This is equivalent to moving the weight of \(w\) from the left side of the original tree to its right side. If the weight of \(w\) is appropriate, such an operation can restore tree balance. The resulting tree is shown as the right tree in the figure.

However, if \(w\) itself is too heavy, this operation may move too much weight to the right subtree, causing the left subtree in the new tree to be too light, i.e., \(z<\alpha(x+y)\). For this situation, since both subtree \(z\) and subtree \(y\) are too small, we can only consider splitting \(w\) into two subtrees, connecting them with \(z\) and \(y\) respectively to become the two subtrees of the new tree. This is equivalent to first rotating node \(w\) to node \(x\), then rotating it to the root. Similarly, we can expect the resulting tree to achieve balance, as shown in the upper tree in the figure.

These two rotation strategies are called single rotation and double rotation respectively. The choice between single and double rotation mainly depends on the weight ratio of subtree \(w\) relative to subtree \(x\), i.e., there exists a threshold \(\beta\) such that

  • When \(w\le\beta x\), the single rotation strategy should be chosen;
  • When \(w>\beta x\), the double rotation strategy should be chosen.

The difficulty lies in choosing the threshold \(\beta\), which requires some specific calculations. Blum and Mehlhorn proved that for parameters1

\[ \alpha\in\left(\dfrac{2}{11},1-\dfrac{\sqrt{2}}{2}\right]\approx(0.182,0.292],~\beta=\frac{1}{2-\alpha}, \]

the balance of a WBLT that becomes unbalanced due to a single insertion or deletion can be maintained through the combined strategy of single and double rotations described above.

Proof

It needs to be proven that if a tree becomes unbalanced after a single insertion or deletion, its balance can be restored using the above strategy. Combining with the above diagram, let

\[ \rho_1 = \dfrac{y}{x+y}, ~\rho_2 = \dfrac{w}{x}, ~\rho_3 = \dfrac{v}{w}. \]

Then, we have \(\rho_1<\alpha\le\rho_2,\rho_3\le 1-\alpha\). There is also an implicit condition regarding the range of \(\rho_1\):

  • If the imbalance is caused by inserting a single element, then we should have

    \[ \dfrac{y}{x-1+y} \ge \alpha \implies \rho_1 \ge \dfrac{\alpha y}{y+\alpha} \ge \dfrac{\alpha}{1+\alpha}. \]

  • If the imbalance is caused by deleting a single element, then we should have

    \[ \dfrac{y+1}{x+y+1} \ge \alpha \implies \rho_1 \ge \dfrac{\alpha y}{y+1-\alpha} \ge \dfrac{\alpha}{2-\alpha}. \]

Since for \(0<\alpha<1/2\), we always have \(\alpha/(2-\alpha)<\alpha/(1+\alpha)\), deleting an element causes more severe imbalance than adding an element, especially for trees of very small size.

Next, the operation to restore balance is divided into two cases:

Case 1: \(w\) is not too heavy, i.e., \(\rho_2\le\beta\), single rotation

First, \(z\) and \(w+y\) are balanced. This is because

\[ \left(1-\dfrac{\alpha}{2-\alpha}\right)\alpha+\dfrac{\alpha}{2-\alpha} \le \dfrac{w+y}{x+y} = (1-\rho_1)\rho_2+\rho_1 < (1-\alpha)\dfrac{1}{2-\alpha}+\alpha. \]

The left expression is always greater than \(\alpha\) for \(\alpha\in(0,1)\), and the right expression is always not greater than \((1-\alpha)\) for \(\alpha\in(0,1-\sqrt{2}/2]\).

Second, \(w\) and \(y\) are balanced. Similarly, consider

\[ \dfrac{y}{w+y} = \dfrac{\rho_1}{(1-\rho_1)\rho_2+\rho_1}. \]

On one hand, for all \(\alpha\in(0,(3-\sqrt{5})/2)\), we have

\[ \dfrac{y}{w+y} < \dfrac{\alpha}{(1-\alpha)\alpha+\alpha} < 1-\alpha. \]

On the other hand, for all \(\alpha\in(0,1/3)\), except for the case of deleting an element with \(y=1\), we have

\[ \rho_1 \ge \min\left\{\dfrac{\alpha}{1+\alpha},\dfrac{2\alpha}{3-\alpha}\right\} = \dfrac{2\alpha}{3-\alpha}, \]

so we have

\[ \dfrac{y}{w+y} \ge \dfrac{\dfrac{2\alpha}{3-\alpha}}{\left(1-\dfrac{2\alpha}{3-\alpha}\right)\dfrac{1}{2-\alpha}+\dfrac{2\alpha}{3-\alpha}} > \alpha. \]

Finally, consider the remaining case, i.e., when deleting an element and \(y=1\). The most likely imbalance occurs when \(x=\lfloor 2/\alpha\rfloor-2\) and \(w=\lfloor\beta x\rfloor\). The tree can be restored to balance if and only if

\[ \dfrac{1}{1+\lfloor\beta x\rfloor}\ge\alpha \iff \lfloor\beta x\rfloor\le\dfrac{1}{\alpha}-1 \iff \beta x < \dfrac{1}{\alpha} \iff x < \dfrac{2}{\alpha}-1. \]

And this always holds. This completes the proof for this case. Note that the proof for the last case uses the property that weights are always integers and cannot be merged into the previous discussion.

Case 2: \(w\) is too heavy, i.e., \(\rho_2>\beta\), double rotation

First, \(z+u\) and \(v+y\) are balanced. This is because

\[ \dfrac{\alpha}{2-\alpha}+\left(1-\dfrac{\alpha}{2-\alpha}\right)\dfrac{1}{2-\alpha}\alpha < \dfrac{z+u}{x+y} = \rho_1+(1-\rho_1)\rho_2\rho_3 <\alpha+(1-\alpha)^3 \]

The left expression is always greater than \(\alpha\) for \(\alpha\in(0,1)\), and the right expression is always less than \((1-\alpha)\) for \(\alpha\in(0,(3-\sqrt{5})/2)\).

Then, \(z\) and \(u\) are balanced. This is because for \(\alpha\in(0,1)\), we always have

$$ \alpha=\dfrac{\dfrac{1}{2-\alpha}\alpha}{1-\dfrac{1}{2-\alpha}(1-\alpha)}<\dfrac{u}{z} = \dfrac{\rho_2(1-\rho_3)}{1-\rho_2\rho_3} <\dfrac{(1-\alpha)^2}{1-(1-\alpha)\alpha} < 1-\alpha. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
Finally, $v$ and $y$ are balanced. Similar to other cases, consider

$$
\dfrac{y}{v+y} = \dfrac{\rho_1}{\rho_1+(1-\rho_1)\rho_2\rho_3}.
$$

On one hand, for all $\alpha\in(0,1-\sqrt{2}/2]$, we have

$$
\dfrac{y}{v+y} < \dfrac{\alpha}{\alpha+(1-\alpha)\dfrac{1}{2-\alpha}\alpha} \le 1-\alpha.
$$

On the other hand,

$$
\dfrac{y}{v+y} \ge \dfrac{\rho_1}{\rho_1+(1-\rho_1)(1-\alpha)^2}.

The right expression is not less than \(\alpha\) if and only if

\[ \rho_1 \ge \dfrac{\alpha(1-\alpha)}{1+\alpha(1-\alpha)}. \]

If the imbalance is caused by insertion, then \(\rho_1\ge \alpha/(1+\alpha)\), which obviously holds. Otherwise, the situation is more complex:

  • When \(y\ge 3\), \(\rho_1\ge 3\alpha/(4-\alpha)\), and \(3\alpha/(4-\alpha)\ge\alpha(1-\alpha)/(1+\alpha(1-\alpha))\) holds for all \(\alpha\in[1-\sqrt{3}/2,1)\);
  • When \(y=2\), the most likely imbalance occurs when \(x=\lfloor 3/\alpha\rfloor-3\), \(w=\lfloor(1-\alpha)x\rfloor\), and \(v=\lfloor(1-\alpha)w\rfloor\). At this point, \(v/(v+y)\ge\alpha\) holds for all \(\alpha\in(3/22,1)\);
  • When \(y=1\), the most likely imbalance occurs when \(x=\lfloor 2/\alpha\rfloor-2\), \(w=\lfloor(1-\alpha)x\rfloor\), and \(v=\lfloor(1-\alpha)w\rfloor\). At this point, \(v/(v+y)\ge\alpha\) holds for all \(\alpha\in(2/11,1)\).

The discussions for the last two cases also use the fact that all node weights are integers.

Combining the two cases, when \(\alpha\in(2/11,1-\sqrt{2}/2]\), the combined strategy of single and double rotations described above can guarantee tree balance.

From this analysis, it can be seen that the most difficult situation to maintain balance occurs when deleting nodes from small-scale trees. Besides \(\beta=1/(2-\alpha)\), the correctness proof for other parameter choices can also repeat the above process, only requiring adjustments to some inequalities used.

Subsequently, Hirai and Yamamoto fully determined all feasible \((\alpha,\beta)\) ranges through machine proof, resulting in a rather complex two-dimensional shape:

In their article, they recommend using the following strategy to maintain balance:

  • When \(x>3y\), judge imbalance;
  • When \(w\le 2z\), choose the single rotation strategy; otherwise, choose the double rotation strategy.

The reason is that this is the only strategy within the feasible parameter range that can be expressed with simple integers, thus avoiding efficiency loss due to floating-point operations. Their recommended strategy corresponds to taking \((\alpha,\beta)=(1/4,2/3)\). In practice, appropriate parameters can be chosen based on specific situations.

Reference implementation is as follows:

Reference Code 
 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);
}

After implementing the balance maintenance strategy, the algorithm for merging two trees becomes very simple. Still assuming \(x>y\), the merging strategy is as follows:

  • If the right subtree \(y\) is empty, directly return the left subtree \(x\);
  • If the left and right subtrees \(x\) and \(y\) are already balanced, i.e., \(y\ge\alpha(x+y)\), directly join the two subtrees;
  • Otherwise, merge the right subtree \(w\) of \(x\) with \(y\), then join the left subtree \(z\) with the result of their merger, and adjust the balance of the new tree.

Reference implementation is as follows:

Reference Code 
 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);
  }
}

It can be proven that this maintains the balance of the merged tree, and the complexity of this operation is \(O(|\log(x/y)|)\).

Proof of Balance and Complexity

We only need to consider the case where \(y\) is too light, i.e., \(y<\alpha(x+y)\). At this point, first merge \(w\) and \(y\), then join \(z\) and \(w+y\). What needs to be proven is that as long as we adjust the tree balance at the root, we can guarantee the tree's balance. Assume the left and right subtrees of tree \(w+y\) are \(c\) and \(d\) respectively, and the left and right subtrees of \(c\) are \(a\) and \(b\) respectively. Adjusting balance at the root can be divided into three cases:

Case 1: \(z\) and \(w+y\) are already balanced, no further adjustment needed, i.e., \(z\ge\alpha(x+y)\)

According to the definition of balance, subtree \(z\) and \(w+y\) are both balanced, and they are also balanced with each other, so the entire tree is balanced.

Case 2: \(z\) is too light and \(c\) is not too heavy, balance can be restored by single rotation, i.e., \(z<\alpha(x+y)\) and \(c\le\beta(w+y)\)

At this point, because \(z\) and \(w\) are balanced, but \(y\) is too light compared to \(x = z+w\), the weight of subtree \(z\) satisfies

\[ \alpha(1-\alpha)(x+y) < \alpha(z+w) \le z \le \alpha(x+y) . \]

And the weight of \(c\) satisfies

\[ \alpha(w+y) \le c \le \beta(w+y). \]

Thus, \(z\) and \(c\) are balanced with each other, as long as

\[ \dfrac{\alpha}{1-\alpha}<\dfrac{1-\alpha}{\alpha}\alpha<\dfrac{c}{z}=\dfrac{w+y}{z}\dfrac{c}{w+y} < \dfrac{1-\alpha(1-\alpha)}{\alpha(1-\alpha)}\beta\le\dfrac{1-\alpha}{\alpha}, \]

which requires

\[ \beta\le \dfrac{(1-\alpha)^2}{1-\alpha(1-\alpha)}. \]

And \(z+c\) and \(d\) are balanced with each other, as long as

\[ \alpha\le (1-\beta)(1-\alpha)\le \dfrac{d}{w+y}\dfrac{w+y}{x+y} = \dfrac{d}{x+y} < \dfrac{d}{c+d} \le 1-\alpha, \]

which requires

\[ \beta \le \dfrac{1-2\alpha}{1-\alpha}. \]
Case 3: \(z\) is too light and \(c\) is too heavy, balance can be restored by double rotation, i.e., \(z<\alpha(x+y)\) and \(c>\beta(w+y)\)

Similar to case 2, we have

\[ \begin{aligned} \alpha(1-\alpha)(x+y) < z &\le \alpha(x+y),\\ \beta(w+y)<c &\le (1-\alpha)(w+y),\\ \alpha c\le a,b &\le (1-\alpha)c. \end{aligned} \]

Thus, \(z\) and \(a\) are balanced with each other, as long as

\[ \dfrac{\alpha}{1-\alpha}\le\dfrac{1-\alpha}{\alpha}\beta\alpha\le\dfrac{a}{z} = \dfrac{w+y}{z}\dfrac{a}{c+d} < \dfrac{1-\alpha(1-\alpha)}{\alpha(1-\alpha)}(1-\alpha)^2, \]

which requires

\[ \beta\ge\dfrac{\alpha}{(1-\alpha)^2}. \]

Second, \(b\) and \(d\) are balanced with each other, as long as

\[ \dfrac{\alpha}{1-\alpha}\le\dfrac{\beta}{1-\beta}\alpha \le \dfrac{b}{d} = \dfrac{c}{d}\dfrac{b}{c} \le \dfrac{1-\alpha}{\alpha}(1-\alpha) < \dfrac{1-\alpha}{\alpha}, \]

which requires

\[ \beta\ge\dfrac{1}{2-\alpha}. \]

Finally, \(z+a\) and \(b+d\) are balanced with each other, as long as

\[ \alpha<(1-\alpha)(1-(1-\alpha)^2)\le\frac{b+d}{x+y} = \dfrac{w+y}{x+y}\dfrac{b+d}{w+y} < (1-\alpha(1-\alpha))(1-\beta\alpha) \le 1-\alpha, \]

which requires

\[ \beta\ge\dfrac{\alpha}{1-\alpha+\alpha^2}. \]

Combining the three cases, as long as

\[ 0<\alpha\le 1-\dfrac{\sqrt{2}}{2},~\dfrac{1}{2-\alpha}\le\beta\le\dfrac{1-2\alpha}{1-\alpha}, \]

it can be guaranteed that the merged tree can be adjusted to balance using the combined strategy of single and double rotations. This clearly includes the parameter range given in the main text.

Finally, a brief explanation of why the complexity of this algorithm is \(O(|\log(x/y)|)\). In the merging process, if \(y\) is too light compared to \(x\), we try to merge it with the right subtree of \(x\). This process continues until a subtree rooted at some descendant of \(x\) becomes balanced with \(y\). Since each level deeper reduces the subtree weight to at most \((1-\alpha)\) of the previous level, at most \(\log_{\frac{1}{1-\alpha}}(x/y)\) iterations are needed to find a subtree balanced with \(y\). Therefore, this merging algorithm calls the balance algorithm \(O(\log n)\) times3, and its complexity is also \(O(\log n)\).

Although not obvious, this argument relies on the conclusion that during the process of repeatedly taking right subtrees, \(y\) will not change from being too light compared to the left subtree to being too heavy compared to it in a single iteration. This is because the weight range of a subtree that can be balanced with \(y\) lies between \(\alpha y/(1-\alpha)\) and \((1-\alpha)y/\alpha\). Therefore, if in one iteration, \(y\) changes from being too light to being too heavy, then the weight of \(x\)'s subtree must have shrunk to at most \(\alpha^2/(1-\alpha)^2\) times its original value during that iteration. However, a single iteration can only shrink the subtree weight to at most \(\alpha\) times its original value, and within the \(\alpha\) range above, \(\alpha>\alpha^2/(1-\alpha)^2\). This indicates that the assumed situation is impossible; after some iteration, there must be a situation where \(y\) is balanced with some subtree of \(x\).

Maintenance via Merging

Merging two subtrees refers to constructing a new tree under the condition that the key values in the left subtree are always not greater than those in the right subtree, such that all leaf node information of the new tree is exactly the union of the leaf node information of the left and right subtrees, while maintaining tree balance.

For this purpose, there is the following strategy2: (still assuming \(x>y\))

  • If the right subtree \(y\) is empty, directly return the left subtree \(x\);
  • If the left and right subtrees \(x\) and \(y\) are already balanced, i.e., \(y\ge\alpha(x+y)\), directly join the two subtrees;
  • Otherwise, the right subtree \(y\) is too light, but if \(x\)'s left subtree \(z\) and \(w+y\) can be balanced, i.e., \(z\ge\alpha(x+y)\), first merge \(w\) and \(y\), then merge \(z\) and \(w+y\);
  • Otherwise, both \(z\) and \(y\) are too light. At this point, we need to first merge \(z\) and \(w\)'s left subtree \(u\), then merge \(w\)'s right subtree \(v\) and \(y\), and then merge the results of the two merges into a new tree.

Comparing this strategy with the previous balance strategy, we can see that the node combinations in the latter two cases are similar to the results of single and double rotations in the previous balance strategy, except that subtree joining is replaced by merging.

It can be proven that when

\[ 0<\alpha \le 1-\dfrac{\sqrt{2}}{2}\approx 0.292 \]

the resulting tree is always balanced, and the complexity of this operation is \(O(|\log(x/y)|)\). That is, the cost of merging two trees is independent of their absolute sizes and depends only on their relative sizes.

Proof of Balance and Complexity

Let \(\tau(x,y)\) be the number of times two subtrees with weights \(x\) and \(y\) need to be directly joined during merging. Strictly speaking, we need to prove that when \(0<\alpha\le 1-\sqrt{2}/2\), there exists a constant \(C>0\) such that for any \(x>y>0\), we have

\[ \tau(x,y) \le 1+C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}, \]

where \(\log^+ x = \max\{0,\log x\}\); and for all \(x/y\le(1-\alpha)/\alpha\), we have \(\tau(x,y)=1\). In fact, the constant in the expression can be taken as

\[ C = -\dfrac{2}{\log(1-\alpha)}. \]

This shows that the complexity of the merging algorithm is \(O(|\log(x/y)|)\).

To prove that the tree obtained by the merging algorithm is always balanced and that the above complexity expression holds, we need to use induction. For all lattice points \((x,y)\in\mathbf N^2_+\) in the first quadrant, we can assign the lexicographic order \((x+y,|x-y|)\), which is clearly a well-order on this set, allowing induction along this order. The induction base is \((x,y)=(1,1)\). At this point, both subtrees have only one leaf node, and the subtree obtained by direct joining must be balanced, with \(\tau(x,y)=1\), satisfying the above expression. Now assume induction proceeds to \((x,y)\), and the conclusion holds for all points before \((x,y)\). This is divided into three cases:

Case 1: Trees \(x\) and \(y\) are balanced, i.e., \(y\ge\alpha(x+y)\)

At this point, the tree obtained by direct joining is also balanced, and only the tree joining algorithm is called once, so \(\tau(x,y)=1\).

Case 2: Tree \(y\) is too light, but \(z\) is not too light, i.e., \(y<\alpha(x+y)\le z\)

At this point, first merge \(w\) and \(y\), then merge \(z\) and \(w+y\), so

\[ \tau(x,y) = \tau(w,y) + \tau(z,w+y). \]

By the induction hypothesis, subtree \(w+y\) is already balanced. For the second merge, we can actually directly prove that \(z\) and \(w+y\) are balanced:

\[ \alpha \le \dfrac{z}{z+(w+y)} = \dfrac{z}{x+y} < \dfrac{z}{z+w} \le 1-\alpha. \]

Therefore, merging \(z\) and \(w+y\) is actually directly joining two subtrees, so \(\tau(z,w+y) = 1\). Thus, the final tree is also balanced.

Now estimate the size of \(\tau(w,y)\). Since \(y>(\alpha/(1-\alpha))x\) and \(\alpha x\le w\le(1-\alpha)x\), we have after scaling

\[ \dfrac{\alpha}{1-\alpha}<1-\alpha=\dfrac{\alpha x}{(\alpha/(1-\alpha))x}< \dfrac{w}{y} \le \dfrac{(1-\alpha)x}{y}. \]

This shows that \(w\) and \(y\) are unbalanced only when \(w>y\), so we have

\[ \begin{aligned} \tau(w,y) &\le 1+C\log^+\dfrac{\alpha w}{(1-\alpha)^2y} \le 1+C\log^+\dfrac{\alpha x}{(1-\alpha)y} \\ &= 1 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}. \end{aligned} \]

The equality in the last step holds because \(x/y>(1-\alpha)/\alpha\).

Therefore, we have

$$ \tau(x,y) \le 2 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}. ```

Case 3: Both trees \(y\) and \(z\) are too light, i.e., \(y,z<\alpha(x+y)\)

At this point, first merge \(z\) and \(u\), then merge \(v\) and \(y\), and finally merge \(z+u\) and \(v+y\). Therefore,

\[ \tau(x,y) = \tau(z,u) + \tau(v,y) + \tau(z+u,v+y). \]

Similar to the previous case, we can estimate the weight ratio of the two subtrees at each merge step.

Since \(z,y<\alpha(x+y)\), we have \(w>(1-2\alpha)(x+y)\). Also, using the balance condition, we have \(\alpha\le z/x,w/x,u/w,v/w\le 1-\alpha\). This shows

\[ \begin{aligned} \dfrac{\alpha}{1-\alpha}<\dfrac{\alpha}{1-\alpha}\frac{1}{1-\alpha}\le \dfrac{z}{u} &= \dfrac{z}{w}\dfrac{w}{u} < \dfrac{\alpha}{1-2\alpha}\dfrac{1}{\alpha} \le \dfrac{1-\alpha}{\alpha},\\ \dfrac{\alpha}{1-\alpha}\le\alpha\dfrac{1-2\alpha}{\alpha}< \dfrac{v}{y} &= \dfrac{v}{w}\dfrac{w}{y} \le (1-\alpha)\dfrac{(1-\alpha)x}{y} = (1-\alpha)^2\dfrac{x}{y}. \end{aligned} \]

For the last term, we have

\[ \dfrac{z+u}{v+y} = \dfrac{x+y}{v+y}-1 = \dfrac{x+y}{y}\dfrac{y}{v+y} - 1 < (1-\alpha)\left(\dfrac{x}{y}+1\right)-1 < (1-\alpha)\dfrac{x}{y}. \]

Conversely,

$$ \dfrac{z+u}{v+y} = \dfrac{x+y}{v+y}-1 \ge \dfrac{x+y}{(1-\alpha)^2x+y}-1 > \dfrac{1}{(1-\alpha)^3+\alpha}-1 > \dfrac{\alpha}{1-\alpha}. 

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Using these inequalities, we can show that the final tree must be balanced. By the induction hypothesis, merging $z$ and $u$, and merging $v$ and $y$, can both guarantee that the resulting trees are balanced. Moreover, the first step of merging $z$ and $u$ is actually directly joining two trees. For merging tree $z+u$ and tree $v+y$, there are two subcases:

-   If $z+u\le v+y$, then their weight ratio is strictly greater than $\alpha/(1-\alpha)$, so they can be directly joined, and the result is balanced;
-   Otherwise, their weight ratio must be strictly less than $x/y$, but $(z+u)+(v+y)=x+y$, so $|(z+u)-(v+y)|<|x-y|$. By the lexicographic order judgment given earlier, this case can also apply the induction hypothesis, and the result is also balanced.

Further applying the induction hypothesis, we have:

$$
\begin{aligned}
\tau(z,u) &= 1,\\
\tau(v,y) &\le 1+C\log^+\dfrac{\alpha x}{y},\\
\tau(z+u,v+y) &\le 1 + C\log^+\dfrac{\alpha x}{(1-\alpha)y}.
\end{aligned}
$$

Directly adding the three inequalities would cause the coefficient before the logarithmic term to become $2C$, preventing completion of the induction. Therefore, a more refined estimate is needed here.

When $\max\{v/y,(z+u)/(v+y)\}\le(1-\alpha)/\alpha$, one of $\tau(v,y)$ and $\tau(z+u,v+y)$ must be $1$, so we have

$$
\begin{aligned}
\tau(v,y) + \tau(z+u,v+y) &\le 2 + C\log^+\dfrac{\alpha x}{(1-\alpha)y}\\
&= 2 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}.
\end{aligned}
$$

Otherwise, we should have

$$
\begin{aligned}
\tau(v,y) + \tau(z+u,v+y) 
&\le 2 + C\log^+\dfrac{\alpha v}{(1-\alpha)^2y} + C\log^+\dfrac{\alpha(z+u)}{(1-\alpha)^2(v+y)}\\
&= 2 + C\log\dfrac{\alpha}{(1-\alpha)^2} + C\log^+\dfrac{\alpha v(z+u)}{(1-\alpha)^2y(v+y)}.
\end{aligned}
$$

For $0<\alpha\le 1-\sqrt{2}/2$, we have

$$
\dfrac{\alpha}{(1-\alpha)^2} < 1-\alpha.
$$

Moreover,

$$
\begin{aligned}
\dfrac{v(z+u)}{y(v+y)} &= \left(\dfrac{v+y}{y}-1\right)\left(\dfrac{x+y}{y}\dfrac{y}{v+y} - 1\right) \\
&= \dfrac{x+y}{y} + 1 -\dfrac{x+y}{y}\dfrac{y}{v+y}-\dfrac{v+y}{y} < \dfrac{x}{y}.
\end{aligned}
$$

This shows that for the latter case, we also have

$$
\tau(v,y) + \tau(z+u,v+y) < 2 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}.

The overall merging complexity is

$$ \tau(x,y) \le 3 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}. ```

Combining all cases, we have

\[ \tau(x,y) \le 3 + C\log(1-\alpha) + C\log^+\dfrac{\alpha x}{(1-\alpha)^2y}. \]

Therefore, as long as we take \(2+C\log(1-\alpha)\le 0\), the complexity induction can be completed. An obvious choice is

\[ C = -\dfrac{2}{\log(1-\alpha)}. \]

This constant indicates that when merging two trees, the number of times subtrees are directly joined roughly does not exceed twice the difference in tree heights.

Reference implementation is as follows:

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Merge two subtrees.
int merge(int x, int y) {
  if (!x || !y) return x | y;
  int a, b, c, d;
  if (too_heavy(sz[x], sz[y])) {
    std::tie(a, b) = cut(x);
    if (too_heavy(sz[b] + sz[y], sz[a])) {
      std::tie(c, d) = cut(b);
      return merge(merge(a, c), merge(d, y));
    } else {
      return merge(a, merge(b, y));
    }
  } else if (too_heavy(sz[y], sz[x])) {
    std::tie(a, b) = cut(y);
    if (too_heavy(sz[a] + sz[x], sz[b])) {
      std::tie(c, d) = cut(a);
      return merge(merge(x, c), merge(d, b));
    } else {
      return merge(merge(x, a), b);
    }
  } else {
    return join(x, y);
  }
}

Using this merging strategy, tree balance maintenance can also be easily implemented: when unbalanced, simply merge the left and right subtrees.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  if (too_heavy(sz[ch[x][0]], sz[ch[x][1]]) ||
      too_heavy(sz[ch[x][1]], sz[ch[x][0]])) {
    int a, b;
    std::tie(a, b) = cut(x);
    x = merge(a, b);
  }
}

Since the two trees that need rebalancing are always nearly balanced, the complexity of maintaining balance is \(O(1)\).

Basic Balanced Tree Operations

Using the functions implemented earlier, WBLT can support all basic balanced tree operations. This section uses a multiset as an example to discuss methods for implementing balanced trees with WBLT.

Building a Tree

The tree-building operation is very similar to a segment tree. We only need to recursively bisect the interval downward until the interval length is \(1\), place the information to be maintained on the leaf node, and merge interval information when backtracking.

Reference Code 
1
2
3
4
5
6
// Build the tree for the interval [ll, rr].
int build(int ll, int rr) {
  if (ll == rr) return new_leaf(ll);
  int mm = (ll + rr) / 2;
  return join(build(ll, mm), build(mm + 1, rr));
}

Time complexity is \(O(n)\).

Insertion and Deletion

For insertion, we need to start from the root node and recursively descend until we find the leaf node with the smallest key value greater than or equal to the element to be inserted. Then create two new nodes: one to store the newly inserted value, and the other as the new parent of the two leaves, replacing the position of this minimum leaf node, and then connect these two leaves to this parent. When backtracking, we need to maintain tree balance.

As shown in the figure, we want to insert an element with value \(4\) into the left tree. First, find the leaf node with value \(5\), then create leaf node \(4\) and non-leaf node \(\text{d}\), and connect \(4\) and \(5\) to \(\text{d}\). This gives the right tree.

For deletion, consider the inverse process of the above. That is, find a leaf node with a key value equal to the value to be deleted, delete it and its parent node, and replace the parent's position with the other child of the parent. When backtracking, similarly maintain tree balance.

Reference implementation is as follows:

Reference Code 
 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
38
39
40
41
42
43
44
45
// Insert v to the subtree at x.
void insert(int& x, int v) {
  if (!x) {
    x = new_leaf(v);
  } else if (sz[x] == 1) {
    bool r = v >= val[x];
    ch[x][r] = new_leaf(v);
    ch[x][!r] = new_leaf(val[x]);
    push_up(x);
  } else {
    bool r = v > val[ch[x][0]];
    insert(ch[x][r], v);
    push_up(x);
    balance(x);
  }
}

// Insert v.
void insert(int v) { insert(rt, v); }

// Remove v from the subtree at x.
bool remove(int& x, int v) {
  if (!x) return false;
  if (sz[x] == 1) {
    if (val[x] == v) {
      del_node(x);
      return true;
    } else {
      return false;
    }
  } else {
    bool r = v > val[ch[x][0]];
    bool succ = remove(ch[x][r], v);
    if (!ch[x][r]) {
      x = ch[x][!r];
    } else {
      push_up(x);
      balance(x);
    }
    return succ;
  }
}

// Remove v.
bool remove(int v) { return remove(rt, v); }

Note the handling of empty trees. If you don't want to handle empty trees, you can insert an \(\infty\) element into the tree in advance.

The time complexity of both operations is \(O(\log n)\).

Querying Rank

Because the structure of WBLT is very similar to a segment tree, querying rank can use a method similar to binary search on a segment tree: if the maximum value of the left subtree is greater than or equal to the value being queried, jump to the left child; otherwise, jump to the right child, while adding the weight of the left subtree to the answer.

Reference implementation is as follows:

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// Count the number of nodes less than v in the subtree at x.
int count_less_than(int x, int v) {
  if (!x) return 0;
  int res = 0;
  while (sz[x] > 1) {
    if (val[ch[x][0]] < v) {
      res += sz[ch[x][0]];
      x = ch[x][1];
    } else {
      x = ch[x][0];
    }
  }
  return res + (val[x] < v ? 1 : 0);
}

// Find the rank of v.
int find_rank(int v) { return count_less_than(rt, v) + 1; }

Time complexity is \(O(\log n)\).

Querying by Rank

Again using the idea of binary search on a segment tree, but here we compare node weights.

Reference implementation is as follows:

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// Find the k-th element in the subtree at x.
// It is guaranteed that such an element exists.
int find_kth(int x, int k) {
  while (sz[x] > 1) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else {
      k -= sz[ch[x][0]];
      x = ch[x][1];
    }
  }
  return val[x];
}

// Find the k-th element.
int find_kth(int k) { return k > sz[rt] || k <= 0 ? -1 : find_kth(rt, k); }

Time complexity is \(O(\log n)\).

Finding Predecessor and Successor

The above two functions can be combined.

Reference implementation is as follows:

Reference Code 
1
2
3
4
5
// Find the predecessor of v.
int find_prev(int v) { return find_kth(find_rank(v) - 1); }

// Find the successor of v.
int find_next(int v) { return find_kth(find_rank(v + 1)); }

If you want to implement directly, note that nodes with the same key value may be stored in multiple leaf nodes.

Split Operation

Splitting in WBLT is similar to Treap without rotation, deciding to recursively split the left or right subtree based on subtree size or key value. The difference is that WBLT needs to merge the split subtrees to maintain the balance of the final split trees.

Reference implementation for splitting by subtree size is as follows:

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// Split the subtree at x.
// The left half will have k elements.
std::pair<int, int> split(int x, int k) {
  if (!x) return {0, 0};
  if (!k) return {0, x};
  if (k == sz[x]) return {x, 0};
  int a, b;
  std::tie(a, b) = cut(x);
  if (k <= sz[a]) {
    int ll, rr;
    std::tie(ll, rr) = split(a, k);
    return {ll, merge(rr, b)};
  } else {
    int ll, rr;
    std::tie(ll, rr) = split(b, k - sz[a]);
    return {merge(a, ll), rr};
  }
}

Time complexity is \(O(\log n)\).

Complexity Proof

The number of recursive descent levels clearly does not exceed the tree height, which is \(O(\log n)\). What needs to be proven is that the complexity of merging the split subtrees on the left and right sides respectively is \(O(\log n)\). Consider only the left side subtrees, as the right side is symmetric. Let the subtrees split from the left side from bottom to top be \(T_1,T_2,\cdots,T_\ell\), with the number of these subtrees \(\ell\in O(\log n)\). The merging process can be described as starting from \(T'_1=T_1\), merging \(T'_{i-1}\) with \(T_i\) to get \(T'_i\), recursively merging all subtrees. The total merging complexity can be expressed as

\[ \sum_{i=2}^\ell \tau(T_i,T'_{i-1}), \]

where \(\tau(T_i,T'_{i-1})\) is the complexity of merging \(T_i\) and \(T'_{i-1}\).

If we always have \(w(T_i)\ge w(T'_{i-1})\), then according to the complexity expression for merging two subtrees, we have

\[ \tau(T_i,T'_{i-1}) \in O\left(\log\dfrac{w(T_i)}{w(T'_{i-1})}\right) \subseteq O\left(\log\dfrac{w(T'_i)}{w(T'_{i-1})}\right). \]

Since the constants in these big O notations are consistent, they can be directly added and telescoped.

However, it should be noted that \(w(T_i)\ge w(T'_{i-1})\) does not always hold, because \(T'_{i-1}\) is split from the right subtree corresponding to \(T_i\) in the original tree, and this right subtree may be larger than the left subtree \(T_i\). Nevertheless, even if \(T'_{i-1}\) is larger than \(T_i\), as part of the right subtree, the weight \(w(T'_{i-1})\) will not exceed \((1-\alpha)/\alpha\) times \(w(T_i)\), meaning that at this point \(T'_{i-1}\) and \(T_i\) must be balanced, and the merging complexity is \(O(1)\).

Summarizing these two situations, the complexity of a single merge can be written as

\[ \tau(T_i,T'_{i-1}) \in O\left(\log\dfrac{w(T'_i)}{w(T'_{i-1})}\right) + O(1). \]

Thus, the total merging complexity is

\[ O\left(\sum_{i=2}^\ell\left( 1+\log\dfrac{w(T'_i)}{w(T'_{i-1})}\right) \right) \subseteq O(\ell+\log w(T'_\ell)) \subseteq O(\log n). \]

This also shows that the total complexity of the split algorithm is \(O(\log n)\).

Reference Implementation

This article has introduced how to use WBLT to complete basic balanced tree operations. Below is a WBLT implementation of the Ordinary Balanced Tree Template.

Reference Code 
  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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
#include <iostream>
#include <tuple>

// Change here to use different strategies to balance and to merge.
#define BALANCE_BY_ROTATING 1
#define ROTATE_BY_JOINING 0

constexpr int N = 2e6;
constexpr double ALPHA = 0.292;

int id, rt, ch[N][2], sz[N], val[N];
int pool[N], top;

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

// 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);
}

// 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);
}

#if BALANCE_BY_ROTATING

#if ROTATE_BY_JOINING

// 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));
  }
}

#else

// 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;
}

#endif

// 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);
}

// 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);
  }
}

#else

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

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  if (too_heavy(sz[ch[x][0]], sz[ch[x][1]]) ||
      too_heavy(sz[ch[x][1]], sz[ch[x][0]])) {
    int a, b;
    std::tie(a, b) = cut(x);
    x = merge(a, b);
  }
}

#endif

// Insert v to the subtree at x.
void insert(int& x, int v) {
  if (!x) {
    x = new_leaf(v);
  } else if (sz[x] == 1) {
    bool r = v >= val[x];
    ch[x][r] = new_leaf(v);
    ch[x][!r] = new_leaf(val[x]);
    push_up(x);
  } else {
    bool r = v > val[ch[x][0]];
    insert(ch[x][r], v);
    push_up(x);
    balance(x);
  }
}

// Insert v.
void insert(int v) { insert(rt, v); }

// Remove v from the subtree at x.
bool remove(int& x, int v) {
  if (!x) return false;
  if (sz[x] == 1) {
    if (val[x] == v) {
      del_node(x);
      return true;
    } else {
      return false;
    }
  } else {
    bool r = v > val[ch[x][0]];
    bool succ = remove(ch[x][r], v);
    if (!ch[x][r]) {
      x = ch[x][!r];
    } else {
      push_up(x);
      balance(x);
    }
    return succ;
  }
}

// Remove v.
bool remove(int v) { return remove(rt, v); }

// Count the number of nodes less than v in the subtree at x.
int count_less_than(int x, int v) {
  if (!x) return 0;
  int res = 0;
  while (sz[x] > 1) {
    if (val[ch[x][0]] < v) {
      res += sz[ch[x][0]];
      x = ch[x][1];
    } else {
      x = ch[x][0];
    }
  }
  return res + (val[x] < v ? 1 : 0);
}

// Find the rank of v.
int find_rank(int v) { return count_less_than(rt, v) + 1; }

// Find the k-th element in the subtree at x.
// It is guaranteed that such an element exists.
int find_kth(int x, int k) {
  while (sz[x] > 1) {
    if (sz[ch[x][0]] >= k) {
      x = ch[x][0];
    } else {
      k -= sz[ch[x][0]];
      x = ch[x][1];
    }
  }
  return val[x];
}

// Find the k-th element.
int find_kth(int k) { return k > sz[rt] || k <= 0 ? -1 : find_kth(rt, k); }

// Find the predecessor of v.
int find_prev(int v) { return find_kth(find_rank(v) - 1); }

// Find the successor of v.
int find_next(int v) { return find_kth(find_rank(v + 1)); }

int main() {
  int n;
  std::cin >> n;
  for (; n; --n) {
    int op, x;
    std::cin >> op >> x;
    switch (op) {
      case 1:
        insert(x);
        break;
      case 2:
        remove(x);
        break;
      case 3:
        std::cout << find_rank(x) << '\n';
        break;
      case 4:
        std::cout << find_kth(x) << '\n';
        break;
      case 5:
        std::cout << find_prev(x) << '\n';
        break;
      case 6:
        std::cout << find_next(x) << '\n';
        break;
    }
  }
  return 0;
}

Using merging and splitting, a literary balanced tree can also be implemented. Below is a WBLT implementation of the Literary Balanced Tree Template, which requires propagating lazy tags when descending nodes.

Reference Code 
  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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <iostream>
#include <tuple>

// Change here to use different strategies to balance and to merge.
#define BALANCE_BY_ROTATING 0
#define ROTATE_BY_JOINING 1

constexpr int N = 2e5;
constexpr double ALPHA = 0.292;

int id, rt, ch[N][2], sz[N], val[N], lz[N];
int pool[N], top;

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

void lazy_reverse(int x) {
  if (!x) return;
  std::swap(ch[x][0], ch[x][1]);
  lz[x] ^= 1;
}

void push_down(int x) {
  if (lz[x]) {
    lazy_reverse(ch[x][0]);
    lazy_reverse(ch[x][1]);
    lz[x] = 0;
  }
}

// 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) {
  push_down(x);
  int y = ch[x][0];
  int z = ch[x][1];
  del_node(x);
  return std::make_pair(y, z);
}

// 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);
}

#if BALANCE_BY_ROTATING

#if ROTATE_BY_JOINING

// 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));
  }
}

#else

// 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;
}

#endif

// 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;
  push_down(x);
  bool r = sz[ch[x][1]] > sz[ch[x][0]];
  if (!too_heavy(sz[ch[x][r]], sz[ch[x][!r]])) return;
  push_down(ch[x][r]);
  if (need_double_rotation(ch[x][r], r)) {
    push_down(ch[ch[x][r]][!r]);
    rotate(ch[x][r], !r);
  }
  rotate(x, r);
}

// 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);
  }
}

#else

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

// Balance the subtree at x;
void balance(int& x) {
  if (sz[x] == 1) return;
  if (too_heavy(sz[ch[x][0]], sz[ch[x][1]]) ||
      too_heavy(sz[ch[x][1]], sz[ch[x][0]])) {
    int a, b;
    std::tie(a, b) = cut(x);
    x = merge(a, b);
  }
}

#endif

// Split the subtree at x.
// The left half will have k elements.
std::pair<int, int> split(int x, int k) {
  if (!x) return {0, 0};
  if (!k) return {0, x};
  if (k == sz[x]) return {x, 0};
  int a, b;
  std::tie(a, b) = cut(x);
  if (k <= sz[a]) {
    int ll, rr;
    std::tie(ll, rr) = split(a, k);
    return {ll, merge(rr, b)};
  } else {
    int ll, rr;
    std::tie(ll, rr) = split(b, k - sz[a]);
    return {merge(a, ll), rr};
  }
}

// Reverse the interval [l, r].
void reverse(int l, int r) {
  int ll, rr;
  std::tie(rt, rr) = split(rt, r);
  std::tie(ll, rt) = split(rt, l - 1);
  lazy_reverse(rt);
  rt = merge(ll, merge(rt, rr));
}

// Output the subtree at x.
void print(int x) {
  if (sz[x] == 1) {
    std::cout << val[x] << ' ';
  } else {
    push_down(x);
    print(ch[x][0]);
    print(ch[x][1]);
  }
}

// Output the tree.
void print() {
  print(rt);
  std::cout << '\n';
}

// Build the tree for the interval [ll, rr].
int build(int ll, int rr) {
  if (ll == rr) return new_leaf(ll);
  int mm = (ll + rr) / 2;
  return join(build(ll, mm), build(mm + 1, rr));
}

int main() {
  int n, m;
  std::cin >> n >> m;
  rt = build(1, n);
  for (; m; --m) {
    int l, r;
    std::cin >> l >> r;
    reverse(l, r);
  }
  print();
  return 0;
}

Note that WBLT requires double the space; when splitting and merging are involved, garbage collection needs attention, and useless nodes should be recycled promptly; otherwise, the space is not linear.

References and Notes

  • Weight-balanced tree - Wikipedia
  • Nievergelt, J.; Reingold, E. M. (1973). "Binary Search Trees of Bounded Balance". SIAM Journal on Computing. 2: 33–43.
  • Blum, Norbert; Mehlhorn, Kurt (1980). "On the average number of rebalancing operations in weight-balanced trees". Theoretical Computer Science. 11 (3): 303–320.
  • Hirai, Y.; Yamamoto, K. (2011). "Balancing weight-balanced trees". Journal of Functional Programming. 21 (3): 287.
  • Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264.
  • Straka, Milan. (2011). "Adams’Trees Revisited: Correctness Proof and Efficient Implementation." International Symposium on Trends in Functional Programming. Berlin, Heidelberg: Springer Berlin Heidelberg.

  1. The parameter range \(\alpha < 1-\dfrac{\sqrt{2}}{2},~\beta=\dfrac{1-2\alpha}{1-\alpha}\) given in Nievergelt and Reingold's original paper is incorrect. Hirai and Yamamoto's article provides corresponding counterexamples, mainly occurring on some very small trees, causing the entire inductive proof to fail. Of course, in actual programming competitions, it is difficult to construct data that can break these wrong parameters, so in practice it may not have much impact. ↩

  2. As can be seen from the later proof: in the third case, \(z\) and \(w+y\) are always balanced; in the fourth case, \(z\) and \(u\) are always balanced. They can be directly joined without needing merging. ↩

  3. Since a single balance operation is at most equivalent to joining subtrees twice, and when the last two subtrees are already balanced, the subtree joining algorithm needs to be called once more, if measured by the number of calls to the subtree joining algorithm, the constant of the merging operation based on balance implementation is consistent with the balance operation algorithm of direct merging described below. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用