A SkiplistSSet uses a skiplist structure to implement the SSet interface. When used in this way, the list stores the elements of the SSet in sorted order. The method works by following the search path for the smallest value such that :
Following the search path for is easy: when situated at some node, , in , we look right to . If , then we take a step to the right in ; otherwise, we move down into . Each step (right or down) in this search takes only constant time; thus, by Lemma 4.1, the expected running time of is .
Before we can add an element to a SkipListSSet, we need a method to simulate tossing coins to determine the height, , of a new node. We do so by picking a random integer, , and counting the number of trailing s in the binary representation of :^{4.1}
To implement the
method in a SkiplistSSet we search for
and then splice
into a few lists ,...,
, where
is selected using the
method. The easiest way to do this
is to use an array,
, that keeps track of the nodes at which
the search path goes down from some list
into
.
More precisely,
is the node in
where the search path
proceeded down into
. The nodes that we modify to insert
are precisely the nodes
. The following
code implements this algorithm for
:
Removing an element,
, is done in a similar way, except that there
is no need for
to keep track of the search path. The removal
can be done as we are following the search path. We search for
and each time the search moves downward from a node
, we check if
and if so, we splice
out of the list:
The following theorem summarizes the performance of skiplists when used to implement sorted sets: