trees instead of specifically to ensure that single rotations are done in these cases rather than double rotations we leave verification of the remaining cases as an exercise splay trees we now describe relatively simple data structure known as splay tree that guarantees that any consecutive tree operations starting from an empty tree take at most ( log ntime although this guarantee does not preclude the possibility that any single operation might take (ntimeand thus the bound is not as strong as an (log nworstcase bound per operationthe net effect is the samethere are no bad input sequences generallywhen sequence of operations has total worst-case running time of (mf( ))we say that the amortized running time is ( ( )thusa splay tree has an (log namortized cost per operation over long sequence of operationssome may take moresome less splay trees are based on the fact that the (nworst-case time per operation for binary search trees is not badas long as it occurs relatively infrequently any one accesseven if it takes ( )is still likely to be extremely fast the problem with binary search trees is that it is possibleand not uncommonfor whole sequence of bad accesses to take place the cumulative running time then becomes noticeable search tree data structure with (nworst-case timebut guarantee of at most ( log nfor any consecutive operationsis certainly satisfactorybecause there are no bad sequences if any particular operation is allowed to have an (nworst-case time boundand we still want an (log namortized time boundthen it is clear that whenever node is accessedit must be moved otherwiseonce we find deep nodewe could keep performing accesses on it if the node does not change locationand each access costs ( )then sequence of accesses will cost ( nthe basic idea of the splay tree is that after node is accessedit is pushed to the root by series of avl tree rotations notice that if node is deepthere are many nodes on the path that are also relatively deepand by restructuring we can make future accesses cheaper on all these nodes thusif the node is unduly deepthen we want this restructuring to have the side effect of balancing the tree (to some extentbesides giving good time bound in theorythis method is likely to have practical utilitybecause in many applicationswhen node is accessedit is likely to be accessed again in the near future studies have shown that this happens much more often than one would expect splay trees also do not require the maintenance of height or balance informationthus saving space and simplifying the code to some extent (especially when careful implementations are writtena simple idea (that does not workone way of performing the restructuring described above is to perform single rotationsbottom up this means that we rotate every node on the access path with its parent as an exampleconsider what happens after an access ( findon in the following tree