splay trees the next search tree structure we study is known as splay tree this structure is conceptually quite different from the other balanced search trees we discuss in this for splay tree does not strictly enforce logarithmic upper bound on the height of the tree in factthere are no additional heightbalanceor other auxiliary data associated with the nodes of this tree the efficiency of splay trees is due to certain move-to-root operationcalled splayingthat is performed at the bottommost position reached during every insertiondeletionor even search (in essencethis is tree variant of the moveto-front heuristic that we explored for lists in section intuitivelya splay operation causes more frequently accessed elements to remain nearer to the rootthereby reducing the typical search times the surprising thing about splaying is that it allows us to guarantee logarithmic amortized running timefor insertionsdeletionsand searches splaying given node of binary search tree we splay by moving to the root of through sequence of restructurings the particular restructurings we perform are importantfor it is not sufficient to move to the root of by just any sequence of restructurings the specific operation we perform to move up depends upon the relative positions of xits parent yand (if it existsx' grandparent there are three cases that we consider zig-zigthe node and its parent are both left children or both right children (see figure we promote xmaking child of and child of ywhile maintaining the inorder relationships of the nodes in (at (bfigure zig-zig(abefore(bafter there is another symmetric configuration where and are left children