ZigZag and ZigZig operation in splay tree?

Question

consider my tree is like this

                 5
                / \
               3   7
              / \ / \
             2  4 6  8

in that, when we search a element 2 that time zigzig operation will be performed, so first we rotate the parent and ancestor of 2 , then we rotate a parent and 2.

in the same case , consider we are searching 4 , that time zigzag operation will be performed. in that first we rotate the 4 and its parent then 4 and its ancestor will be rotated.

why we did like that, in zigzag, why we are not rotate the parent and ancestor instead of searching node and parent.

Please explain me?? Thanks In Advance.

Answer 1

The order of rotations is important. That's what makes the analysis yield O(lg n) time per operation amortized over a sequence of m operations. The splay(x) heuristic moves node x to the root of the tree but instead of just rotating x until it becomes the root, the zigzig step first rotates the parent of x then rotates x. For example, if we were to just rotate x until it becomes the root, then the analysis won't yield something useful.

You are describing something different here. You want to always rotate the parent first and then rotate the child. You need to prove formally that this heuristic is good if you think it is, but to answer the question: rotation order in splay trees guarantees the O(m lg n) bound over a sequence of m operations.