in this ranger '( log( '( )log( ( <log( ( + ) ( + thusthe total variation of (tcaused by the insertion is '( )- ( <log( + thereforea payment of (logncyber-dollars is sufficient to maintain the invariant when new node is inserted when deleting node from splay tree with keysthe ranks of all the ancestors of are decreased thusthe total variation of (tcaused by the deletion is negativeand we do not need to make any payment to maintain the invariant when node is deleted thereforewe may summarize our amortized analysis in the following proposition (which is sometimes called the "balance propositionfor splay trees)proposition consider sequence ofm operations on splay treeeach one searchinsertionor deletionstarting from splay tree with zero keys alsolet ni be the number of keys in the tree after operation iand be the total number of insertions the total running time for performing the sequence of operations is which is ( log nin other wordsthe amortized running time of performing searchinsertionor deletion in splay tree is (logn)where is the size of the splay tree at the time thusa splay tree can achieve logarithmic-timeamortized performance for implementing an ordered dictionary adt this amortized performance matches the worst-case performance of avl trees( , treesand red-black treesbut it does so using simple binary tree that does not need any extra balance information stored at each of its nodes in additionsplay trees have number of other interesting properties that are not shared by these other balanced search trees we explore one such additional property in the following proposition (which is sometimes called the "static optimalityproposition for splay trees)