Ask the web
with the leading AI models

SkiplistSSet: An Efficient SSet                           §4.2


 L5
 L4
 L3
 L2
 L1
 L0              0         1         2         3        4         5            6
      sentinel


        Figure 4.2: The search path for the node containing 4 in a skiplist.


as consisting of a data value, x, and an array, next, of pointers, where
u.next[i] points to u’s successor in the list Li . In this way, the data, x, in
a node is stored only once, even though x may appear in several lists.

                                 SkiplistSSet
struct Node {
  T x;
  int height;            // length of next
  Node *next[];
};

    The next two sections of this chapter discuss two different applica-
tions of skiplists. In each of these applications, L0 stores the main struc-
ture (a list of elements or a sorted set of elements). The primary difference
between these structures is in how a search path is navigated; in partic-
ular, they differ in how they decide if a search path should go down into
Lr−1 or go right within Lr .


4.2 SkiplistSSet: An Efficient SSet

A SkiplistSSet uses a skiplist structure to implement the SSet interface.
When used in this way, the list L0 stores the elements of the SSet in sorted
order. The find(x) method works by following the search path for the
smallest value y such that y ≥ x:

                        SkiplistSSet
Node* findPredNode(T x) {



                                         89

Discussion and Exercises                      §1.8

                      SSet implementations
                       find(x)     add(x)/remove(x)
        SkiplistSSet   O(log n)E   O(log n)E                  § 4.2
        Treap          O(log n) E  O(log n)E                  § 7.2
        ScapegoatTree O(log n)     O(log n)A                  § 8.1
        RedBlackTree   O(log n)    O(log n)                   § 9.2
        BinaryTrieI    O(w)        O(w)                       § 13.1
        XFastTrieI     O(log w)A,E O(w)A,E                    § 13.2
        YFastTrieI     O(log w)A,E O(log w)A,E                § 13.3


                  (Priority) Queue implementations
                         findMin() add(x)/remove()
        BinaryHeap       O(1)        O(log n)A                § 10.1
        MeldableHeap     O(1)        O(log n)E                § 10.2
        I This structure can only store w-bit integer data.



       Table 1.2: Summary of SSet and priority Queue implementations.


1.8   Discussion and Exercises

The List, USet, and SSet interfaces described in Section 1.2 are influ-
enced by the Java Collections Framework [54]. These are essentially sim-
plified versions of the List, Set, Map, SortedSet, and SortedMap inter-
faces found in the Java Collections Framework.
   For a superb (and free) treatment of the mathematics discussed in this
chapter, including asymptotic notation, logarithms, factorials, Stirling’s
approximation, basic probability, and lots more, see the textbook by Ley-
man, Leighton, and Meyer [50]. For a gentle calculus text that includes
formal definitions of exponentials and logarithms, see the (freely avail-
able) classic text by Thompson [71].
   For more information on basic probability, especially as it relates to
computer science, see the textbook by Ross [63]. Another good reference,
which covers both asymptotic notation and probability, is the textbook by
Graham, Knuth, and Patashnik [37].

Exercise 1.1. This exercise is designed to help familiarize the reader with



                                    25

ArrayStack: Fast Stack Operations Using an Array                 §2.1


or remove(i) is at least
                                r
                                X
                                       (ni /2 − 1) ≤ m ,
                                 i=1
which is equivalent to
                                 r
                                 X
                                       ni ≤ 2m + 2r .
                                 i=1
On the other hand, the total time spent during all calls to resize() is
                         r
                         X
                               O(ni ) ≤ O(m + r) = O(m) ,
                         i=1

since r is not more than m. All that remains is to show that the number
of calls to add(i, x) or remove(i) between the (i − 1)th and the ith call to
resize() is at least ni /2.
     There are two cases to consider. In the first case, resize() is being
called by add(i, x) because the backing array a is full, i.e., a.length = n =
ni . Consider the previous call to resize(): after this previous call, the
size of a was a.length, but the number of elements stored in a was at
most a.length/2 = ni /2. But now the number of elements stored in a is
ni = a.length, so there must have been at least ni /2 calls to add(i, x) since
the previous call to resize().
     The second case occurs when resize() is being called by remove(i)
because a.length ≥ 3n = 3ni . Again, after the previous call to resize()
the number of elements stored in a was at least a.length/2 − 1.1 Now
there are ni ≤ a.length/3 elements stored in a. Therefore, the number of
remove(i) operations since the last call to resize() is at least

                        R ≥ a.length/2 − 1 − a.length/3
                           = a.length/6 − 1
                           = (a.length/3)/2 − 1
                           ≥ ni /2 − 1 .

In either case, the number of calls to add(i, x) or remove(i) that occur
between the (i −1)th call to resize() and the ith call to resize() is at least
ni /2 − 1, as required to complete the proof.
   1 The − 1 in this formula accounts for the special case that occurs when n = 0 and
a.length = 1.




                                            35