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!
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