In this chapter, 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
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
into a perfectly
balanced tree. One of the simplest is to traverse
gathering all its nodes into an array,
, and then to recursively
build a balanced subtree using
. If we let
then the element
becomes the root of the new subtree,
get stored recursively in the left subtree
get stored recursively in the
A call to takes time. The resulting subtree has minimum height; there is no tree of smaller height that has nodes.