Splay trees - Data Structures and Problem Solving Using Java - page 846

that the cost of an access in a binary search tree is proportional to the depth of
the accessed node. Thus we can attempt to restructure the tree by moving fre-
quently accessed items toward the root. Although this process costs extra time
during the first find operation, it could be worthwhile in the long run.
The easiest way to move a frequently accessed item toward the root is to
rotate it continually with its parent, moving the item closer to the root, a pro-
cess called the rotate-to-root strategy. Then, if the item is accessed a second
time, the second access is cheap, and so on. Even if a few other operations
intervene before the item is reaccessed, that item will remain close to the root
and thus will be quickly found. An application of the rotate-to-root strategy to
node 3 is shown in Figure 22.1. 1
As a result of the rotation, future accesses of node 3 are cheap (for a
while). Unfortunately, in the process of moving node 3 up two levels, nodes 4
and 5 each move down a level. Thus, if access patterns do not follow the 90-
10 rule, a long sequence of bad accesses can occur. As a result, the rotate-to-
root rule does not exhibit logarithmic amortized behavior, which is likely
unacceptable. A bad case is illustrated in Theorem 22.1.

The rotate-to-root
strategy rearranges
a binary search tree
after each access
so as to move fre-
quently accessed
items closer to
the root.

The rotate-to-root
strategy is good if
the 90-10 rule
applies. It can be a
bad strategy when
the rule does not
apply.

Theorem 22.1

There are arbitrarily long sequences for which M rotate-to-root accesses use Θ ( MN )

time.

Consider the tree formed by the insertion of 1 , 2 , 3 , , N in an initially empty tree.
The result is a tree consisting of only left children. This outcome is not bad, as the
time to construct the tree is only O ( N ) total.

Proof

…

As illustrated in Figure 22.2, each newly added item is made a child of the root. Then,
only one rotation is needed to place the new item at the root. The bad part, as shown
in Figure 22.3, is that accessing the node with key 1 takes N units of time. After the
rotations have been completed, access of the node with key 2 takes N units of time
and access of key 3 takes N - 1 units of time. The total for accessing the N keys in
order is . After they have been accessed, the tree reverts to its
original state and we can repeat the sequence. Thus we have an amortized bound of
only

N

N +

∑

i = Θ N 2 ()

i = 2

Θ( N ) .

1. An insertion counts as an access. Thus an item would always be inserted as a leaf and then
immediately rotated to the root. An unsuccessful search counts as an access on the leaf at
which the search terminates.