This chapter provides knowledge of skip lists. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Skip Lists 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Skip Lists S3 -∞ +∞ S2 -∞ 15 S1 -∞ 15 23 15 23 S0 -∞ © 2014 Goodrich, Tamassia, Goldwasser 10 +∞ +∞ 36 +∞ Skip Lists 1 What is a Skip List q A skip list for a set S of distinct (key, element) items is a series of lists S0, S1 , , Sh such that n n n n q Each list Si contains the special keys +∞ and -∞ List S0 contains the keys of S in nondecreasing order Each list is a subsequence of the previous one, ., S0 ⊆ S1 ⊆ ⊆ Sh List Sh contains only the two special keys We show how to use a skip list to implement the map ADT S3 -∞ S2 -∞ S1 -∞ S0 -∞ +∞ 31 23 12 23 © 2014 Goodrich, Tamassia, Goldwasser +∞ 31 26 34 31 34 Skip Lists 64 44 56 64 +∞ 78 +∞ 2 1 Skip Lists 3/19/14 Search We search for a key x in a a skip list as follows: q n n n We start at the first position of the top list At the current position p, we compare x with y ← key(next(p)) x = y: we return element(next(p)) x > y: we “scan forward” x < y: we “drop down” If we try to drop down past the bottom list, we return null Example: search for 78 q S3 -∞ S2 -∞ S1 -∞ S0 -∞ +∞ scan forward drop down 23 12 23 © 2014 Goodrich, Tamassia, Goldwasser 31 +∞ 31 26 34 31 64 34 44 56 64 +∞ 78 +∞ Skip Lists 3 Randomized Algorithms q q A randomized algorithm performs coin tosses (., uses random bits) to control its execution It contains statements of the type b ← random() if b = 0 do A else { b = 1} do B q We analyze the expected running time of a randomized algorithm under the following assumptions n n q Its running time depends on the outcomes of the coin tosses © 2014 Goodrich, Tamassia, Goldwasser q q Skip Lists the coins are unbiased, and the coin tosses are independent The worst-case running time of a .
