balanced binary search trees deleting an item from an avl tree deleting value from an avl tree can be accomplished in the same way as described in programming problem from chap howeverit is necessary to adjust balances on the way back from deleting the final leaf node this can be done either by maintaining path stack if delete is implemented iteratively or by adjusting balances or heights while returning from the recursive calls in recursive implementation of delete in either casewhen adjusted balance of node on the path reaches left rotation is required to rebalance the tree if the adjusted balance of node on the path results in - then right rotation is required these rotations may cascade back up the path to the root of the tree splay trees avl trees are always balanced since the balance of each node is computed and maintained to be either - or because they are balanced they guarantee (log nlookupinsertand delete time an avl tree is binary search tree so it also maintains its items in sorted order allowing iteration from the smallest to largest item in (ntime while there doesn' seem to be many downsides to this data structure there is possible improvement in the form of splay trees one of the criticisms of avl trees is that each node must maintain its balance the extra work and extra space that are required for this balance maintenance might be unnecessary what if binary search tree could maintain its balance good enough without storing the balance in each node storing the balance of each node or the height of each node increases the size of the data in memory this was bigger concern when memory sizes were smaller butmaintaining the extra information takes extra time as well what if we could not only reduce the overall data size but eliminate some of the work in maintaining the balance of binary search tree the improvement to avl trees incorporates the concept of spatial locality this idea reflects the nature of interaction with large data sets access to large data set is often localizedmeaning that the same piece or several pieces of data might be accessed several times over short period of time and then may not be accessed for some time while some other relatively small subset of the data is accessed by either inserting new values or looking up old values spatial locality means that relatively small subset of data is accessed over short period of time in terms of our example at the beginning of this tree containing cookies may have cookies that are assigned when user first visits website user coming into the website will interact for while and then leaveprobably not coming back soon again the set of users who are interacting with the web server will change over time but it is always relatively small subset compared to the overall number of entries in the tree if we could store the cookies of the recent users closer to the top of the treewe might be able to improve the overall time for looking up and inserting new value in the tree the complexity won' improve inserting an item will still this copy belongs to 'acha