< ( '( )- ( )proposition let be splay tree with root tand let be the total variation of (tcaused by splaying node at depth we have < ( (tr( ) + justificationsplaying node consists of / splaying substepseach of which is zig-zig or zig-zagexcept possibly the last onewhich is zig if is odd let (xr(xbe the initial rank of xand for plet (xbe the rank of after the ith substep and be the variation of (tcaused by the ith substep by lemma the total variation of (tcaused by splaying is ( (xr ( ) < ( (tr( ) by proposition if we make payment of ( (tr( ) cyber-dollars towards the splaying of node xwe have enough cyber-dollars to maintain the invariantkeeping (vcyber-dollars at each node in tand pay for the entire splaying workwhich costs dollars since the size of the root is its rank (tlog( in additionwe have (xr(tthusthe payment to be made for splaying is (logncyber-dollars to complete our analysiswe have to compute the cost for maintaining the invariant when node is inserted or deleted when inserting new node into splay tree with keysthe ranks of all the ancestors of are increased namelylet be the ancestors of vwhere vv is the parent of - and is the root for ,dlet '( and ( be the size of before and after the insertionrespectivelyand let '( and ( be the rank of before and after the insertionrespectively we have '{ {