数据结构与算法之如何掌握跳表

这篇文章主要讲解了“数据结构与算法之如何掌握跳表”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“数据结构与算法之如何掌握跳表”吧！

数据结构与算法笔记-数据结构-跳表

跳表(skip list)

跳表代码-gitee

跳表代码-github

关键词

1. 跳表是基于链表的一种动态数据结构,可以简单认为就是对链表的节点添加了多级索引.

2. 跳表支持快速地插入,删除,查找操作,时间复杂度都是O(logn),空间复杂度为O(n)

3. 跳表是通过添加索引使用空间换时间的设计思路,构建多级索引来提升查询效率

4. 跳表的时间复杂度为O(logn)

5. 跳表数通过随机函数来维护平衡

6. 跳表插入数据时要维护索引和节点的平衡,否则极端情况下可能会导致跳表退化成为链表

7. 跳表更加灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗.

8. 跳表有可与红黑树匹敌的性能,跳表写起来却好写很多.很多时候可以直接替代红黑树

9. 按照区间来查找数据这个操作,红黑树的效率没有跳表高.对于按照区间查找数据这个操作,跳表可以做到,O(logn) 的时间复杂度定位区间的起点,而后在原始链表中顺序往后遍历即可

理解跳表

二分查找法底层依赖的时数组随机访问的特性,所以只能用数组来实现.

链表也有类似二分的查找操作, 叫做跳表(skip list)

链表是一种各方面性能都很优秀的动态数据结构,支持: 快速插入,删除,查找.写起来也简单, 甚至可以代替红黑树.

其中Redis的有序列表(sorted set)就是利用跳表来实现的,因为:

严格来说Redis还用到了Hash table
主要Redis手册,有序集合的核心操作就是
	插入一个数据；
	删除一个数据；
	查找一个数据；
	按照区间查找数据（比如查找值在[100, 356]之间的数据）；
	迭代输出有序序列。
	
其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了
还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

单项链表的数据就算是有序的,要获取指定的数据也要从头逐个遍历,时间复杂度为O(n)

如图:

一级索引

想要提高查询效率,可以通过对链表建一级索引来实现.在每两个节点中提取一个节点到作为索引或索引层

如图: 下面的down代表下一个节点的指针

设若获取节点16:

1. 先遍历索引层,当遍历到索引层中值为13的节点时,发现下一个节点是17,那节点16必然就在这两个节点之间.

2. 通过索引层及诶单的down指针,到原始接链表中继续向后遍历

3. 此时,只需再向后遍历两个及诶单即可找到值等于16的节点

4. 原来需要查找16次,现在只要7次遍历

可见, 加一层索引之后,查找一个节点需要遍历的次数就减少了很多,查找效率提升很高.

二级索引

和建立第一级索引的方式类似, 在第一级索引的基础上,每两个节点抽出一个节点到第二级作为二级索引.

此时再来查找16,只需要遍历6个节点.

如图:

当数据量够大,够大的时候, 查询效率会有更大的提升,下图一个64个节点的链表.建立了五级索引

要找到值为62的节点, 在没有索引时需要遍历62个节点.

现在只需要遍历11个节点即可

如图:

上面这种链表加多级索引的结构就是跳表 ,可以看到跳表大大减少了查询次数.对链表的优化是显而易见的.

跳表查询有多快

单项链表中查询指定数据的时间复杂度是O(n)

具有多级索引的跳表中, 假设有n个节点需要多少级索引:

设,若每两个节点抽出一个节点作为上一级索引

1. 第一级索引约为n/2个

2. 第二级索引约为n/4个

3. 第三极索引约为n/8个

4. 第四级索引约为n/16个

5. ......以此类推

6. 第k级索引的节点个数是k-1级索引的节点个数的1/2

7. 第k级索引节点的个数就是n/(2^k)

设,索引有h级,最高级的索引有2个节点,

1. 套用上面的公式得到n/(2^h)=2,求得h=log2n-1

2. 如果包含原始链表这一层,整个跳表的高度就是log2n

3. 在跳表查询某个数据时,若每一次都要遍历m个节点,那在跳表中查询一个数据的时间复杂度就是O(m*logn)

多级索引

如果每三个或五个抽出一个作为索引,如图有14个节点:

1. 第一级索引需要n/3个节点

2. 第二级索引需要n/9个节点

3. ......每向上一级,索引的个数都除以3

4. 假设做高级的索引个数为1, 把每级节点个数列出来,就是一个等比数列

通过等比数列求和公式, 总的索引结点大约就是 n/3+n/9+n/27+…+9+3+1=n/2

尽管空间复杂度还是 O(n),但比上面的每两个结点抽一个结点的索引构建方法,要减少了一半索引结点存储空间.

一般在真正的开发中,不考虑索引占的空间,索引结点只需要存储关键值和几个指针,并不需要存储对象.

高效的动态插入和删除

插入和删除实际上是需要两步的:

1. 找到合适的节点

2. 插入或删除

查找

跳表还支持动态插入,删除,切插入和删除的时间复杂度都是O(logn)

相比之下,单项链表的插入是O(1),但是这是在定好插入位置之后的时间复杂度.

但是为了保证链表数据的顺序性, 在插入之前还需要找到插入位置,查找一通这就费了劲了.

单向链表, 需要遍历每一个节点来找到插入的位置

插入操作

上面说过了, 跳表通过查找指定节点的时间复杂度是O(logn),找到插入位置也一样, 插入过程如下图:

删除操作

1. 如果这个节点同时在索引中,想要删除原始链表中的节点,同时还要删除索引中的节点.

2. 单项连表的删除操作需要拿到要该节点的前一个节点,然后通过指针来删除后一个节点,以完成删除该节点的操作.

3. 所以在查找要删除的节点时,一定要获取到该节点的前一个节点.(双向链表不考虑这个问题)

跳表索引动态更新

在不断的插入数据而不去更新索引时,可能会出现两个索引之间节点数特别多的情况.

在极端情况下,会导致跳表退化成为链表.

如下图:

跳表作为一个动态数据结构,需要我们不断地维护索引与原始链表之间的平衡.

如果链表节点多了,索引节点就要增加,以避免复杂度退化,导致查找和删除性能下降.

红黑树和avl数是通过左右旋的方式保持左右子树的大小平衡,而跳表数通过随机函数来维护平衡.

通过随机函数,决定该节点插入到哪几级索引中,

如随机函数生成了值k,那就将这个节点添加到第一级到第K级的, 这几级的索引中

如下图:

随机函数要比较高,从概率上来讲要保证跳表的索引大小和数据大小平衡性,不至于性能过度退化.

感谢各位的阅读，以上就是“数据结构与算法之如何掌握跳表”的内容了，经过本文的学习后，相信大家对数据结构与算法之如何掌握跳表这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！