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

figure 22.6
Zig-zig case (unique
to the splay tree); the
symmetric case has
been omitted

G X

D A

P P

C B

X G

AB C D

The difference seems quite minor, and the fact that it matters is somewhat
surprising. To see this difference consider the sequence that gave the poor
results in Theorem 22.1. Again, we insert keys 1, 2, 3, ..., N in an initially
empty tree in linear total time and obtain an unbalanced left-child-only tree.
However, the result of a splay is somewhat better, as shown in Figure 22.7.
After the splay at node 1, which takes N node accesses, a splay at node 2 takes
only roughly accesses, rather than N - 1 accesses. Splaying not only
moves the accessed node to the root, but it also roughly halves the depth of
most nodes on the access path (some shallow nodes are pushed down at most
two levels). A subsequent splay at node 2 brings nodes to within of the
root. Splaying is repeated until the depth becomes roughly log N . In fact, a
complicated analysis shows that what used to be a bad case for the rotate-to-
root algorithm is a good case for splaying: Sequential access of the N items in
the splay tree takes a total of only O ( N ) time. Thus we win on easy input. In
Section 22.4 we show, by subtle accounting, that there are no bad access
sequences.

Splaying has the
effect of roughly
halving the depth of
most nodes on the
access path and
increasing by at
most two levels the
depth of a few
other nodes.

N 2 ⁄

N 4 ⁄

figure 22.7
Result of splaying at
node 1 (three zig-zigs)

7 7 7 1

6

6 6 6

4 7

5 5 1

4 2 5

4 4

2 5 3

3 1

3

2 2

1

3