# 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](/files/-LRPqu7R-S0Fwffptto5)

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

#### Two Linked Lists

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

![图 2 - Two Linked Lists](/files/-LRPtkDIci32oIfbIfh5)

如图 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.046/skip-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.