Skip to main content
Engineering LibreTexts

4.2: SkiplistSSet - An Efficient SSet

  • Page ID
    8451
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

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

        Node<T> findPredNode(T x) {
            Node<T> u = sentinel;
            int r = h;
            while (r >= 0) {
                while (u.next[r] != null && compare(u.next[r].x,x) < 0)
                    u = u.next[r];   // go right in list r
                r--;               // go down into list r-1
            }
            return u;
        }
        T find(T x) {
            Node<T> u = findPredNode(x);
            return u.next[0] == null ? null : u.next[0].x;
        }
    

    Following the search path for \(\mathtt{y}\) is easy: when situated at some node, \(\mathtt{u}\), in \(L_{\mathtt{r}}\), we look right to \(\texttt{u.next[r].x}\). If \(\mathtt{x}>\texttt{u.next[r].x}\), then we take a step to the right in \(L_{\mathtt{r}}\); otherwise, we move down into \(L_{\mathtt{r}-1}\). Each step (right or down) in this search takes only constant time; thus, by Lemma 4.1.1, the expected running time of \(\mathtt{find(x)}\) is \(O(\log \mathtt{n})\).

    Before we can add an element to a SkipListSSet, we need a method to simulate tossing coins to determine the height, \(\mathtt{k}\), of a new node. We do so by picking a random integer, \(\mathtt{z}\), and counting the number of trailing \(1\)s in the binary representation of \(\mathtt{z}\):1

        int pickHeight() {
            int z = rand.nextInt();
            int k = 0;
            int m = 1;
            while ((z & m) != 0) {
                k++;
                m <<= 1;
            }
            return k;
        }
    

    To implement the \(\mathtt{add(x)}\) method in a SkiplistSSet we search for \(\mathtt{x}\) and then splice \(\mathtt{x}\) into a few lists \(L_0\),..., \(L_{\mathtt{k}}\), where \(\mathtt{k}\) is selected using the \(\mathtt{pickHeight()}\) method. The easiest way to do this is to use an array, \(\mathtt{stack}\), that keeps track of the nodes at which the search path goes down from some list \(L_{\mathtt{r}}\) into \(L_{\mathtt{r}-1}\). More precisely, \(\mathtt{stack[r]}\) is the node in \(L_{\mathtt{r}}\) where the search path proceeded down into \(L_{\mathtt{r}-1}\). The nodes that we modify to insert \(\mathtt{x}\) are precisely the nodes \(\mathtt{stack[0]},\ldots,\mathtt{stack[k]}\). The following code implements this algorithm for \(\mathtt{add(x)}\):

        boolean add(T x) {
            Node<T> u = sentinel;
            int r = h;
            int comp = 0;
            while (r >= 0) {
                while (u.next[r] != null 
                       && (comp = compare(u.next[r].x,x)) < 0)
                    u = u.next[r];
                if (u.next[r] != null && comp == 0) return false;
                stack[r--] = u;          // going down, store u
            }
            Node<T> w = new Node<T>(x, pickHeight());
            while (h < w.height())
                stack[++h] = sentinel;   // height increased
            for (int i = 0; i < w.next.length; i++) {
                w.next[i] = stack[i].next[i];
                stack[i].next[i] = w;
            }
            n++;
            return true;
        }
    
    skiplist-add.png
    Figure \(\PageIndex{1}\): Adding the node containing \(3.5\) to a skiplist. The nodes stored in \(\mathtt{stack}\) are highlighted.

    Removing an element, \(\mathtt{x}\), is done in a similar way, except that there is no need for \(\mathtt{stack}\) to keep track of the search path. The removal can be done as we are following the search path. We search for \(\mathtt{x}\) and each time the search moves downward from a node \(\mathtt{u}\), we check if \(\texttt{u.next.x}=\mathtt{x}\) and if so, we splice \(\mathtt{u}\) out of the list:

        boolean remove(T x) {
            boolean removed = false;
            Node<T> u = sentinel;
            int r = h;
            int comp = 0;
            while (r >= 0) {
                while (u.next[r] != null 
                       && (comp = compare(u.next[r].x, x)) < 0) {
                    u = u.next[r];
                }
                if (u.next[r] != null && comp == 0) {
                    removed = true;
                    u.next[r] = u.next[r].next[r];
                    if (u == sentinel && u.next[r] == null)
                        h--;  // height has gone down
                }
                r--;
            }
            if (removed) n--;
            return removed;
        }
    
    skiplist-remove.png
    Figure \(\PageIndex{2}\): Removing the node containing \(3\) from a skiplist.

    \(\PageIndex{1}\) Summary

    The following theorem summarizes the performance of skiplists when used to implement sorted sets:

    Theorem \(\PageIndex{1}\).

    SkiplistSSet implements the SSet interface. A SkiplistSSet supports the operations \(\mathtt{add(x)}\), \(\mathtt{remove(x)}\), and \(\mathtt{find(x)}\) in \(O(\log \mathtt{n})\) expected time per operation.


    Footnotes

    1This method does not exactly replicate the coin-tossing experiment since the value of \(\mathtt{k}\) will always be less than the number of bits in an \(\mathtt{int}\). However, this will have negligible impact unless the number of elements in the structure is much greater than \(2^{32}=4294967296\).


    This page titled 4.2: SkiplistSSet - An Efficient SSet is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin (Athabasca University Press) .

    • Was this article helpful?