8. Scapegoat Trees

In this chapter, we study a binary search tree data structure, the $ \mathtt{ScapegoatTree}$, that 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 $ \mathtt{u}$ into a perfectly balanced tree. One of the simplest is to traverse $ \mathtt{u}$'s subtree, gathering all its nodes into an array $ \mathtt{a}$ and then to recursively build a balanced subtree using $ \mathtt{a}$. If we let $ \ensuremath{\mathtt{m}}=\ensuremath{\mathtt{a.length}}/2$, then the element $ \mathtt{a[m]}$ becomes the root of the new subtree, $ \ensuremath{\mathtt{a}}[0],\ldots,\ensuremath{\mathtt{a}}[\ensuremath{\mathtt{m}}-1]$ get stored recursively in the left subtree and $ \ensuremath{\mathtt{a}}[\ensuremath{\mathtt{m}}+1],\ldots,\ensuremath{\mathtt{a}}[\ensuremath{\mathtt{a.length}}-1]$ get stored recursively in the right subtree.

  void rebuild(Node *u) {
    int ns = BinaryTree<Node>::size(u);
    Node *p = u->parent;
    Node **a = new Node*[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;
    }
    delete[] a;
  }
  int packIntoArray(Node *u, Node **a, int i) {
    if (u == nil) {
      return i;
    }
    i = packIntoArray(u->left, a, i);
    a[i++] = u;
    return packIntoArray(u->right, a, i);
  }
A call to $ \mathtt{rebuild(u)}$ takes $ O(\ensuremath{\mathtt{size(u)}})$ time. The subtree built by $ \mathtt{rebuild(u)}$ has minimum height; there is no tree of smaller height that has $ \mathtt{size(u)}$ nodes.



Subsections

opendatastructures.org