本文共 911 字，大约阅读时间需要 3 分钟。

跳表

背景

一个有序链表搜索、添加、删除丶平均时间复杂度是多少？

O(n)

那么我们能否利用向数组二分搜索优化有序链表，使其搜索、添加、删除的平均时间复杂度降低至O(logn)?

但很明显的是链表没有像数组那样的高效随机访问(O(1)时间复杂度)，所以不能像有序数组那样直接进行二分搜索优化

那么有没有其他办法让有序链表搜索、添加、删除的平均时间复杂度降低至O(logn)?

答案是使用跳表(SkipList)

跳表(SkipList)

跳表，又叫做跳跃表，在有序链表的基础上增加了“跳跃”的功能；

由William Pugh于1990年发布，设计的初衷是为了取代平衡树(比如红黑树)；

Redi中的SortedSet、LevelDB中的MemTable都用到了跳表；

Redis、LevelDB都是著名的key-value数据库；

对比平衡树

• 跳表的实现和维护会更加简单；
• 跳表的搜索、删除、添加的平均时间复杂度都是O(logn)

使用跳表优化链表

1.跳表的搜索

• 从顶层链表的首元素开始，从左往右开始搜索，直至找到一个大于或等于目标的元素，或者到达当前层的的尾部；
• 如果该元素等于目标元素，则表明该元素已找到；
• 如果该元素大于目标元素或者已到达链表的尾部，则退回到当前层的前一个元素，然后转入下一层进行搜索

2.跳表的添加、删除

• 添加的细节
  • 随即决定新添加元素的层数
• 删除的细节
  • 删除一个元素之后，整个调表的层数可能会降低

3.跳表的层数

• 跳表是按层构造的，底层是一个普通的有序链表，高层相当于是低层的”快速通道“

• 在第i层中的元素按某个固定的概率p出现在第i+1层中，产生越高的层数，概率越低；

  • 元素层数恰好等于1的概率为1-p；
  • 元素层数大于等于2的概率为p，而元素层数恰好等于2的概率为p*(1-p)

  

4.跳表的时间复杂度

每一层的元素个数

• 第1层链表固定有n个元素；
• 第2层链表平均有n*p个元素；
• 第3层链表平均有n*p^2个元素；
• 第k层链表平均有n*p^k个元素；

另外：

表固定有n个元素；

• 第2层链表平均有n*p个元素；
• 第3层链表平均有n*p^2个元素；
• 第k层链表平均有n*p^k个元素；

另外：

转载地址：http://ccwdf.baihongyu.com/