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

bound guarantees that any sequence of M splays will use at most 3 M log
N + M tree rotations. Consequently, any sequence of M operations starting
from an empty tree will take a total of at most O ( M log N ) time.

analysis of bottom-up splaying

22.4

The analysis of the splay tree algorithm is complicated because each splay
can vary from a few rotations to O ( N ) rotations. Each splay can drastically
change the structure of the tree. In this section we prove that the amortized
cost of a splay is at most 3 log N + 1 single rotations. The splay tree's amortized
bound guarantees that any sequence of M splays use at most 3 M log N + M tree
rotations, and consequently any sequence of M operations starting from an
empty tree take a total of at most O ( M log N ) time.

The analysis of the
splay tree is com-
plicated and is part
of a much larger
theory of amortized
analysis.

To prove this bound, we introduce an accounting function called the
potential function . Not maintained by the algorithm, the potential function is
merely an accounting device used to establish the required time bound. Its
choice is not obvious and is the result of a large amount of trial and error.
For any node i in the splay tree, let S ( i ) be the number of descendants of i
(including i itself). The potential function is the sum, over all nodes i in the
tree T, of the logarithm of S ( i ). Specifically,

The potential func-
tion is an account-
ing device used to
establish the
required time
bound.

The rank of a node
is the logarithm of
its size. Ranks and
sizes are not main-
tained but are
merely accounting
tools for the proof.
Only nodes on the
splay path have
their ranks
changed.

Φ () T = log

iT ∈ ∑

Si ()

To simplify the notation, we let R ( i ) = log S ( i ), which gives

Φ () T =

∑

Ri ()

The term R ( i ) represents the rank of node i, or the logarithm of its size.
Note that the rank of the root is log N . Recall that neither ranks nor sizes are
maintained by splay tree algorithms (unless, of course, order statistics are
needed). When a zig rotation is performed, only the ranks of the two nodes
involved in the rotation change. When a zig-zig or a zig-zag rotation is per-
formed, only the ranks of the three nodes involved in the rotation change. And
finally, a single splay consists of some number of zig-zig or zig-zag rotations
followed by perhaps one zig rotation. Each zig-zig or zig-zag rotation can be
counted as two single rotations.
For Theorem 22.2 we let Φ i

Φ 0

be the potential function of the tree immedi-

ately after the i th splay and be the potential prior to the first splay.