notes operations splay trees support the following operations we write for setsx for elements and for key values splay(skreturns an access to an element with key in the set in case no such element existswe return an access to the next smaller or larger element split(skreturns (s_ ,s_ )where for each in s_ holdskey[ < and for each in s_ holdsk key[yjoin(s_ ,s_ returns the union s_ s_ conditionfor each in s_ and each in s_ < insert( ,xaugments by delete( ,xremoves from each splitjoindelete and insert operation can be reduced to splay operations and modifications of the tree at the root which take only constant time thusthe run time for each operation is essentially the same as for splay operation splay operation the most important tree operation is splay( )which moves an element to the root of the tree in case is not present in the treethe last element on the search path for is moved instead the run time for splay(xoperation is proportional to the length of the search path for while searching for we traverse the search path top-down let be the last node on that path in second stepwe move along that path by applying rotations as described later the time complexity of maintaining splay tree is analyzed using an amortized analysis consider sequence of operations op_ op_ op_m assume that our data structure has potential one can think of the potential as bank account each tree operation op_i has actual costs proportional to its running time we're paying for the costs c_i of op_i with its amortized costs a_i the difference between concrete and amortized costs is charged against the potential of the data structure this means that we're investing in the potential if the amortized costs are higher that the actual costsotherwise we're decreasing the potential thuswe're paying for the sequence op_ op_ op_m no more than the initial potential plus the sum of the amortized costs a_ a_ a_m the trick of the analysis is to define potential function and to show that each splay operation has amortized costs (ln ( )it follows that the sequence has costs ( ln (nn ln ( ) rotations the splay operation moves the accessed element to the root of the tree this is done using rotations on and parent and grandparent there are two kinds of double rotations and one single rotation due to symmetrywe need mirror-image versions of each rotation type or respectively type or respectively type the last case deals with the situation that the splay node is child of the root thuswe need single rotation or respectively lovely professional university