Skip to content

Scapegoat Tree

Introduction

Scapegoat Tree is a weight-balanced tree that maintains balance through reconstruction operations. After insertion or deletion operations, the Scapegoat Tree checks whether the tree has become unbalanced; if so, it performs targeted reconstruction to restore balance.

Generally, Scapegoat Trees do not support interval operations and cannot be fully persistent; however, they have the advantages of simple implementation and small constant factors.

Basic Structure and Operations

The core operations of a Scapegoat Tree are reconstruction, insertion, and deletion.

Node Information

A Scapegoat Tree needs to store the following information for self-balancing operations:

  • Tree structure information:
    • id: Number of nodes used;
    • rt: Root node;
    • lc[x], rc[x]: Left and right child nodes;
    • tot[x]: Subtree size rooted at \(x\) (each node counts as \(1\))3;
    • tot_active: Number of undeleted nodes (i.e., cnt[x] != 0) in the entire tree.

When using a Scapegoat Tree to implement a balanced tree, the following information is also needed:

  • Balanced tree node information:
    • val[x]: Value stored in the node;
    • cnt[x]: Count of the value stored in the node (may be \(0\));
    • sz[x]: Count of values stored in the subtree rooted at \(x\).

To maintain node information, a push_up operation can be implemented:

Reference Implementation 
1
2
3
4
5
// Update node info from its children.
void push_up(int x) {
  tot[x] = 1 + tot[lc[x]] + tot[rc[x]];
  sz[x] = cnt[x] + sz[lc[x]] + sz[rc[x]];
}

Note the difference in how tot[x] and sz[x] are updated.

Reconstruction Operation

When the tree becomes unbalanced, a subtree needs to be reconstructed to make it as balanced as possible. Reconstruction consists of two steps:

  • Perform an in-order traversal of the subtree to be reconstructed, storing all undeleted nodes in a sequence;
  • Build the tree using binary division: take the middle element as the root, recursively build left and right subtrees, and update node information.

Reference implementation:

Reference Implementation 
 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
// Tree -> Array.
void flatten(int x) {
  if (!x) return;
  flatten(lc[x]);
  if (cnt[x]) tmp[n_tmp++] = x;
  flatten(rc[x]);
}

// Array -> Tree.
int build(int ll, int rr) {
  if (ll > rr) return 0;
  int mm = (ll + rr) / 2;
  int x = tmp[mm];
  lc[x] = build(ll, mm - 1);
  rc[x] = build(mm + 1, rr);
  push_up(x);
  return x;
}

// Rebuild a subtree.
void rebuild(int& x) {
  n_tmp = 0;
  flatten(x);
  x = build(0, n_tmp - 1);
}

When building the tree, pay attention to maintaining node information, including leaf node information.

The complexity of a single reconstruction is \(\Theta(|T_x|)\). Therefore, if reconstruction is performed after every insertion and deletion, the complexity would be unacceptable. The core idea of the Scapegoat Tree lies in the choice of when to reconstruct, thereby achieving an amortized complexity of \(O(\log n)\).

Insertion Operation

Insertion may cause the tree to become unbalanced. To determine imbalance, a parameter \(\alpha\in(0.5,1)\) is introduced, typically chosen between \(0.7\sim 0.8\).

If the depth of the newly inserted node exceeds \(\lfloor\log_{1/\alpha}|T|\rfloor\), where \(|T|\) is the size of the tree after the update, then during backtracking, the node where imbalance occurs needs to be found and reconstructed. At this point, the imbalance condition for the subtree rooted at \(x\) is judged as follows:

\[ \max\{|T_{\mathrm{left}(x)}|,|T_{\mathrm{right}(x)}|\} > \alpha\cdot |T_x|, \]

where \(\mathrm{left}(x)\) and \(\mathrm{right}(x)\) are the left and right child nodes of \(x\), and \(|T_x|\) is the size of the subtree rooted at \(x\).

The specific steps for insertion are as follows:

  • First, use the properties of a binary search tree to find the insertion position downwards, recording the depth during descent;
  • If a node already exists, directly modify its information; otherwise, create a new node;
  • If the new node is too deep, backtrack from bottom to top to the root, update node information, and record the first (or any) node where the subtree becomes unbalanced;
  • If an unbalanced node exists, reconstruct its subtree.

Reference implementation:

Reference Implementation 
 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
// Insert v into subtree of x.
bool insert(int& x, int v, int dep) {
  bool check = false;
  if (!x) {
    x = ++id;
    val[x] = v;
    check = dep > std::log(tot[rt] + 1) / std::log(1 / ALPHA);
  }
  if (val[x] == v) {
    if (!cnt[x]) ++tot_active;
    ++cnt[x];
  } else if (v < val[x]) {
    check = insert(lc[x], v, dep + 1);
  } else {
    check = insert(rc[x], v, dep + 1);
  }
  push_up(x);
  if (check && (tot[lc[x]] > ALPHA * tot[x] || tot[rc[x]] > ALPHA * tot[x])) {
    rebuild(x);
    return false;
  }
  return check;
}

// Insert v into the tree.
void insert(int v) { insert(rt, v, 0); }

Note that a single insertion causes at most one reconstruction. If no new node is added, or the new node is not too deep, or reconstruction has already been performed during this backtracking process, further imbalance checks are unnecessary. Excessive reconstruction may lead to efficiency loss1. The first unbalanced node encountered during backtracking is the so-called "scapegoat".

Deletion Operation

The deletion operation is handled very simply. The deletion strategy of the Scapegoat Tree is "lazy deletion", meaning that when a node becomes empty, it is not removed immediately but left for later processing.

Of course, if there are too many empty nodes in the tree, access efficiency will significantly decrease. Therefore, the Scapegoat Tree maintains two counts: the number of undeleted nodes in the entire tree and the number of nodes actually used in the entire tree. For a chosen threshold2 \(\alpha\in(0,1)\), when the ratio of the former to the latter falls below \(\alpha\), the entire tree is reconstructed once, removing all empty nodes during reconstruction.

Reference Implementation 
 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
// Remove v from subtree of x.
bool remove(int x, int v) {
  if (!x) return false;
  bool succ = true;
  if (v < val[x]) {
    succ = remove(lc[x], v);
  } else if (v > val[x]) {
    succ = remove(rc[x], v);
  } else if (cnt[x]) {
    --cnt[x];
    if (!cnt[x]) --tot_active;
  } else {
    succ = false;
  }
  push_up(x);
  return succ;
}

// Remove v from the tree.
bool remove(int v) {
  bool succ = remove(rt, v);
  if (!tot_active) {
    rt = 0;
  } else if (succ && tot_active < tot[rt] * ALPHA) {
    rebuild(rt);
  }
  return succ;
}

Time Complexity

Accessing a node in a Scapegoat Tree of size \(n\) has a time complexity of \(O(\log n)\) per operation. The amortized time complexity for \(\Theta(n)\) insertions and deletions is also \(O(\log n)\) per operation.

This section provides a brief argument for the time complexity of the Scapegoat Tree; for detailed proofs, please refer to the original paper.

Argument for the Time Complexity of Scapegoat Tree

Due to the lazy deletion strategy, a Scapegoat Tree with \(n\) undeleted nodes may occupy \(\alpha^{-1}n\) nodes. Since they differ only by a constant factor, this article does not distinguish between the number of undeleted nodes and the number of occupied nodes in a Scapegoat Tree, but uniformly refers to it as the "size of the tree".

  1. Access Operation: The complexity of access operations is guaranteed because the height of a Scapegoat Tree of size \(n\) is always \(O(\log n)\).

    First, distinguish two concepts:

    • \(\alpha\)‑weight balance: For all nodes, the sizes of the left and right child subtrees do not exceed \(\alpha\) times the size of the subtree at that node;
    • \(\alpha\)‑height balance: The height of the tree does not exceed \(\lfloor\log_{1/\alpha}|T|\rfloor\), where \(T\) is the size of the tree.

    \(\alpha\)‑weight balance implies \(\alpha\)‑height balance because each increase in child node depth reduces the size by a factor of \(\alpha\); the converse is not necessarily true. More strictly, after each operation, the Scapegoat Tree is always \(\alpha\)‑height balanced4, which guarantees the complexity of access operations.

    Only insertion operations change the tree structure, so it is sufficient to show that after each insertion, the Scapegoat Tree remains \(\alpha\)‑height balanced. If a newly inserted node is too deep, causing the entire tree to no longer be \(\alpha\)‑height balanced, then when backtracking from this node to the root, at least one node, the "scapegoat", will be encountered whose subtree is no longer \(\alpha\)‑weight balanced. After reconstructing it, the height of the subtree will decrease by at least one, so the newly inserted node will no longer be too deep.

  2. Insertion Operation: The amortized complexity of insertion is \(O(\log n)\).

    Suppose after an insertion, a reconstruction of the subtree at node \(x\) occurs, with a time cost of \(\Theta(|T_x|)\). Because when node \(x\) was first inserted, or after its last reconstruction (either itself or an ancestor), its left and right subtrees differed by at most one node. Before this reconstruction, the condition at node \(x\) must have been:

    \[ \max\{|T_{\mathrm{left}(x)}|,|T_{\mathrm{right}(x)}|\} > \alpha\cdot |T_x|. \]

    This condition ensures that the difference in sizes between the left and right subtrees is at least \((2\alpha-1)|T_x|\). Therefore, between these two reconstructions, \(\Omega(|T_x|)\) nodes have been inserted into subtree \(T_x\).

    Using amortized analysis5, if during each node insertion, \(\Theta(1)\) potential is added to each node on the path from the root to that node (before possible reconstruction), then by the time reconstruction occurs at node \(x\), \(\Omega(|T_x|)\) potential must have accumulated at node \(x\), sufficient to pay for the reconstruction cost \(\Theta(|T_x|)\). Since the tree depth is \(O(\log n)\), the potential added per insertion is \(O(\log n)\); this implies that the total potential increase over \(\Theta(n)\) insertions is \(O(n\log n)\). Consequently, the total cost of subtree reconstructions is also \(O(n\log n)\), and the amortized time complexity per insertion (including reconstruction) is \(O(\log n)\).

    Note that the analysis does not assume that no other reconstructions occurred within subtree \(T_x\) between the two reconstructions at node \(x\). Therefore, as long as only subtrees at nodes satisfying the imbalance condition are reconstructed, the complexity is guaranteed to be correct.

  3. Deletion Operation: The amortized complexity of deletion is also \(O(\log n)\).

    Reconstruction triggered by deletion results in the entire tree having no empty nodes. Before a deletion triggers reconstruction, there are already \(\Theta(n)\) empty nodes in the entire tree, meaning at least \(\Theta(n)\) deletion operations have been performed. Since the addressing complexity of each deletion is \(O(\log n)\), and the complexity of a single reconstruction is \(\Theta(n)\), the actual time cost for these \(\Theta(n)\) deletions is:

    \[ \Theta(n)O(\log n)+\Theta(n). \]

    Therefore, the amortized complexity per deletion is \(O(\log n)\).

Balanced Tree Operations

This section describes how to maintain a multiset using a Scapegoat Tree.

Apart from the operations introduced in the previous section, the remaining operations are common balanced tree operations. However, because a Scapegoat Tree may contain empty nodes, these operations also need to be adjusted accordingly.

Query Rank

Use the properties of a binary search tree to find the node position downwards, recording the number of values stored on the left side of the path during the process.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Find the rank of v, i.e., #{val < v} + 1.
int find_rank(int v) {
  int res = 0;
  int x = rt;
  while (x && val[x] != v) {
    if (v < val[x]) {
      x = lc[x];
    } else {
      res += sz[lc[x]] + cnt[x];
      x = rc[x];
    }
  }
  return res + sz[lc[x]] + 1;
}

Query Value by Rank

Use the subtree value count information stored in nodes to search downwards. Note that there may be nodes with zero count.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// Find the k-th smallest element.
int find_kth(int k) {
  if (k <= 0 || sz[rt] < k) return -1;
  int x = rt;
  for (;;) {
    if (k <= sz[lc[x]]) {
      x = lc[x];
    } else if (k <= sz[lc[x]] + cnt[x]) {
      return val[x];
    } else {
      k -= sz[lc[x]] + cnt[x];
      x = rc[x];
    }
  }
  return -1;
}

Query Predecessor and Successor

Combine the above two functions.

Reference Implementation 
1
2
3
4
5
// Find predecessor.
int find_prev(int x) { return find_kth(find_rank(x) - 1); }

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

If you want to implement directly, pay attention to handling nodes with zero count.

Reference Implementation

Finally, this section provides a reference implementation for the template problem Ordinary Balanced Tree.

Reference Implementation 
  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
#include <cmath>
#include <iostream>

constexpr int N = 2e6;
constexpr double ALPHA = 0.7;
int id, rt, lc[N], rc[N], tot[N], tot_active;  // Tree structure info.
int tmp[N], n_tmp;                             // Space for rebuilding trees.
int val[N], cnt[N], sz[N];                     // Node info.

// Update node info from its children.
void push_up(int x) {
  tot[x] = 1 + tot[lc[x]] + tot[rc[x]];
  sz[x] = cnt[x] + sz[lc[x]] + sz[rc[x]];
}

// Tree -> Array.
void flatten(int x) {
  if (!x) return;
  flatten(lc[x]);
  if (cnt[x]) tmp[n_tmp++] = x;
  flatten(rc[x]);
}

// Array -> Tree.
int build(int ll, int rr) {
  if (ll > rr) return 0;
  int mm = (ll + rr) / 2;
  int x = tmp[mm];
  lc[x] = build(ll, mm - 1);
  rc[x] = build(mm + 1, rr);
  push_up(x);
  return x;
}

// Rebuild a subtree.
void rebuild(int& x) {
  n_tmp = 0;
  flatten(x);
  x = build(0, n_tmp - 1);
}

// Insert v into subtree of x.
bool insert(int& x, int v, int dep) {
  bool check = false;
  if (!x) {
    x = ++id;
    val[x] = v;
    check = dep > std::log(tot[rt] + 1) / std::log(1 / ALPHA);
  }
  if (val[x] == v) {
    if (!cnt[x]) ++tot_active;
    ++cnt[x];
  } else if (v < val[x]) {
    check = insert(lc[x], v, dep + 1);
  } else {
    check = insert(rc[x], v, dep + 1);
  }
  push_up(x);
  if (check && (tot[lc[x]] > ALPHA * tot[x] || tot[rc[x]] > ALPHA * tot[x])) {
    rebuild(x);
    return false;
  }
  return check;
}

// Insert v into the tree.
void insert(int v) { insert(rt, v, 0); }

// Remove v from subtree of x.
bool remove(int x, int v) {
  if (!x) return false;
  bool succ = true;
  if (v < val[x]) {
    succ = remove(lc[x], v);
  } else if (v > val[x]) {
    succ = remove(rc[x], v);
  } else if (cnt[x]) {
    --cnt[x];
    if (!cnt[x]) --tot_active;
  } else {
    succ = false;
  }
  push_up(x);
  return succ;
}

// Remove v from the tree.
bool remove(int v) {
  bool succ = remove(rt, v);
  if (!tot_active) {
    rt = 0;
  } else if (succ && tot_active < tot[rt] * ALPHA) {
    rebuild(rt);
  }
  return succ;
}

// Find the rank of v, i.e., #{val < v} + 1.
int find_rank(int v) {
  int res = 0;
  int x = rt;
  while (x && val[x] != v) {
    if (v < val[x]) {
      x = lc[x];
    } else {
      res += sz[lc[x]] + cnt[x];
      x = rc[x];
    }
  }
  return res + sz[lc[x]] + 1;
}

// Find the k-th smallest element.
int find_kth(int k) {
  if (k <= 0 || sz[rt] < k) return -1;
  int x = rt;
  for (;;) {
    if (k <= sz[lc[x]]) {
      x = lc[x];
    } else if (k <= sz[lc[x]] + cnt[x]) {
      return val[x];
    } else {
      k -= sz[lc[x]] + cnt[x];
      x = rc[x];
    }
  }
  return -1;
}

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

// Find successor.
int find_next(int x) { return find_kth(find_rank(x + 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;
}

References

  1. According to the complexity analysis later, these efficiency losses only imply larger constant factors, while the complexity remains correct. Since checking tree depth may involve many floating-point logarithm operations, code that does not check depth but only checks imbalance may be faster on some data. ↩

  2. This does not have to be the same parameter as chosen for the insertion operation above. Although the original paper makes this assumption, choosing different parameters only changes the constant factor in the per-operation complexity; the overall complexity remains correct. ↩

  3. Alternatively, only count undeleted nodes. In this case, tot_active is no longer needed, but the total number of occupied nodes tot_max must be counted, and the code should be adjusted accordingly. ↩

  4. According to the original definition, \(n\) refers to the number of undeleted nodes, so it can only guarantee that the tree height does not exceed \(\lfloor\log_{1/\alpha}n\rfloor+1\), which is called weak \(\alpha\)‑height balance. The difference in this constant term is not elaborated here. ↩

  5. Some articles simply analyze that \(\Omega(|T_x|)\) insertions correspond to one reconstruction, so the amortized complexity is \(\dfrac{\Omega(|T_x|)O(\log n)+\Theta(|T_x|)}{\Omega(|T_x|)} = O(\log n)\). This idea can help understand why the amortized complexity is correct, but it is not rigorous. This is because a single insertion may correspond to reconstructions at multiple ancestor nodes, so when node \(x\) undergoes reconstruction, the number of nodes within the subtree that did not cause reconstruction is not obviously \(\Omega(|T_x|)\). ↩

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