Next: 9. Red-Black Trees Up: 8. Scapegoat Trees Previous: 8.1 : A Binary Contents
The term scapegoat tree is due to Galperin and Rivest [28], who define and analyze these trees. However, the same structure was discovered earlier by Andersson [3,5], who called them general balanced trees since they can have any shape as long as their height is small.
Experimenting with the
implementation will reveal that
it is often considerably slower than the other
implementations
in this book. This may be somewhat surprising, since height bound of
and
not too far from that of a
. The implementation could be optimized
by storing the sizes of subtrees explicitly at each node (or at least
reusing already computed subtree sizes). Even with these optimizations,
there will always be sequences of
and
operation for
which a
takes longer than other
implementations.
This gap in performance is due to the fact that, unlike the other
implementations discussed in this book, a
can spend a lot
of time restructuring itself. Exercise 8.1 asks you to prove
that there are sequences of
operations in which a
will spend on the order of
time in calls to
.
This is in contrast to other
implementations discussed in this
book that only make
structural changes during a sequence of
operations. This is, unfortunately, a necessary consequence of
the fact that a
does all its restructuring by calls to
[15].
Despite their lack of performance, there are applications in which a
could be the right choice. This would occur any time
there is additional data associated with nodes that cannot be updated
in constant time when a rotation is performed, but that can be updated
during a
operation. In such cases, the
and related structures based on partial rebuilding may work. An example of such an application is outlined in Exercise 8.5.
and call
for
, then the total time spent during calls to
is at least
for some constant 
.
, as described in this chapter guarantees that the
length of the search path does not exceed
. Design,
analyze, and implement a modified version of
where the
length of the search path does not exceed
, where
is a parameter with
.
What does your analysis and/or experiments say about the amortized cost
of
,
and
as a function of
?
. This is a tree in
which each node
, except the root, maintains the balance
invariant that
. The
and
operations are identical to the standard
operations, except that any time the balance invariant is violated at
a node
, the subtree rooted at
is rebuilt.
Your analysis should show that operations on a
run in
amortized time.
. In a
each
node
keeps a timer
. The
and
operations are exactly the same as in a standard
except that, whenever one of these operations affects
's subtree,
is decremented. When
the entire subtree rooted at
is rebuilt into a perfectly balanced binary search tree. When a node
is involved in a rebuilding operation (either because
is rebuilt
or one of
's ancestors is rebuilt)
is reset to
.
Your analysis should show that operations on a countdown tree run
in
amortized time. (Hint: First show that each node
satisfies some version of a balance invariant.)
data structure that maintains a
sequence (list) of elements. It supports these operations:
: Add a new element after the element
in the
sequence. Return the newly added element. (If
is null,
the new element is added at the beginning of the sequence.)
: Remove
from the sequence.
: return
if and only if
comes
before
in the sequence.
amortized time.
The third operation should run in constant-time.
The
data structure can be implemented by storing the elements
in something like a
, in the same order that they occur
in the sequence. To implement
in constant time,
each element
is labelled with an integer that encodes the path from
the root to
. In this way,
can be implemented
just by comparing the labels of
and
.