amortized analysis we also see that si ( >si (xconsequentlyri ( <ri (pmaking this substitution gives atzig-zag < rf (prf ( ri (xfrom figure we see that sf (psf ( <sf (xif we apply lemma we obtain log sf (plog sf ( < log sf ( by the definition of rankthis becomes rf (prf ( < rf ( substituting thiswe obtain atzig-zag < rf ( ri ( < (rf (xri ( )since rf ( >ri ( )we obtain atzig-zag < (rf (xri ( )zig-zig stepthe third case is the zig-zig the proof of this case is very similar to the zig-zag case the important inequalities are rf (xri ( )rf ( >rf ( )ri ( <ri ( )and si (xsf ( <sf (xwe leave the details as exercise the amortized cost of an entire splay is the sum of the amortized costs of each splay step figure shows the steps that are performed in splay at node let ( ) ( ) ( )and ( be the rank of node in each of the four trees the cost of the first stepwhich is zig-zagis at most ( ( ( )the cost of the second stepwhich is zig-zigis ( ( ( )the last step is zig and has cost no larger than ( ( ( ) the total cost thus telescopes to ( ( ( ) figure the splaying steps involved in splaying at node