【数据结构与算法】什么是跳表？通俗易懂来理解跳表

2024-07-12 22:13| 来源: 网络整理| 查看: 265

跳表背景

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

O(n)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I3JYSJVr-1617526278668)(imgs/1.png)]

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

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

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

答案是使用跳表(SkipList)

跳表(SkipList)

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

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

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

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

对比平衡树

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

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z6MfUwcp-1617526278672)(imgs\2.png)]$

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

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xi5sUybQ-1617526278673)(imgs\3.png)]$

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

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

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

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

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ITEiJbOc-1617526278677)(imgs\4.png)]$

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个元素；

另外：

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lto4PNNx-1617526278678)(imgs\5.png)]$

【本文地址】

今日新闻