Page 167 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Figure 7.2: Splay character ‘a’ in a LST

h

h
g

r
d
e Splay at ‘a’ e g

d a

f
c b

b
c

a

Rules for Splaying

Here are the rules for splaying. Denote the node being accessed as X, the parent of X as P and
the grandparent of X as G:

Zig: In this case, P is the root of the tree.
1. Zig_Left( X ) if X is a left child.
2. Zig_Right( X ) if X is a right child.

162 LOVELY PROFESSIONAL UNIVERSITY