【数据结构与算法】什么是跳表?通俗易懂来理解跳表
发布日期:2021-06-29 15:36:06
浏览次数:2
分类:技术文章
本文共 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个元素;
另外:
转载地址:https://codingchaozhang.blog.csdn.net/article/details/115430433 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月14日 19时35分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
华为员工离职心声:菊厂15年退休,感恩,让我实现了财务自由!
2019-04-29
春晚上的“拓荒牛”
2019-04-29
嵌入式驱动自学者的亲身感受,有什么建议?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
腾讯机器狗,站起来了!
2019-04-29
我用自己创造的深度学习框架进入腾讯,爽!
2019-04-29
芯片为什么持续缺货?
2019-04-29
又涨了?2021 年 3 月程序员工资统计新出炉
2019-04-29
初入行的C++程序员,如何快速摆脱CRUD阶段?
2019-04-29
研究生跟了一个很棒的导师是种怎样的体验?
2019-04-29
学会扶墙的机器人:没有什么能让我倒下!
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
单片机的几种数字滤波算法
2019-04-29
用单片机控制导弹?
2019-04-29
各种滤波器合集!
2019-04-29
国产CPU深度研究报告(干货,110页)
2019-04-29
在电路中,耦合是什么?有哪些方式?
2019-04-29
变局之际,聊聊物联网的过去、现在和未来
2019-04-29
缺货涨价很久的MCU的国产和国外厂家汇总!(80家)
2019-04-29
单片机6年想转嵌入式Linux ,不知如何下手?
2019-04-29