Introduction to Scapegoat Trees
Learn the implementation of ScapegoatTrees in this lesson.
We'll cover the following...
ScapegoatTree
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 get stored recursively in the left subtree and
get stored recursively in the right subtree.
class ScapegoatTree(BinarySearchTree):def __init__(self):super(ScapegoatTree, self).__init__()self._initialize()def _initialize(self):self.n = 0self.q = 0def rebuild(self, u):ns = self._size(u)p = u.parenta = new_array(ns)self.pack_into_array(u, a, 0)if p == self.nil:self.r = self.build_balanced(a, 0, ns)self.r.parent = nilelif p.right == u:p.right = self.build_balanced(a, 0, ns)p.right.parent = pelse:p.left = self.build_balanced(a, 0, ns)p.left.parent = p
A call to rebuild(u)
takes time. The resulting subtree has
minimum height; there is no tree of smaller height that has size(u)
nodes.
ScapegoatTree
: A binary search tree with partial rebuilding
A ScapegoatTree
is a BinarySearchTree
that, in addition to keeping
track of the number, n
, of nodes in the tree also keeps a counter, q
, that
maintains an upper-bound on the number of nodes.
class ScapegoatTree(BinarySearchTree):def __init__(self):super(ScapegoatTree, self).__init__()self._initialize()def _initialize(self):self.n = 0self.q = 0
At all times, n
and q
obey the following inequalities:
...