chap advanced tree structures ( log ntime for tree of nodes whenever > thusa single insert or search operation could take (ntime howeverm such operations are guaranteed to require total of ( log ntimefor an average cost of (log nper access operation this is desirable performance guarantee for any search-tree structure unlike the avl treethe splay tree is not guaranteed to be height balanced what is guaranteed is that the total cost of the entire series of accesses will be cheap ultimatelyit is the cost of the series of operations that mattersnot whether the tree is balanced maintaining balance is really done only for the sake of reaching this time efficiency goal the splay tree access functions operate in manner reminiscent of the moveto-front rule for self-organizing lists from section and of the path compression technique for managing parent-pointer trees from section these access functions tend to make the tree more balancedbut an individual access will not necessarily result in more balanced tree whenever node is accessed ( when is inserteddeletedor is the goal of search)the splay tree performs process called splaying splaying moves to the root of the bst when is being deletedsplaying moves the parent of to the root as in the avl treea splay of node consists of series of rotations rotation moves higher in the tree by adjusting its position with respect to its parent and grandparent side effect of the rotations is tendency to balance the tree there are three types of rotation single rotation is performed only if is child of the root node the single rotation is illustrated by figure it basically switches with its parent in way that retains the bst property while figure is slightly different from figure in fact the splay tree single rotation is identical to the avl tree single rotation unlike the avl treethe splay tree requires two types of double rotation double rotations involve sits parent (call it )and ' grandparent (call it gthe effect of double rotation is to move up two levels in the tree the first double rotation is called zigzag rotation it takes place when either of the following two conditions are met is the left child of pand is the right child of is the right child of pand is the left child of in other wordsa zigzag rotation is used when gpand form zigzag the zigzag rotation is illustrated by figure the other double rotation is known as zigzig rotation zigzig rotation takes place when either of the following two conditions are met