algorithm skipsearch( )inputa search key outputposition in the bottom list with the largest key such that key( < start {begin at start positionwhile below( none do below( {drop downwhile >key(next( )do next( {scan forwardreturn code fragment algorthm to search skip list for key as it turns outthe expected running time of algorithm skipsearch on skip list with entries is (log nwe postpone the justification of this facthoweveruntil after we discuss the implementation of the update methods for skip lists navigation starting at the position identified by skipsearch(kcan be easily used to provide the additional forms of searches in the sorted map adt ( find gtfind rangeinsertion in skip list the execution of the map operation [kv begins with call to skipsearch(kthis gives us the position of the bottom-level item with the largest key less than or equal to (note that may hold the special item with key -if key(pkthe associated value is overwritten with otherwisewe need to create new tower for item (kvwe insert (kvimmediately after position within after inserting the new item at the bottom levelwe use randomization to decide the height of the tower for the new item we "flipa coinand if the flip comes up tailsthen we stop here else (the flip comes up heads)we backtrack to the previous (next higherlevel and insert (kvin this level at the appropriate position we again flip coinif it comes up headswe go to the next higher level and repeat thuswe continue to insert the new item (kvin lists until we finally get flip that comes up tails we link together all the references to the new item (kvcreated in this process to create its tower coin flip can be simulated with python' built-in pseudo-random number generator from the random module by calling randrange( )which returns or each with probability / we give the insertion algorithm for skip list in code fragment and we illustrate it in figure the algorithm uses an insertafterabove(pq(kv)method that inserts position storing the item (kvafter position (on the same level as pand above position qreturning the new position (and setting internal references so that nextprevaboveand below methods will work correctly for pqand rthe expected running time of the insertion algorithm on skip list with entries is (log )which we show in section