chap advanced tree structures (ad (bfigure splay tree zigzig rotation (athe original tree with spand in zigzig formation (bthe tree after the rotation takes place the positions of subtrees abcand are altered as appropriate to maintain the bst property is the left child of pwhich is in turn the left child of is the right child of pwhich is in turn the right child of thusa zigzig rotation takes place in those situations where zigzag rotation is not appropriate the zigzig rotation is illustrated by figure while figure appears somewhat different from figure in fact the zigzig rotation is identical to the avl tree double rotation note that zigzag rotations tend to make the tree more balancedbecause they bring subtrees and up one level while moving subtree down one level the result is often reduction of the tree' height by one zigzig promotions do not typically reduce the height of the treethey merely bring the newly accessed record toward the root splaying node involves series of double rotations until reaches either the root or the child of the root thenif necessarya single rotation makes the root this process tends to re-balance the tree in any caseit will make frequently accessed nodes stay near the top of the treeresulting in reduced access cost proof that the splay tree does in fact meet the guarantee of ( log nis beyond the scope of this book such proof can be found in the references in section example consider search for value in the splay tree of figure (athe splay tree' search operation is identical to searching in bst howeveronce the value has been foundit is splayed to the root three rotations are required in this example the first is zigzig rotation