Skip List
- Dynamic search structure, O(lgn)
2 Sorted Linked List
- L2 stores all elements, L1 stores subset
Search (X)
- Walk right in top list L1 until going right would go too far
- Walk to L2
- Walk right in L2 until find X (or > X)
- For example, serach 59, start 14 of L1, walk to 34, 42, 72, 72 is greater than 59, switch back to 42 and jump to L2 to continue the search until find 59
What keys go in L1
- Best is to spread them out uniformly
- Cost of search, |L1| + |L2|/|L1|
- minimize |L1| + n/|L1|
- |L1|2 = n
- Search cost 2√n
- 3 sorted list, 33√n
- k sorted list, kk√n
- k = lgn, lgnlgn√n = 2lgn
Insert (X)1
- Search (X) to find where to insert in bottom list
- Which other list should add x, flip coin, if head, add it, flip coin, ...
- Store -∞ to the left of each list
Delete (X)1
- find (x) and delete in all lists
Reference
