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

figure 22.9
Top-down splay
rotations: (a) zig,
(b) zig-zig, and
(c) zig-zag

X

Y

L R L R

Y

A

A B

X

B

(a)

X Z

L

R L R

Y

A

C

Z

Y

X

A B

B C

(b)

X

Z

L R L R

Y

B

C

Z

Y X

A

B

A C

(c)

item in R; X 's left child is logically made null . 2 As a result, X is the new small-
est element in R, making future attachments easy.
Note that Y does not have to be a leaf for the zig case to apply. If the item
sought is found in Y, a zig case will apply even if Y has children. A zig case
also applies if the item sought is smaller than Y and Y has no left child, even if
Y has a right child, and also for the symmetric case.
A similar dissection applies to the zig-zig case. The crucial point is that a
rotation between X and Y is performed. The zig-zag case brings the bottom
node Z to the top of the middle tree and attaches subtrees X and Y to R and L,
respectively. Note that Y is attached to, and then becomes, the largest item in L .

2. In the code written here, the smallest node in R does not have a null left link because it is
not needed.