4: Skiplists

Open Data Structures - An Introduction · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    4: Skiplists

    In this chapter, we discuss a beautiful data structure: the skiplist, which has a variety of applications. Using a skiplist we can implement a List that has \(O(\log n)\) time implementations of \(\mathtt{get(i)}\), \(\mathtt{set(i,x)}\), \(\mathtt{add(i,x)}\), and \(\mathtt{remove(i)}\). We can also implement an SSet in which all operations run in \(O(\log \mathtt{n})\) expected time.

    The efficiency of skiplists relies on their use of randomization. When a new element is added to a skiplist, the skiplist uses random coin tosses to determine the height of the new element. The performance of skiplists is expressed in terms of expected running times and path lengths. This expectation is taken over the random coin tosses used by the skiplist. In the implementation, the random coin tosses used by a skiplist are simulated using a pseudo-random number (or bit) generator.


    This page titled 4: Skiplists was last modified on Sat, 01 May 2021 15:12:14 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin (Athabasca University Press) .