trees these rotations have the effect of pushing all the way to the rootso that future accesses on are easy (for whileunfortunatelyit has pushed another node ( almost as deep as used to be an access on that node will then push another node deepand so on although this strategy makes future accesses of cheaperit has not significantly improved the situation for the other nodes on the (originalaccess path it turns out that it is possible to prove that using this strategythere is sequence of operations requiring ( ntimeso this idea is not quite good enough the simplest way to show this is to consider the tree formed by inserting keys into an initially empty tree (work this example outthis gives tree consisting of only left children this is not necessarily badthoughsince the time to build this tree is (ntotal the bad part is that accessing the node with key takes units of timewhere each node on the access path counts as one unit after the rotations are completean access of the node with key takes units of timekey takes unitsand so on the total for accessing all the keys in order is nn = ( after they are accessedthe tree reverts to its original stateand we can repeat the sequence splaying the splaying strategy is similar to the rotation idea aboveexcept that we are little more selective about how rotations are performed we will still rotate bottom up along the access