Lecture Data structures and algorithms in Java (6th edition): Chapter 10.4 - Goodrich, Tamassia, Goldwasser

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 .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.