- the standard splaying step requires two passesone downward pass to find the node to splayfollowed by an upward pass to splay the node describe method for splaying and searching for in one downward pass each substep now requires that you consider the next two nodes in the path down to xwith possible zig substep performed at the end describe how to perform the zig-zigzig-zagand zig steps - consider variation of splay treescalled half-splay treeswhere splaying node at depth stops as soon as the node reaches depth  / perform an amortized analysis of half-splay trees - describe sequence of accesses to an -node splay tree where is oddthat results in consisting of single chain of nodes such that the path down alternates between left children and right children - as positional structureour treemap implementation has subtle flaw position instance associated with an key-value pair (kvshould remain valid as long as that item remains in the map in particularthat position should be unaffected by calls to insert or delete other items in the collection our algorithm for deleting an item from binary search tree may fail to provide such guaranteein particular because of our rule for using the inorder predecessor of key as replacement when deleting key that is located in node with two children given an explicit series of python commands that demonstrates such flaw - how might the treemap implementation be changed to avoid the flaw described in the previous problemprojects - perform an experimental study to compare the speed of our avl treesplay treeand red-black tree implementations for various sequences of operations - redo the previous exerciseincluding an implementation of skip lists (see exercise - - implement the map adt using ( tree (see section - redo the previous exerciseincluding all methods of the sorted map adt (see section - redo exercise - providing positional supportas we did for binary search trees (section )so as to include methods first)last)before( )after( )and find position(keach item should have distinct position in this abstractioneven though several items may be stored at single node of tree