notes simple rotation the only two nodes that change rank are and so the cost is '(xr(xr'(yr(ysince decreases in rankthis is at most '(xr(xsince increases in rankr'(xr(xis positive and this is bounded by ( '(xr( )zig-zig rotation only the nodes xyand change in rank since this is double rotationwe assume it has actual cost and the amortized time is '(xr(xr'(yr(yr'(zr(zsince the new rank of is the same as the old rank of zthis is equal to (xr'(yr(yr'(zthe new rank of is greater than the new rank of yand the old rank of is less than the old rank yso this is at most (xr'(xr(xr'( '( (xr'(znowlet (xbe the old size of and let '(xbe the new size of consider the term '(xr(xr'(zthis must be at least because it is equal to lg( '( )/ ( )lg( '( )/ '( )notice that this is the sum of two ratios where '(xis on top nowbecause '( > (xs'( )the way to make the sum of the two logarithms as small as possible is to choose (xs(zs'( )/ but in this case the sum of the logs is therefore the term '(xr(xr'(zmust be at least substituting it for the red abovewe see that the amortized time is at most ( '(xr(xr'( ) '( (xr'( ( '(xr( )as required zig-zag rotation againthe amortized time is '(xr(xr'(yr(yr'(zr(zbecause the new rank of is the same as the old rank of zand the old rank of is less than the old rank of ythis is (xr'(yr(yr'( < (xr'(yr'(znow consider the term '(xr'(yr'(zby the same argument as beforethis must be at least so we can replace the constant above while maintaining bound on amortized time<( '(xr'(yr'( ) (xr'(yr'( ( '(xr( )therefore amortized run time in this case too is bounded by ( '(xr( ))and this completes the proof of the amortized complexity of splay tree operations summary splay trees are self-adjusting binary search trees in which every access for insertion or retrieval of nodelifts that node all the way up to become the rootpushing the other nodes out of the way to make room for this new root of the modified tree hencethe frequently accessed nodes will frequently be lifted up and remain around the root positionwhile the most infrequently accessed nodes would move farther and farther away from the root lovely professional university