Next: 8.2 Discussion and Exercises Up: 8. Scapegoat Trees Previous: 8. Scapegoat Trees Contents
A ScapegoatTree is a BinarySearchTree that, in addition to keeping
track of the number,
, of nodes in the tree also keeps a counter,
,
that maintains an upper-bound on the number of nodes.
int q;
At all times,
and
obey the following inequalities:
and height
.
Implementing the
operation in a ScapegoatTree is done
using the standard algorithm for searching in a BinarySearchTree
(see ). This takes time proportional to the
height of the tree which, by (![[*]](crossref.png)
) is
.
To implement the
operation, we first increment
and
and then use the usual algorithm for adding
to a binary search
tree; we search for
and then add a new leaf
with
.
At this point, we may get lucky and the depth of
might not exceed
. If so, then we leave well enough alone and don't do
anything else.
Unfortunately, it will sometimes happen that
. In this case we need to do something to reduce the height.
This isn't a big job; there is only one node, namely
, whose depth
exceeds
. To fix
, we walk from
back up to the
root looking for a scapegoat,
. The scapegoat,
, is a very
unbalanced node. It has the property that
is the child of
on the path from the root to
.
We'll very shortly prove that a scapegoat exists. For now, we can
take it for granted. Once we've found the scapegoat
, we completely
destroy the subtree rooted at
and rebuild it into a perfectly balanced
binary search tree. We know, from (), that, even before
the addition of
,
's subtree was not a complete binary tree.
Therefore, when we rebuild
, the height decreases by at least 1 so that height of the ScapegoatTree is once again at most
.
boolean add(T x) {
// first do basic insertion keeping track of depth
Node<T> u = newNode(x);
int d = addWithDepth(u);
if (d > log32(q)) {
// depth exceeded, find scapegoat
Node<T> w = u.parent;
while (3*size(w) <= 2*size(w.parent))
w = w.parent;
rebuild(w.parent);
}
return d >= 0;
}
|
and rebuilding the
subtree rooted at
, then the running time of
is dominated
by the initial search, which takes
time.
We will account for the cost of finding the scapegoat and rebuilding
using amortized analysis in the next section.
The implementation of
in a ScapegoatTree is very simple.
We search for
and remove it using the usual algorithm for removing a
node from a BinarySearchTree. (Note that this can never increase the
height of the tree.) Next, we decrement
but leave
unchanged.
Finally, we check if
and, if so, we rebuild the entire
tree into a perfectly balanced binary search tree and set
.
boolean remove(T x) {
if (super.remove(x)) {
if (2*n < q) {
rebuild(r);
q = n;
}
return true;
}
return false;
}
Again, if we ignore the cost of rebuilding, the running time of the
operation is proportional to the height of the tree, and is
therefore
.
In this section we analyze the correctness and amortized running time
of operations on a ScapegoatTree. We first prove the correctness by
showing that, when the
operation results in a node that violates
Condition (), then we can always find a scapegoat:
be a node of depth
in a ScapegoatTree.
Then there exists a node
on the path from
to the root
such that
on the path from
to the root. Denote the path
from the root to
as
. Then, we have
,
,
and, more generally,
, hence
Next, we analyze the parts of the running time that we have not yet
accounted for. There are two parts: The cost of calls to
when search for scapegoat nodes, and the cost of calls to
when we find a scapegoat
.
The cost of calls to
can be related to the cost of calls to
, as follows:
in a ScapegoatTree, the cost of finding the scapegoat
and rebuilding the subtree rooted at
is
.
, once we find it, is
. When searching for the scapegoat node, we call
on a sequence of nodes
until we find the scapegoat
. However, since
is the first node in this sequence
that is a scapegoat, we know that
. Therefore, the cost of all calls to
is
 |
 |
 |
|
|
 |
||
|
 |
||
|
 |
All that remains is to prove an upper-bound on the cost of calls to
:
and
operations causes at most
time to be used
by
operations.
, units of time
spent rebuilding. The scheme gives out a total of
credits
and every call to
is paid for with credits stored at
.
During an insertion or deletion, we give one credit to each node on the
path to the inserted node, or deleted node,
. In this way we hand
out at most
credits per operation.
During a deletion we also store an additional 1 credit ``on the side.''
Thus, in total we give out at most
credits. All that
remains is to show that these credits are sufficient to pay for all
calls to
.
If we call
during an insertion, it is because
is
a scapegoat. Suppose, without loss of generality, that
was rebuilt (or when
was inserted, if a subtree containing
was never rebuilt), we had
or
operations that have
affected
or
since then is at least
that are available to pay for the
time it takes to
call
.
If we call
during a deletion, it is because
.
In this case, we have
credits stored ``on the side'' and
we use these to pay for the
time it takes to rebuild the root.
This completes the proof.
operations, a ScapegoatTree supports the operations
,
, and
in
time per operation.
Furthermore, beginning with an empty ScapegoatTree, any sequence of
and
operations results in a total of
time spent during all calls to
.
opendatastructures.org