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

原创
2020/12/22 03:59
阅读数 2K

[TOC]

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

跳表(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)

如图:

img

一级索引

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

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

img

设若获取节点16:

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

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

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

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

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

二级索引

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

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

如图:

img

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

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

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

如图:

img

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

跳表查询有多快

单项链表中查询指定数据的时间复杂度是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个节点:

img

  1. 第一级索引需要n/3个节点
  2. 第二级索引需要n/9个节点
  3. ......每向上一级,索引的个数都除以3
  4. 假设做高级的索引个数为1, 把每级节点个数列出来,就是一个等比数列

img

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

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

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

高效的动态插入和删除

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

  1. 找到合适的节点
  2. 插入或删除

查找

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

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

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

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

插入操作

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

img

删除操作

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

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

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

跳表索引动态更新

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

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

如下图:

img

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

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

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

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

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

如下图:

img

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

总结

跳表的实现方式是很简单的,但是要特别注意的是随机函数的选择,

如果随机函数选择不当,会导致索引分配极不均衡.

极端情况下,跳表的一部分节点之间会退化为链表, 那就尴尬了.

插入

  1. 首先随机,得到要索引要补充的高度
  2. 从大到小循环,高度为上次得到的索引高度
  3. 循环数据,在上一步的循环中嵌套循环, 直到找到数据要插入的位置或者查到了链表的最后
  4. 找到位置后,将该位置后面的节点取出,将当前要插入的节点的下一个指针标记为该节点.
  5. 将该位置的前一个节点的下一个节点的指针修改为当前节点
  6. 插入完成

删除

查找

删除和查找流程类似, 不再赘述.

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部