Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

Introduction to Scapegoat Trees

Explore the fundamentals of Scapegoat Trees, a balanced binary search tree that maintains logarithmic height through partial subtree rebuilding. Understand how adding and removing nodes triggers balance restoration via scapegoat nodes, and learn the efficiency and implementation details of these operations in C++.

We'll cover the following...

Scapegoat trees overview

Here, we study a binary search tree data structure, the ScapegoatTree. This structure is based on the common wisdom that, when something goes wrong, the first thing people tend to do is find someone to blame (the scapegoat). Once blame is firmly established, we can leave the scapegoat to fix the problem.

A ScapegoatTree keeps itself balanced by partial rebuilding operations. During a partial rebuilding operation, an entire subtree is deconstructed and rebuilt into a perfectly balanced subtree. There are many ways of rebuilding a subtree rooted at node u into a perfectly balanced tree. One of the simplest is to traverse u’s subtree, gathering all its nodes into an array, a, and then to recursively build a balanced subtree using a. If we let m = a.length/2, then the element a[m] becomes the root of the new subtree, a[0],...,a[m−1][0],...,\text{a}[m−1] get stored recursively in the left subtree and a[m+1],...,a[a.length−1]\text{a}[m + 1],...,\text{a}[\text{a.length} − 1] ...

C++
void rebuild(Node < T > u) {
  int ns = size(u);
  Node < T > p = u.parent;
  Node < T > [] a = Array.newInstance(Node.class, ns);
  packIntoArray(u, a, 0);
  if (p == nil) {
    r = buildBalanced(a, 0, ns);
    r.parent = nil;
  } else if (p.right == u) {
    p.right = buildBalanced(a, 0, ns);
    p.right.parent = p;
  } else {
    p.left = buildBalanced(a, 0, ns);
    p.left.parent = p;
  }
}
int packIntoArray(Node < T > u, Node < T > [] a, int i) {
  if (u == nil) {
    return i;
  }
  i = packIntoArray(u.left, a, i);
  a[i++] = u;
  return packIntoArray(u.right, a, i);
}
Node < T > buildBalanced(Node < T > [] a, int i, int ns) {
  if (ns == 0)
    return nil;
  int m = ns / 2;
  a[i + m].left = buildBalanced(a, i, m);
  if (a[i + m].left != nil)
    a[i + m].left.parent = a[i + m];
  a[i + m].right = buildBalanced(a, i + m + 1, ns - m - 1);
  if (a[i + m].right != nil)
    a[i + m].right.parent = a[i + m];
  return a[i + m];
}

A call to rebuild(u) takes ...