notes (bzig_zag_right splay tree algorithms to show that splay trees deliver the promised amortized performancewe define potential function ph(tto keep track of the extra time that can be consumed by later operations on the tree as beforewe define the amortized time taken by single tree operation that changes the tree from to tas the actual time tplus the change in potential ph( ')-ph(tnow consider sequence of operations on treetaking actual times tm and producing trees tm the amortized time taken by the operations is the sum of the actual times for each operation plus the sum of the changes in potentialt tm (ph( ph( )(ph( ph( )(ph(tmph(tm- ) tm ph(tmph( therefore the amortized time for sequence of operations underestimates the actual time by at most the maximum drop in potential ph(tmph( seen over the whole sequence of operations the key to amortized analysis is to define the right potential function given node in binary treelet size(xbe the number of nodes below (including xlet rank(xbe the log base of size(xthen the potential ph(tof tree is the sum of the ranks of all of the nodes in the tree note that if tree has nodes in itthe maximum rank of any node is lg nand therefore the maximum potential of tree is lg this means that over sequence of operations on the treeits potential can decrease by at most lg so the correction factor to amortized time is at most lg nwhich is good nowlet us consider the amortized time of an operation the basic operation of splay trees is splayingit turns out that for tree tany splaying operation on node takes at most amortized time *rank( since the rank of the tree is at most lg( )the splaying operation takes (lg namortized time thereforethe actual time taken by sequence of operations on tree of size is at most (lg nper operation to obtain the amortized time bound for splayingwe consider each of the possible rotation operationswhich take node and move it to new location we consider that the rotation operation itself takes time let (xbe the rank of before the rotationand '(xthe rank of node after the rotation we will show that simple rotation takes amortized time at most ( '(xr( )) and that the other two rotations take amortized time ( '(xr( )there can be only one simple rotation (at the top of the tree)so when the amortized time of all the rotations performed during one splaying is addedall the intermediate terms (xand '(xcancel out and we are left with ( (tr( ) in the worst case where is leaf and has rank this is equal to * ( lovely professional university