印度阿三17 / 开发 / 数据结构与算法之美学习笔记:第十七讲

0 0

   

数据结构与算法之美学习笔记:第十七讲

2019-11-19  印度阿三17

一、课前思考

两节我们讲了二分查找算法。当时我讲到,因为二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了吗?

实际上,我们只需要对链表稍加改造,就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表(Skiplist),也就是今天要讲的内容。

跳表这种数据结构对你来说,可能会比较陌生,因为一般的数据结构和算法书籍里都不怎么会讲。但是它确实是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除、查找操作,
写起来也不复杂,甚至可以替代红黑树(Red-blacktree)。

Redis中的有序集合(Sorted Set)就是⽤跳表来实现的。如果你有一定基础,应该知道红黑树也可以实现快速的插入、删除和查找操作。那Redis为什么会选择用跳表来实现有序集合呢?
 为什么不用红黑树呢?学完今天的内容,你就知道答案了。

二、如何理解跳表

1、单链表

2、怎么提高查询效率

1、18个节点一级索引

2、18个节点二级索引

3、64个节点建立五级索引

3、当链表的⻓度n⽐较⼤时

三、用跳表查询到底有多快

1、如果链表⾥有n个结点,会有多少级索引?

2、复杂度推算过程

3、M值为什么是3

4、基于单链表实现二分查找

四、跳表是不是很浪费内存

1、索引节点数是一个等比数列

2、通过等⽐数列求和公式

3、实际上,在软件开发中,我们不必太在意索引占⽤的额外空间

五、高效的动态插入删除

1、在跳表单链表中插⼊⼀个数据的时间复杂度

2、在跳表中删除⼀个数据的时间复杂度

六、跳表索引动态更新

1、如果链表中结点多了,索引结点就相应地增加⼀些

2、跳表是通过随机函数来维护前⾯提到的“平衡性”

3、如何选择加⼊哪些索引层呢?

七、解答开篇

1、如果你去查看Redis的开发⼿册,就会发现Redis中的有序集合⽀持的核⼼操作主要有下⾯这⼏个

1、插⼊⼀个数据;删除⼀个数据;查找⼀个数据;

2、按照区间查找数据(⽐如查找值在[100, 356]之间的数据

3、迭代输出有序序列。

2、Redis之所以⽤跳表来实现有序集合,还有其他原因

3、跳表也不能完全替代红⿊树

跳表的实现还是稍微有点复杂的,我将Java实现的代码放到了GitHub中,你可以根据我刚刚的讲解,对照着代码仔细思考⼀下。你不⽤死记硬背代码,跳表的实现并不是我们这节的重点

八、内容小结

今天我们讲了跳表这种数据结构。跳表使用空间换时间的设计思路,通过构建多级索引来提高查询的效率,实现了基于链表的“二分查找”。跳表是一种动态数据结构,支持快速的插入、删除、查找操作,时间复杂度都是O(logn)。

跳表的空间复杂度是O(n)。不过,跳表的实现非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单,但是作为一种动态数据结构,比起红黑树来说,
实现要简单多了。所以很多时候,我们为了代码的简单、易读,比起红黑树,我们更倾向用跳表。

九、课后思考

在今天的内容中,对于跳表的时间复杂度分析,我分析了每两个结点提取一个结点作为索引的时间复杂度。如果每三个或者五个结点提取一个结点作为上级索引,
对应的在跳表中查询数据的时间复杂度是多少呢

经典留言escray

如果每三个或者五个节点提取一个节点作为上级索引,那么对应的查询数据时间复杂度,应该也还是 O(logn)。

假设每 5 个节点提取,那么最高一层有 5 个节点,而跳表高度为 log5n,每层最多需要查找 5 个节点,即 O(mlogn) 中的 m = 5,最终,时间复杂度为 O(logn)。
空间复杂度也还是 O(logn),虽然省去了一部分索引节点,但是似乎意义不大。

不知道在一般的生产系统,跳表的提取是按照多少个节点来实现?还是每个系统根据实际情况,都不一样。
看了跳表的 Java 实现,查找部分的代码真是漂亮,插入部分看了半天才看明白。

 

来源:https://www.icode9.com/content-1-566201.html

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多