| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> 跳表的原理与实现 [图解] -> 正文阅读 |
|
[数据结构与算法]跳表的原理与实现 [图解] |
下文介绍一种基于单链表的高级数据结构, 跳表 。? 将单链表先进行排序,然后针对 有序链表?为了实现高效的查找,可以使用跳表这种数据结构。 其根本思想是 二分查找 的思想。 跳表的前提条件是?针对?有序的单链表 ,实现高效地查找,插入,删除。 Redis中的 有序集合 sorted set?就是用跳表实现的。 一. 跳表的原理对于单链表,即使是 存储的有序数据(即 有序链表),想在其中查找某个数据,也只能从头到尾遍历,查找效率低,时间复杂度是O(n),如下图所示: 怎么才能提高查找效率呢?? 为了提高查找效率,使用二分查找的思想,对有序链表建立一级“索引”。 每两个节点提取一个节点到索引层。?索引层中的每个节点 都包含两个指针,一个指向下一个节点,一个down指针,指向下一级节点。 假设要查找图中 18这个节点: 首先在一级索引层遍历,当遍历到14这个节点的时候,发现其下一个节点是23,则要查找的18就在14和23之间。?然后,通过14节点的?down 指针,下降到原始链表这一层,继续在原始链表中遍历。?此时,只需要在原始链表中,遍历两个节点,14和18,就找到18这个节点了。? ? 查找18这个节点,在原始链表需要遍历10个节点,现在只需要遍历7个节点(一级索引层遍历5个节点,原始链表遍历2个节点)。? 从以上示例可以看出,加上一层索引之后,查找一个节点的遍历节点数减少了,效率提高了。如果再增加一级索引,那么效率会不会更高呢? 建立二级索引 与建立一级索引的方式类似,在第一级索引的基础上,每两个节点抽出一个节点到第二级索引,如下图: ?现在如果要查找18节点,只需要遍历6个节点(二级索引层遍历3个节点,一级索引层1个节点,原始链表2个节点)。 通过建立索引的方式,对于数据量越大的有序链表,通过建立多级索引,查找效率提升会非常明显。 这种链表加多级索引的结构?就是?跳表。 二.跳表的?时间复杂度?和 空间复杂度2.1 跳表的查询时间复杂度假设链表包含n个节点,在单链表中查询某个数据的时间复杂度是O(n)。 一个包含n个节点的有序单链表最多会有多少级索引? 每两个节点抽出一个节点作为上一级索引的节点,则 : 第一级索引的节点个数大约是?n/2 ,第二级索引的节点个数大约是 n/4,第三级索引的节点个数大约是?n/8,则第k级索引节点的个数大约是。 假设有 h?级索引,最高一级的索引有两个节点,也就是? ,从而求得?如果把原始链表这一层也算进去,那么整个跳表的高度约为? 在跳表查询时,每一级索引 最多需要遍历3个节点。? (因为假设在上图跳表中,从二级索引层,查找?节点12,则从节点1遍历到节点7,然后再遍历节点14(节点12 小于?节点14) ,从节点7向下一级索引层遍历到节点7,然再向右遍历节点11,再遍历节点14,发现节点12小于节点14,?则继续向下一级遍历,最终在下一级遍历到节点12。? 在上面遍历节点12的过程,在二级索引层遍历了3个节点(1—>7---->14),在一级索引层遍历了3个节点(7—>11---->14)。因此每一级最多遍历3个节点。 ) 那么在跳表中查询数据的时间复杂度就是? ? ?每一层遍历的节点数乘以层数??,因此跳表中查找的时间复杂度就是O(logn).? 与二分查找的时间复杂度相同。 基于单链表实现了二分查找,查询效率的提升依赖构建了多级索引,是一种空间换时间的设计思路。 2.2 空间复杂度建立索引后 的 总的索引点 的 空间复杂度: ???????? 跳表的查询数据的空间复杂度是O(n),也就是说,基于单链表构造跳表,需要额外再用一倍的存储空间。 有没有办法降低索引占用的存储空间呢? 如果每3个节点 或 每5个节点抽1个节点到上一级索引,索引节点就会相应减少。假设每3个节点抽取一个节点到上一级,总的索引节点个数为: ? ? ? ? 每3个节点抽1个节点到上一级索引的方法? 比 每2个节点抽1个节点构建索引的方式,减少了一半的索引节点存储空间。 因此,通过调节抽取节点的间隔,控制索引节点占用的存储空间,以此来达到空间复杂度 和 时间复杂度的平衡。 三.?跳表的插入和删除跳表作为一个动态数据结构,不仅支持查找操作,还支持数据的插入和删除操作,并且?插入和删除的操作的时间复杂度都是O(logn). 3.1? 插入操作为了保证原始链表中数据的有序性,我们需要先找到新数据应该插入的位置。 可以基于多级索引,快速查找到新数据的插入位置,时间复杂度为O(log n)。 假设插入数据为6的节点,如下图: 3.2? 删除操作删除原链表中的节点,如果节点存在于索引中,也要删除索引中的节点。 因为单链表中的删除需要用到 要删除节点 的 前驱动节点。 可以像插入操作一样,通过索引逐层向下遍历到原始链表中,要删除的节点,并记录其 前驱节点,从而实现删除操作。 四. 跳表索引动态更新当频繁地向跳表中插入数据时,如果插入过程不伴随着索引更新,就有可能导致某2个索引节点之间数据非常多,在极端地情况下,跳表就会退化成单链表。 作为一种动态数据结构,为了避免性能下降,我们需要在数据插入,删除的过程中,动态地更新跳表的索引结构。? 就像红黑树,二叉平衡树是通过左右旋来保持左右子树的大小平衡, 而跳表是借助随机函数来更新索引结构。 当向跳表中插入数据时,我们选择同时将这个数据插入到部分索引层中。 如何决定插入到哪些索引层中呢? 通过一个随机函数来决定,比如通过? 随机函数得到某个值 K, 那么就将这个节点添加到第一级到第K级索引中。 五.总结为什么Redis中的有序集合用跳表而非红黑树来实现呢? 1.对于插入,删除,查找 以及 输出有序序列 这几个操作,红黑树也可以完成,时间复杂度 与 用跳表实现是相同的。 但是,对于按照区间查找数据这个操作(比如 [20,300]),红黑树的效率没有跳表高,跳表可以做到 O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序向后遍历输出,直到遇到值大于区间终点的节点为止。 2.跳表更加灵活,它可以通过改变节点的抽取间隔,灵活地平衡空间复杂度和时间复杂度 3.相比红黑树,跳表更容易实现,代码更简单。 六. 代码实现1.C++版本(参考 Leetcode1206题 题解)
2.Java版本(参考 Leetcode1206题 题解)
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 | -2024/11/26 0:29:04- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |