Page 169 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS
P. 169
Advanced Data Structure and Algorithms
Notes
Figure 7.4: Splay Tree Zig_Zag Rotations of Node X
(a): Zig_Right_Zag_Left
(b): Zig_Left_Zag_Right
ZigZig: P is not the root of the tree. X and P are the same type of children (left or right). X, P and
G are in a straight line.
1. Zig_Zig_Left if X and P are both right children.
2. Zig_Zig_Right if X and P are both left children.
Figure 7.5: Splay Tree Zig_Zig Rotations of Node X
(a) Zig_Zig_Left
Contd....
164 LOVELY PROFESSIONAL UNIVERSITY
