Lecture Data Structures: Lesson 40 provide students with knowledge about skip list: formally; skip list: search; repeatedly toss a coin until we get tails, and we denote with i the number of times the coin came up heads; skip list: insertion; randomized algorithms; . | Skip List formally A skip list for a set S of distinct key element items is a series of lists S0 S1 Sh such that 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 Lecture Data Structure Dr. Sohail Aslam Skip List formally S3 S2 31 S1 23 31 34 64 S0 12 23 26 31 34 44 56 64 78 Skip List Search We search for a key x as follows We start at the first position of the top list At the current position p we compare x with y key after p x y we return element after p x y we scan forward x y we drop down If we try to drop down past the bottom list we return NO_SUCH_KEY Skip List Search Example search for 78 S3 S2 31 S1 23 31 34 64 S0 12 23 26 31 34 44 56 64 78 Skip List Insertion To insert an item x o into a skip list we use a randomized algorithm We repeatedly toss a coin until we get tails and we denote with i the number of times the coin came up heads If i h we add to the skip list new lists Sh 1 Si 1 each containing only the two special keys Skip List Insertion To insert an item x o into a skip list we use a randomized algorithm cont We search for x in the skip list and find the positions p0 p1 pi of the items with largest key less than x in each list S0 S1 Si For j 0 i we insert item x o into list Sj after position pj Skip List Insertion Example insert key 15 with i 2 S3 p2 S2 S2 15 p1 S1 23 S1 15 23 p0 S0 10 23 36 S0 10 15 23 36 Randomized Algorithms A randomized algorithm performs coin tosses . uses random bits to control its execution It contains statements of the type b random if b Skip List Deletion To remove an item with key x from a skip list we proceed as follows We search for x in the skip list and find the positions p0 p1 pi of the items with key x where position pj is in list Sj We remove positions p0 p1 pi from the lists S0 S1 Si We remove all but one list containing only the two special keys Skip List
