performance analysis in the worst case splay tree may become stick resulting in (ncomplexity for each lookupinsertand delete operation while avl trees guarantee (log ntime for lookupinsertand delete operations it would appear that avl trees might have better performance howeverthis does not seem to be the case in practice close to , insert and , random lookups were performed in an experiment using pre-generated dataset the insert and lookup operations were identified in the dataset with all looked up values being found in the tree the average combined insert and lookup time were recorded in fig for an avl treea splay tree implemented iterativelyand the recursive implementation of splay tree insert and lookup the results show that the recursive splay tree implementation performs better on random set of values than the avl tree implementation the experiment suggests that splay trees also exhibit (log ncomplexity in practice for insert and lookup operations in figs and we got an intuitive understanding of how splay trees maintain balance through their specialized double rotations howeverit is not very convincing argument to say that the double rotations appear to make the tree more balanced this idea is formalized using amortized complexity amortizationfirst encountered in chap is an accounting term used when an expense is spread over number of years as opposed to expensing it all in one year this same principle can be applied to the expense in finding or inserting value in splay tree the complete fig average insert/lookup time this copy belongs to 'acha