take (log ntime but the overall time to insert or lookup an item might improve little bit this is the motivation for splay tree in splay treeeach insert or lookup moves the inserted or looked up value to the root of the tree through process called splaying when deleting valuethe parent may be splayed to the root of the tree splay tree is still binary search tree splay trees usually remain well-balanced but unlike an avl treea splay tree does not contain any balance or height information splaying node to the root involves series of rotatesmuch like the rotates of avl treesbut with slight difference it is interesting to note that while splay trees are designed to exploit spatial locality in the datathey are not dependent on spatial locality to perform well splay trees function as well or better than avl trees in practice on completely random data sets there are several things that are interesting about splay trees firstthe splaying process does not require the balance or any other information about the height of subtrees the binary search tree structure is good enough splay trees don' stay perfectly balanced all the time howeverbecause they stay relatively balancedthey are balanced enough to get an average case complexity of (log nfor insertlookupand delete operations this idea that they are good enough is the basis for what is called amortized complexity which is discussed later in chap and later in this splaying is relatively simple to implement in this text we cover two bottom-up splay tree implementations splay trees can be implemented either iteratively or recursively and we examine both implementations in chap binary search tree insert was implemented recursively if splaying is to be done recursivelythe splay can be part of the insert function if written iterativelya stack can be used in the splaying process the following sections cover both the iterative and recursive implementations but first we examine the rotations that are used in splaying splay rotations each time value is inserted or looked up the node containing that value is splayed to the top through series of rotate operations unlike avl treesa splay tree employs double rotation to move node up to the level of its grandparent if grandparent exists through series of double rotations the node will either make it to the root or to the child of the root if the splayed node makes it to the child of the roota single rotation is used to bring it to the root the single rotate functions are often labelled zig or zag while the double rotations are called zig-zig or zig-zag operations depending on the direction of the movement of the splayed node sometimes the node moves with zig-zag motion while other times it moves with zig-zig motion splaying happens when value is inserted intolooked upor deleted from splay tree when value is looked up either the searched value is splayed to the top or the this copy belongs to 'acha