AIOJ

Introduction

A scapegoat tree is a weight-balanced tree that maintains balance through rebuilding. After each insertion or deletion, it checks for imbalance and selectively rebuilds the tree when necessary.

Scapegoat trees generally do not support interval operations or full persistence, but they are simple to implement and have small constants.

Basic Structure and Operations

The core operations are rebuilding, insertion, and deletion.

Node Information

A scapegoat tree stores the following information for self-balancing:

Structural information:
- id: the number of allocated vertices;
- rt: the root vertex;
- lc[x], rc[x]: the left and right children;
- tot[x]: the size of the subtree rooted at $x$ (each vertex counts as $1$ )¹;
- tot_active: the number of undeleted vertices (cnt[x] != 0) in the whole tree.

When using a scapegoat tree as a balanced tree, also store:

Balanced-tree vertex information:
- val[x]: the value stored at a vertex;
- cnt[x]: the count of the value stored at a vertex (possibly $0$ );
- sz[x]: the number of stored values in the subtree rooted at $x$ .

Implement push_up to maintain this information:

Reference implementation

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

Be careful: tot[x] and sz[x] are updated differently.

Rebuilding

When the tree becomes unbalanced, rebuild a subtree to make it as balanced as possible. Rebuilding has two steps:

Traverse the subtree in inorder and store all undeleted vertices in a sequence;
Build by divide and conquer: choose the midpoint as the root, recursively build both sides, and update the vertex information.

A reference implementation follows:

Reference implementation

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

Remember to maintain vertex information while building the tree, including information for leaves.

A single rebuild costs $\Theta(|T_x|)$ . Rebuilding after every insertion or deletion would be too slow. The key idea is to choose rebuild times carefully and obtain amortized complexity $O(\log n)$ .

Insertion

An insertion may make the tree unbalanced. Introduce $\alpha\in(0.5,1)$ to detect this; a typical choice is $0.7\sim 0.8$ .

If the new vertex has depth greater than $\lfloor\log_{1/\alpha}|T|\rfloor$ , where $|T|$ is the updated tree size, find an unbalanced vertex while backtracking and rebuild its subtree. The subtree rooted at $x$ is unbalanced when:

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

Here, $\mathrm{left}(x)$ and $\mathrm{right}(x)$ are the left and right children of $x$ , and $|T_x|$ is the size of the subtree rooted at $x$ .

The insertion procedure is:

Descend by the binary-search-tree property to the insertion position, recording the depth;
Update an existing vertex, or create a new one;
If the new vertex is too deep, backtrack to the root, update information, and record the first (or any) unbalanced subtree;
If an unbalanced vertex exists, rebuild its subtree.

A reference implementation follows:

Reference implementation

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

An insertion causes at most one rebuild. Extra balance checks are unnecessary if no vertex was added, the new vertex is not too deep, or a rebuild has already occurred while backtracking; extra rebuilds can hurt performance². The first unbalanced vertex found while backtracking is the “scapegoat”.

Deletion

Deletion is simple: the tree uses lazy deletion, so an empty vertex is not removed immediately but retained for later rebuilding.

Too many empty vertices reduce access efficiency. Maintain the number of undeleted vertices and the number of allocated vertices; for the chosen threshold³ $\alpha\in(0,1)$ , rebuild the whole tree when their ratio falls below $\alpha$ , removing all empty vertices.

Reference implementation

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

For a tree of size $n$ , accessing a vertex costs $O(\log n)$ ; the amortized cost per insertion or deletion over $\Theta(n)$ operations is also $O(\log n)$ .

This section gives only a brief complexity argument; see the original paper for the detailed proof.

Complexity of scapegoat trees

With lazy deletion, $n$ undeleted vertices may occupy $\alpha^{-1}n$ vertices. This differs only by a constant factor, so both are called the “tree size”.

Access: a tree of size $n$ has height $O(\log n)$ , so access has that complexity.

First distinguish two notions:
- $\alpha$ -weight balance: each child subtree has size at most $\alpha$ times the subtree size at its parent;
- $\alpha$ -height balance: the height is at most $\lfloor\log_{1/\alpha}|T|\rfloor$ , where $T$ is the tree.
$\alpha$ -weight balance implies $\alpha$ -height balance because each level reduces subtree size by a factor of $\alpha$ ; the converse need not hold. After each operation the scapegoat tree is $\alpha$ -height-balanced⁴, which guarantees the access bound.

Only insertion changes the structure. If a new vertex is too deep, the tree is no longer $\alpha$ -height-balanced, so the path back to the root contains a “scapegoat” whose subtree is no longer $\alpha$ -weight-balanced; after rebuilding, the tree regains $\alpha$ -height balance and the new vertex is no longer too deep.
Insertion: insertion has amortized complexity $O(\log n)$ .

scapegoat-tree update，scapegoat-tree update $x$ scapegoat-tree update，scapegoat-tree update $\Theta(|T_x|)$ ．scapegoat-tree update $x$ scapegoat-tree update，scapegoat-tree update（scapegoat-tree update）scapegoat-tree update，scapegoat-tree update．scapegoat-tree update，scapegoat-tree update $x$ scapegoat-tree update
$\max\{|T_{\mathrm{left}(x)}|,|T_{\mathrm{right}(x)}|\} > \alpha\cdot |T_x|.$
The child-subtree size difference is therefore at least $(2\alpha-1)|T_x|$ , so $T_x$ vertices are inserted into $\Omega(|T_x|)$ between consecutive rebuilds.

Give every vertex on the root-to-inserted-vertex path $\Theta(1)$ potential. Before rebuilding at vertex $x$ , the subtree at vertex $x$ has accumulated $\Omega(|T_x|)$ potential; the rebuild at $x$ costs $\Theta(|T_x|)$ . Since the tree depth is $O(\log n)$ , each insertion adds $O(\log n)$ potential; thus $\Theta(n)$ insertions add $O(n\log n)$ in total, all rebuilds cost $O(n\log n)$ , and insertion has amortized complexity $O(\log n)$ .

The argument does not assume that no other rebuild occurs inside $x$ between the two rebuilds at $T_x$ ; rebuilding only subtrees satisfying the imbalance condition is sufficient.
Deletion: deletion also has amortized complexity $O(\log n)$ .

scapegoat-tree update．scapegoat-tree update，scapegoat-tree update $\Theta(n)$ scapegoat-tree update，scapegoat-tree update $\Theta(n)$ scapegoat-tree update．scapegoat-tree update $O(\log n)$ scapegoat-tree update，scapegoat-tree update $\Theta(n)$ ，scapegoat-tree update $\Theta(n)$ scapegoat-tree update
$\Theta(n)O(\log n)+\Theta(n)$
Therefore one deletion has amortized complexity $O(\log n)$ .

Balanced-Tree Operations

This section describes maintaining a multiset with a scapegoat tree.

The remaining operations are standard balanced-tree operations, with adjustments because empty vertices may remain.

Querying Rank

Descend by the binary-search-tree property and record the number of values stored in left subtrees on the path.

Reference implementation

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

Querying a Value by Rank

Descend using the subtree value counts stored at each vertex; a vertex with count zero may exist.

Reference implementation

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

Querying the Predecessor and Successor

Combine the two functions above.

Reference implementation

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

When implementing this directly, handle vertices whose count is zero.

Reference Implementation

Finally, here is a reference implementation for the template problem Ordinary Balanced Tree.

Reference implementation

#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.

// --8<-- [start:push-up]
// 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]];
}

// --8<-- [end:push-up]
// --8<-- [start:rebuild]
// 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);
}

// --8<-- [end:rebuild]
// --8<-- [start:insert]
// 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); }

// --8<-- [end:insert]
// --8<-- [start:remove]
// 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;
}

// --8<-- [end:remove]
// --8<-- [start:find-rank]
// 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;
}

// --8<-- [end:find-rank]
// --8<-- [start:find-kth]
// 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;
}

// --8<-- [end:find-kth]
// --8<-- [start:pred-succ]
// 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)); }

// --8<-- [end:pred-succ]
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

Galperin, Igal, and Ronald L. Rivest. "Scapegoat trees." Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. 1993.
Scapegoat Tree - Wikipedia
Scapegoat Tree - riteme's blog

Footnotes

One may count only undeleted vertices, replacing tot_active with the total occupied-vertex count tot_max and adjusting the code accordingly. ↩
The analysis below shows that this loss is only a larger constant factor. Checking depth may involve floating-point logarithms, so checking only imbalance can be faster on some inputs. ↩
This need not equal the insertion parameter. Different choices change only constant factors and preserve the overall complexity. ↩
In the original definition, $n$ counts undeleted vertices, so the height is at most $\lfloor\log_{1/\alpha}n\rfloor+1$ , called weak $\alpha$ -height balance. ↩

Scapegoat Tree

Introduction

Basic Structure and Operations

Node Information

Rebuilding

Insertion

Deletion

Time Complexity

Balanced-Tree Operations

Querying Rank

Querying a Value by Rank

Querying the Predecessor and Successor

Reference Implementation

References

Footnotes