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.