balanced binary search trees analysis of this is done on case by case basis and is not present in this text but may be found in texts on-line these proofs show that splay trees do indeed operate as efficiently as avl trees on randomly accessed data in additionthe splaying operation used when inserting or looking up value exploits spatial locality in the data data values that are frequently looked up will make their way toward the top of the tree so as to be more efficiently looked up in the future while taking advantage of spatial locality is certainly desirable if present in the datait does not improve the overall computational complexity of splay tree insert and lookup operations howeverthis does not happen in the average case on randomly inserted and looked up values in factthe recursive implementation of splay trees presented in the previous section exhibits (log naverage insert and lookup time on randomly distributed set of values and performs better in random sample than the avl tree implementation insertlookupand delete operations on an avl tree can be completed in (log ntime in the average case this holds for splay trees as well traversal of an avl or splay tree runs in (ntime and yields its items in ascending or descending order (depending on how the iterator is writtenwhile the quicksort algorithm can sort the items of list just as efficientlyavl and splay trees are data structures that allow many insert and delete operations while still maintaining the ordering of their elements an avl or splay tree may be practical choice if data structure is needed that efficiently implements lookupdeleteand insert operations while also allowing the sequence of values to be iterated over in ascending or descending order the advantage of avl trees lies in their ability to maintain the ordering of elements while guaranteeing efficient lookupinsertand delete complexity splay trees work just as well in almost all cases and in the case of the recursive splay tree implementation described in this it performs even better than the avl tree implementation on random data sets the difference in performance between the avl tree and the recursive splay tree performance numbers is the difference between maintaining the balance explicitly in the avl tree and getting good enough balance in the splay tree summary this presented several implementations of height-balanced avl trees and splay trees recursive and iterative insert algorithms were presented both balance maintaining and height maintaining avl nodes were discussed the recursive insert algorithms for both avl and splay trees result in very clean code without many special caseswhile the iterative versions needs few more if statements to handle some conditions in some instance the iterative version may be slightly more efficient than the recursive version since there is cost associated with function calls in any languagebut the experimental results obtained from the experiments performed in this seem to suggest that the recursive implementations operate very efficiently when written in python this copy belongs to 'acha