Page 168 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS
P. 168
Unit 7: Splay Trees
Notes
Figure 7.3: Splay Tree Zig Rotations of Node X
P P
X C A P
A B B C
(a): Zig_Left
P X
A X P C
B C A B
(b): Zig_Right
ZigZag: P is not the root of the tree. X and P are opposite types of children (left or right). The path
from X to G is “crooked”.
1. Zig_Right_Zag_Left if X is a right child and P is a left child.
2. Zig_Left_Zag_Right if X is a left child and P is a right child.
LOVELY PROFESSIONAL UNIVERSITY 163
