splay trees another way we can implement the fundamental dictionary operations is to use balanced search tree data structure 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 use any explicit rules to enforce its balance insteadit applies certain move-to-root operationcalled splayingafter every accessin order to keep the search tree balanced in an amortized sense the splaying operation is performed at the bottom-most node reached during an insertiondeletionor even search the surprising thing about splaying is that it allows us to guarantee an amortized running timefor insertionsdeletionsand searchesthat is logarithmic the structure of splay tree is simply binary search tree in factthere are no additional heightbalanceor color labels that we associate with the nodes of this tree splaying given an internal node of binary search tree twe 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 replace by xmaking child of and child of ywhile maintaining the inorder relationships of the nodes in figure zig-zig(abefore(bafter there is another symmetric configuration where and are left children