amortized analysis of splaying after zig-zig or zig-zagthe depth of position decreases by twoand after zig the depth of decreases by one thusif has depth dsplaying consists of sequence of  / zig-zigs and/or zig-zagsplus one final zig if is odd since single zig-zigzig-zagor zig affects constant number of nodesit can be done in ( time thussplaying position in binary search tree takes time ( )where is the depth of in in other wordsthe time for performing splaying step for position is asymptotically the same as the time needed just to reach that position in top-down search from the root of worst-case time in the worst casethe overall running time of searchinsertionor deletion in splay tree of height is ( )since the position we splay might be the deepest position in the tree moreoverit is possible for to be as large as nas shown in figure thusfrom worst-case point of viewa splay tree is not an attractive data structure in spite of its poor worst-case performancea splay tree performs well in an amortized sense that isin sequence of intermixed searchesinsertionsand deletionseach operation takes on average logarithmic time we perform the amortized analysis of splay trees using the accounting method amortized performance of splay trees for our analysiswe note that the time for performing searchinsertionor deletion is proportional to the time for the associated splaying so let us consider only splaying time let be splay tree with keysand let be node of we define the size (wof as the number of nodes in the subtree rooted at note that this definition implies that the size of nonleaf node is one more than the sum of the sizes of its children we define the rank (wof node as the logarithm in base of the size of wthat isr(wlog( ( )clearlythe root of has the maximum sizenand the maximum ranklog nwhile each leaf has size and rank we use cyber-dollars to pay for the work we perform in splaying position in and we assume that one cyber-dollar pays for zigwhile two cyber-dollars pay for zig-zig or zig-zag hencethe cost of splaying position at depth is cyber-dollars we keep virtual account storing cyber-dollars at each position of note that this account exists only for the purpose of our amortized analysisand does not need to be included in data structure implementing the splay tree