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

The splaying strategy is similar to the simple rotate-to-root strategy, but
it has one subtle difference. We still rotate from the bottom up along the
access path (later in the chapter we describe a top-down strategy). If X is a
nonroot node on the access path on which we are rotating and the parent of
X is the root of the tree, we merely rotate X and the root, as shown in
Figure 22.4. This rotation is the last along the access path, and it places X at
the root. Note that this action is exactly the same as that in the rotate-to-root
algorithm and is referred to as the zig case.

Otherwise, X has both a parent P and a grandparent G, and we must con-
sider two cases and symmetries. The first case is the so called zig-zag case,
which corresponds to the inside case for AVL trees. Here X is a right child and
P is a left child (or vice versa). We perform a double rotation exactly like an
AVL double rotation, as shown in Figure 22.5. Note that, as a double rotation
is the same as two bottom-up single rotations, this case is no different than the
rotate-to-root strategy. In Figure 22.1, the splay at node 3 is a single zig-zag
rotation.

The zig and zig-zag
cases are identical
to rotate-to-root.

The final case, the zig-zig case, is unique to the splay tree and is the out-
side case for AVL trees. Here, X and P are either both left children or both
right children. In this case, we transform the left-hand tree of Figure 22.6 to
the right-hand tree. Note that this method differs from the rotate-to-root strat-
egy. The zig-zig splay rotates between P and G and then X and P, whereas the
rotate-to-root strategy rotates between X and P and then between X and G .

The zig-zig case is
unique to the splay
tree.

figure 22.4
The zig case (normal
single rotation)

P X

C A

X P

A B B C

figure 22.5
The zig-zag case
(same as a double
rotation); the
symmetric case has
been omitted

G X

D

P P G

A A B CD

X

BC