Name	Name	Last commit message	Last commit date
parent directory ..
Images	Images
SkipList.playground	SkipList.playground
README.md	README.md
README_en.md	README_en.md

跳表(Skip List)

Skip List is a probablistic data-structure with same logarithmic time bound and efficiency as AVL/ or Red-Black tree and provides a clever compromise to efficiently support search and update operations and is relatively simpler to implement compared to other map data structures.

跳表是一个概率数据结构，具有相同的对数时间限制和作为AVL或红黑树的效率，并提供了一个聪明的妥协有效地支持搜索和更新操作，并且相对简单与其他映射数据结构相比，实现。

A skip list S consists of series of sorted linked lists {L0, ..., Ln}, layered hierarchicaly and each layer L stores a subset of items in layer L0 in incremental order. The items in layers {L1, ... Ln} are chosen at random based on a coin flipping function with probability 1/2 . For traversing, every item in a layer hold references to the node below and the next node. This layers serve as express lanes to the layer underneath them, effectively making fast O(log n) searching possible by skipping lanes and reducing travel distance and in worse case searching degrades to O (n), as expected with regular linked list. 跳表 S 由一系列排序链表 {L0, ..., Ln} 组成，分层次的层次结构和每一层 L 存储图层中的项目子集 L0 按增量顺序。层 {L1, ... Ln} 中的项目是随机选择的基于硬币翻转功能，概率为1/2。为了遍历，每一个图层中的项目包含对下面节点和下一个节点的引用。这个层作为快速通道到它们下面的层，有效地制作快速O(log n) 搜索可以通过跳过车道和减少行驶距离并且在更糟糕的情况下，搜索降级为O(n)，正如预期的那样经常链接名单。

For a skip list S: 对于跳表 S

List L0 contains every inserted item.
For lists {L1, ..., Ln}, Li contains a randomly generated subset of the items in Li-1
Height is determined by coin-flipping.
链表 L0 包含每个插入的项目。
对于列表*{L1, ..., Ln}，Li 包含随机生成的子集物品Li-1*
高度由硬币翻转决定。

Figure 1

搜索

Searching for element N starts by traversing from top most layer Ln until L0. 搜索元素N首先从最顶层Ln遍历到L0。

Our objective is to find an element K such that its value at the rightmost position of current layer, is less-than target item and its subsequent node has a greater-equal value or nil ( K.key < N.key <= (K.next.key or nil) ). if value of K.next is equal to N, search is terminated and we return K.next, otherwise drop underneath using K.down to the node below ( at layer Ln-1 ) and repeat the process until L0 where K.down is nil which indicates that level is L0 and item doesn't exists.

我们的目标是找到一个元素 K，使其在最右边的值当前层的位置，小于目标项及其后续节点大于等于或等于零 ( K.key < N.key <= (K.next.key or nil) 。如果 K.next 的值等于 N，搜索终止，我们返回 K.next，否则使用K.down下面到下面的节点（在层Ln-1）和重复该过程，直到L0，其中K.down为nil，表示该级别是L0且项目不存在。

例子：

插入

Inserting element N has a similar process as searching. It starts by traversing from top most layer Ln until L0. We need to keep track of our traversal path using a stack. It helps us to traverse the path upward when coin-flipping starts, so we can insert our new element and update references to it. 插入元素 N 具有与搜索类似的过程。它开始于从最顶层穿过Ln直到L0。我们需要跟踪我们的情况使用堆栈的遍历路径。它有助于我们在向上穿越路径硬币翻转开始，所以我们可以插入我们的新元素并更新引用它。

Our objective is to find a element K such that its value at the rightmost position of layer Ln, is less-than new item and its subsequent node has a greater-equal value or nil ( K.key < N.key < (K.next.key or nil) ). Push element K to the stack and with element K, go down using K.down to the node below ( at layer Ln-1 ) and repeat the process ( forward searching ) up until L0 where K.down is nil which indicates that level is L0. We terminate the process when K.down is nil. 我们的目标是找到一个元素K，使其在最右边的值层的位置 Ln 小于新项，其后续节点有一个大于等于或等于 ( K.key < N.key < (K.next.key or nil) )。推元素K到堆栈并使用元素K，使用K.down向下移动到下面的节点（在层Ln-1）并重复该过程（向前搜索）直到L0，其中K.down是nil，表示该等级是L0。我们K.down为零时终止进程。

At L0, N can be inserted after K. 在 L0，N可以在K之后插入。

Here is the interesting part. We use coin flipping function to randomly create layers. 这是有趣的部分。我们使用硬币翻转功能随机创建层。

When coin flip function returns 0, the whole process is finished but when returns 1, there are two possibilities: 当硬币翻转功能返回0时，整个过程结束但是何时返回1，有两种可能性：

Stack is empty ( Level is L0 /- Ln or at uninitialized stage)
Stack has items ( traversing upward is possible )
堆栈为空（级别为L0 / - Ln或未初始化阶段）
堆栈有物品（可以向上移动）

In case 1:

A new layer M* is created with a head node NM referencing head node of layer below and NM.next referencing new element N. New element N referecing element N at previous layer. 创建一个新的层M*，其头节点NM引用层的头节点下面和NM.next引用新元素N。新元素N referecing元素前一层的N。

In case 2:

repeat until stack is empty Pop an item F from stack and update the references accordingly. F.next will be K.next and K.next will be F 重复直到堆栈为空从堆栈中弹出项目F并更新引用因此。 F.next将是K.next和K.next将是F when stack is empty Create a new layer consisintg of a head node NM referencing head node of layer below and NM.next referencing new element N. New element N referencing element N at previous layer. 当stack为空时创建一个头节点的新层consisintg NM 引用下面层的头节点和NM.next引用新元素N。新元素N在前一层引用元素N。