Regarding splay trees

Question

I am reading about splay trees in Data structures and algorithms by Mark Allen Wesis

The splaying strategy is similar to the rotation idea, except that we are a little more selective about how rotations are performed. We will still rotate bottom up along the access path. Let x be a (nonroot) node on the access path at which we are rotating. If the parent of x is the root of the tree, we merely rotate x and the root. This is the last rotation along the access path. Otherwise, x has both a parent (p) and a grandparent (g), and there are two cases, plus symmetries, to consider. The first case is the zig-zag case, Here x is a right child and p is a left child (or vice versa). If this is the case, we perform a double rotation, exactly like an AVL double rotation. Otherwise, we have a zig-zig case: x and p are either both left children or both right children.

In above text what does author mean by following statement "There are two cases plus symmetries"? two cases are given but what are symmetires here?

Thanks!

Answer 1

I think it's just pretty basic axial symetry:

example for a zig zag case, here are 2 symetric trees:

     g
    / \ 
    p  d
   /\
  c  x
    / \
   a   b

     g
    / \ 
   d   p
      /\
     x  c
    / \
   a   b

Answer 2

For example, say a case is "When the node in questions is the right child of its parent and the parent is the left child of the grandparent" In this case you do a left rotation and then a right rotation. So the node will come up to the grand parent.

The symmetric part of this case is "When the node in questions is the left child of its parent and the parent is the right child of the grandparent" In this case you do a right rotation and then a left rotation. So the node will come up to the grand parent.

replace left with right and right with left you get the symmetric case.

There are only 3 cases for rotation in a splay tree. Listed it here You can see the runtime difference in searching with and without splaying.