Deletion, like insertion, also uses the idea of a cut list, that is, a list of all the predecessors whose links must be repaired to leave out the deleted item.
However, deletion uses a slightly different concept of the cut list, the search cut list. The only difference comes when the skip list allows duplicate keys. When we're inserting a child with a duplicate key, we want it to go after the other children with that key, to guarantee stability.
For deletion and searching, however, we want the cut list to point before the first of any values whose keys are equal to the key we're deleting or searching for.
# - - - S k i p L i s t . d e l e t e - - - def delete ( self, key ): """Delete the first or only child with a given key value. """
First we find the search cut list for the given key. We
also set local variables
nextItem to point to the
predecessor and successor of the cut point at level 0.
See Section 4.18, “
#-- 1 -- # [ cutList := search-cut-list ( key ) # prevItem := first element of search-cut-list ( key ) # nextItem := successor to first element of # search-cut-list ( key ) ] cutList = self.__searchCutList ( key ) prevItem = cutList nextItem = prevItem.links
If the cut point is before the terminator, or the element
after the cut point does not have the key value we're
looking for, we're done, and we return
None to signify failure to delete
anything. See Section 4.13, “
#-- 2 -- # [ if (nextItem is self.__terminator) or # ( cmp ( key-of ( nextItem's child ), key ) ) > 0 ) -> # return None # else -> I ] if ( ( nextItem is self.__terminator ) or ( self.__compareItemKey ( nextItem, key ) > 0 ) ): return None
We've found the item to be deleted, and
nextItem points to it. Relink all
the lists that point at that item so that the predecessor
at that level in the cut list points at
nextItem's successor at that level.
#-- 3 -- # [ self := self modified so that for all I in # [0,self.__nLevels), if the skipItem pointed to by # cutList[I] has an (I)th link that points to # nextItem, make that link point where nextItem's # (I)th link points ] for i in xrange(self.__nLevels): #-- 3 body -- # [ if the _SkipItem pointed to by cutList[i] has an # (i)th link that points to nextItem -> # that link is made to point where nextItem's (i)th # link points ] prevItem = cutList[i] if prevItem.links[i] is nextItem: prevItem.links[i] = nextItem.links[i]
Finally, we must adjust
to reflect the deletion of one child, and return the
deleted child value.
We must also set the level-0 link in the deleted
None, for reasons discussed in
Section 3.4, “Classes in this module”.
#-- 4 -- self.__nItems = self.__nItems - 1 nextItem.links = None return nextItem.child