# skiplist简介

skiplist，即跳表是由William Pugh在1989年发明的，允许快速查询一个有序连续元素的数据链表，搜索、插入、删除的平均时间复杂度均为O(lgn)。

## 1. 背景

A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L -> M -> N


A -> C -> E -> G -> I -> K -> M


bui自然要尽快去吃喝玩乐，那么怎么能尽快的到达城市H呢？很直观的，我们会这么选择

1. 先乘坐快车 A -> C -> E -> G
2. 再乘坐慢车 G -> H

## 2. 推导

### 2.3. skiplist的做法

1/2的元素会在level-1列表出现
1/4的元素会在level-2列表出现
1/8的元素会在level-3列表出现
etc.

 空间 O(n) 高度 O(lgn) 查找 O(lgn) 插入 O(lgn) 删除 O(lgn)

+∞ -∞定义是为了实现上的方便性。

## 3. 具体实现

1. 从top-list的第一个元素开始，也就是-∞
2. 在当前位置p，比较x与p的下一个元素的值y：如果x == y，返回p的下一个元素；如果x > y，p在本层向前移动一个位置(scan forward)；如果 x < y，向下一层(drop down)。
3. 如果尝试在最底层继续向下一层，说明值为x的元素不存在。

## 4. 证明

### 4.1. 空间复杂度

1. level-0层元素个数为n
2. level-1层元素个数为n/2
3. level-2层元素个数为n/4

# 等比数列求和
n + n/2 + n/4 + n/8 + ... = 2n = O(n)


### 4.2. 高度

P{至少一个元素出现}
= P{元素0出现 U 元素1出现 U 元素2出现 U ... U 元素n出现}
<= P{元素0出现} + P{元素1出现} + P{元素2出现} + ... + P{元素n出现}
= n /2^i


with high probability(w.h.p.)if, for any a >= 1, there is an appropriate choice of constants for which E occurs with probability at least 1 - O(1/n^a)。

### 4.3. search and update

scan forward的期望大小为2，因此search的时间复杂度为O(lgn)。

insert/delete的分析与search类似，不再赘述，详细的实现在代码一节里介绍。

A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure.

## 5. 论文补充

skiplist 相比 balanced trees的优势

For many applications, skip lists are a more natural representation than trees, also leading to simpler algorithms. The simplicity of skip list algorithms makes them easier to implement and provides significant constant factor speed improvements over balanced tree and self-adjusting tree algorithms. Skip lists are also very space efficient. They can easily be configured to require an average of 1 1/3 pointers per element (or even less) and do not require balance or priority information to be stored with each node.

Determining MaxLevel Since we can safely cap levels at L(n), we should choose MaxLevel = L(N) (where N is an upper bound on the number of elements in a skip list). If p = 1/2, using MaxLevel = 16 is appropriate for data structures containing up to 216 elements.