# Skip Lists

## 简介

Skip Lists 是一种随机数据结构（Randomized Data Structure），它是 Set (Ordered Set) 的一种实现。它的各操作复杂度如下表所示：

| Operation Name    | Time Complexity | Space Complexity |
| ----------------- | --------------- | ---------------- |
| find-key(k)       | $$O(lgn)$$      | $$O(1)$$         |
| iter()            | $$O(n)$$        | $$O(n)$$         |
| insert(x)         | $$O(lgn)$$      | $$O(1)$$         |
| delete-key(k)     | $$O(lgn)$$      | $$O(1)$$         |
| delete-min/max()  | $$O(lgn)$$      | $$O(1)$$         |
| find-next/prev(k) | $$O(lgn)$$      | $$O(1)$$         |
| find-min/max()    | $$O(lgn)$$      | $$O(1)$$         |
| order-iter()      | $$O(n)$$        | $$O(1)$$         |

### 从 Find/Search 谈起

#### One Linked List

![图 1 - One Linked List](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LRPnRaCjutWjo1NY3C5%2F-LRPqu7R-S0Fwffptto5%2FScreen%20Shot%202018-11-16%20at%2012.50.50%20PM.jpg?alt=media\&token=6c88e35f-478a-49f5-b408-3b31b64894a5)

当我们有一个 Linked List 时，Search 操作在最差情况下的复杂度为 $$θ(n)$$ ，我们有什么方式能够提高它的速度呢？

#### Two Linked Lists

快速公交系统（BRT）与普通公交系统的区别在于：普通公交系统与其它私人交通工具共享车道且每站必停，而快速公交系统独享车道，且只经停部分公交站。那么假如我要从 A 地区 B 地（快速公交不可直达），就可以先从 A 开始乘坐快速公交到达离 B 最近的公交站，再乘坐普通公交到达 B。如果我们把 Search 操作比喻成这样的乘车过程，可以考虑使用两个 Linked Lists：

![图 2 - Two Linked Lists](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LRPnRaCjutWjo1NY3C5%2F-LRPtkDIci32oIfbIfh5%2FScreen%20Shot%202018-11-16%20at%201.03.16%20PM.jpg?alt=media\&token=458e42fb-12df-44ab-a59c-c0266efc3764)

如图 2 所示，举例如下：

14 -> 59：14 -> 34 -> 42 -> 50 -> 59\
14 -> 79：14 -> 34 -> 42 -> 72 -> 79

怎么设计快速公交系统的停靠站能使得公交系统的性能达到最大？直觉告诉我们，将快速公交的停靠站平均分布在普通公交停靠站上。那么这时候 Search 的成本为：

$$
searchcost = |L\_1| + \frac{|L\_2|}{|L\_1|}
$$

求其最小值，可以得到：

$$
|L1|^2 = |L2| = n => |L1| = \sqrt{n}
$$

如此一来，Search 的成本就是：

$$
|L\_1| + \frac{|L\_2|}{|L\_1|} = \sqrt{n} + \frac{n}{\sqrt{n}} = 2\sqrt{n}
$$

#### More Linked Lists

| Number Of Linked Lists | Search Cost                  |
| ---------------------- | ---------------------------- |
| 2                      | $$2\sqrt{n}$$                |
| 3                      | $$3\sqrt\[3]{n}$$            |
| 4                      | $$4\sqrt\[4]{n}$$            |
| ...                    | ...                          |
| $$lgn$$                | $$lgn\sqrt\[lgn]{n} = 2lgn$$ |

使用 $$lgn$$ 个 linked lists 时，已经很像一棵树，如 B 树。

### Skip Lists

完美的 Skip Lists 就是由 $$lgn$$ 个 linked lists 构成的数据结构。

#### Insert(x)

从空的 Skp Lists 开始不断 Insert 元素，就构成了 Skip Lists 的创建过程。如何保证这个过程能够建立出接近完美的 Skip Lists 其实就是 Insert 的实现需要解决的问题。

方案：先用 search/find 找到元素在最底层的位置，将元素插入到最底层中，然后以 1/2 的概率决定是否将该元素插入到上面一层，递归重复。根据概率理论，平均来看 ---

* 1/2 的元素会被插入到上面 0 层
* 1/4 的元素会被插入到上面 1 层
* 1/8 的元素会被插入到上面 2 层
* ...（以此类推）

search 的时间复杂度为 $$O(lgn)$$ ，递归插入的时间复杂度同样为 $$O(lgn)$$ ，因此 insert 的总时间复杂度也为$$O(lgn)$$。

#### Delete(x)

Delete 需要先用 search/find 找到元素的位置，然后从所有可能存在该元素的链表中删除该元素，因此总时间复杂度为$$O(lgn)$$。

具体证明请查阅参考资料。

## 参考

[lecture note](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec07.pdf), [video](https://www.youtube.com/watch?v=2g9OSRKJuzM\&t=2s)