初识跳表

为什么需要跳表？

首先，跳表是链表的一种优化模型。

对于有序的数组来说，我们查询的时间复杂度可以通过二分查找降低至O(log N)。而二分查找依赖的是数组可以通过索引随机访问一个元素，通过下标即可很容易定位到中间元素。而普通的单链表，无法通过下标访问元素，所以查找的时间复杂度为O(N)，即需要遍历整条链表。

但是，数组也存在一定的局限性：

1. 需要连续的内存空间
2. 插入、删除操作复杂度高（需要移动新元素以后的所有元素）

而对比链表：不需要连续的内存空间，插入删除操作的时间复杂度为O(1)。

O(1)仅指插入和删除的动作，不包括查找到需要操作的节点。

所以链表在插入、删除操作比较频繁的情景下，优先级应该要高于数组。唯一的不足就是查找需要遍历整条链表。

而跳表就是为了解决这个问题：提高链表查询效率。

跳表是什么？

基于上述，链表由于无法用索引访问元素，所以导致了查询的时间复杂度较高。于是跳表的核心就是为结点添加索引。

普通的单链表：

单链表.png

如果我们为该链表建立一层索引：

两层索引.png

此时如果我们通过索引进行查找，明显可以降低查找的次数。如果我们再添加一层索引，还可以更进一步降低查找次数：

三层索引.png

以上就是跳表的核心。上面的图片非常利于理解跳表，但是具体代码不是这样实现的。

跳表实现

在实现具体代码之前，我们先考虑要如何实现索引。

索引问题

这里有两个问题：

1. 每一层要多少个结点索引？
2. 索引的数据结构要怎么实现？

索引结点数量

关于每一层需要多少个索引，从上图我们可以看到每一层的结点个数都是下一层的一半。可以类比完全二叉树，每一个结点都可以对应到下一层的两个结点，这样查询的时间复杂度可以完美的达到O(log N)。

但是如果我们要严格要求每一层的个数都是下一层的一半，那么在插入、删除结点时，我们又需要花费大量的精力去维护这个要求，最终得不偿失。所以常规的跳表实现，只要求概率上满足这个条件。即这个结点在某一层需要建立索引的概率为1/2.一般直接通过random函数来取值判断。

所以跳表实现的论文写道：“Skip Lists : A Probabilistic Alternative to Balanced”

索引的数据结构

如果基于上图的理解，我们在单链表的基础上，再创建几条链表作为索引链表。但是这样明显的问题是，当数据量非常大的时候，我们也需要耗费大量的空间来维护索引结构。所以常规的实现并不是这样的。

常规的实现是每个结点中添加一个索引数组。如下图，每个结点右边的格子代表数组，由于是随机决定的，所以数组不定长。数组中的下标代表索引的层级：

跳表.png

综上，结点的定义为：

class ListNode:
    def __init__(self, key=None, value=None):
        self._key = key
        self._value = value
        self._forwards = []

代码实现

刚开始看跳表的代码很难理解，但是如果能理清楚上述两个模型图的关系，边敲代码边理解，实现起来比较清晰的。只需要弄懂插入函数，其余的删除、查找函数都同理。

操作逻辑根据多链表图来理解，代码实现根据实际数组图来理解。

代码基础架构

class SkipList:

    _MAX_LEVEL = 4 

    def __init__(self):
        self._level_count = 1
        self._head = ListNode()
        self._head._forwards = [None] * self._MAX_LEVEL

    def insert(self, value):
        """
        插入一个元素

        :param value:
        :return: 已存在返回False 正常插入True
        """
        pass

    def delete(self, value):
        """
        删除一个元素  (插入的逆操作)

        :param value:
        :return: 如果不存在这个节点False 成功删除True
        """
        pass
    
    def find(self, value):
        """
        查找单个元素

        :param value:
        :return: 返回一个ListNode对象
        """
        pass

    def find_range(self, begin_value, end_value) :
        """
        查找一个范围内的元素

        :param begin_value:
        :param end_value:
        :return: 返回一组有序ListNode对象
        """
        pass
    
    def _random_level(self, p = 0.5):
        """
        返回随机层数

        :param p:
        :return:
        """
        pass

结点

为了简化实现，我们的结点不包含data数据，只使用索引。

# 这是包含data数据的定义模式
# class ListNode:
#     def __init__(self, key=None, value=None):
#         self._key = key
#         self._value = value
#         self._forwards = []

# data即索引，或者说是key
class ListNode:
    def __init__(self, data = None):
        self._data = data
        self._forwards = []

随机层数

准确点来说，这里返回的应该是某个结点索引的最高层级，以下的层级都建立索引。

实际跳表实现中，如果我们返回3，那么我们会在第3层、第2层、第1层都建立索引。

    def _random_level(self, p=0.5):
        """
        返回随机层数

        :param p:
        :return:
        """
        level = 1
        while random.random()<p and level<self._MAX_LEVEL:
            level +=1
        return level

注意这里指的层数即实际个数，由于数组索引从0开始，所以后续数组相关操作都需要-1

插入

当需要插入一个元素时，流程为：

1. 计算出需要建立索引的层级
2. 找到每一层索引需要插入的位置
3. 调整每一层的索引

举个例子：

三层索引.png

如果我们想要插入结点 12，那么以单链表的思路找到每一层需要插入的地方（图中红圈）。【第一个圈错了...】

插入位置.png

for是用于遍历每一层，for内的代码可以以单链表查找的方式理解。对于每一层索引，我们的目标就是找到红圈前的结点。

# update数组保存的即是每一层 红圈前的结点
update = [self._head] * level

# 找到每一层需要插入索引的位置
p = self._head
for i in range(level-1, -1, -1):
    
    # 在同一层，找到小于等于当前节点的最后一个节点
    while p._forwards[i] and p._forwards[i]._data< value:
        # 同理node = node.next
        p = p._forwards[i]
    if p._forwards[i] and p._forwards[i]._data==value:
        # 说明已存在，不需要再插入
        return False
    # 保存这个节点
    update[i] = p

由上，我们找到了每一层红圈前的结点，接下来的操作就是插入。同样以单链表的方式理解：

对于 单链表 a → c  
我们已找到a  要插入 b

则 ：   b.next = a.next
        a.next = b
        
得 ：   a → b → c

于是代码实现如下，同理for是遍历每一层：

# 调整每层索引
for i in range(level):
    # b.next = a.next
    new_node._forwards[i] = update[i]._forwards[i]
    # a.next = b
    update[i]._forwards[i] = new_node

至此我们完成了我们的插入函数。

删除

有了插入的基础，删除即是插入的逆：遍历所有的层级，找到可能出现要删除结点的位置（同理上红圈前的结点）

# 记录下每层索引可能受影响的节点
update = [None] * self._level_count
p = self._head
for i in range(self._level_count-1, -1, -1):
    while p._forwards[i] and p._forwards[i]._data < value:
        p = p._forwards[i]
    update[i] = p

然后只需要删除对应的结点即可，删除操作同单链表：

对于 单链表  a → b → c
我们已找到a  要删除 b

则 ：   a.next = a.next.next
        
得 ：   a → c  

对应到代码中：

for i in range(self._level_count-1, -1, -1):
    if update[i]._forwards[i] and update[i]._forwards[i]._data == value:
        # a.next = a.next.next
        update[i]._forwards[i] = update[i]._forwards[i]._forwards[i]

查找

逻辑同上

p = self._head
for i in range(self._level_count - 1, -1, -1):
    while p._forwards[i] and p._forwards[i]._data < value:
        p = p._forwards[i]
    if p._forwards[i] and p._forwards[i]._data == value:
        return p._forwards[i]

总结

1. 跳表是一个多层的链表
2. 第0层的链表包含所有节点，其他层的链表包含部分节点，层次越高，节点越少
3. 每层链表之间会共享相同的节点
4. 对于某个节点，在插入时通过概率判断它最高会出现在哪一层，并且也会出现在之下的每一层
5. 查找时从最高层开始向下查找，当遇到链表末尾或大于key的节点时，往下走一层，直到找到key节点

直接看代码比较难理清除，建议看着注释跟着敲代码，结合着两种核心图理解！

完整代码见：https://github.com/Sssmeb/python_datastructure/tree/master

如果对你有帮助可以点个star~（项目里还包含了其他重难点数据结构）

文中图片取自百度