[TOC]
数据结构与算法笔记-数据结构-跳表
跳表(skip list)
关键词
- 跳表是基于链表的一种动态数据结构,可以简单认为就是对链表的节点添加了多级索引.
- 跳表支持快速地插入,删除,查找操作,时间复杂度都是O(logn),空间复杂度为O(n)
- 跳表是通过添加索引使用空间换时间的设计思路,构建多级索引来提升查询效率
- 跳表的时间复杂度为O(logn)
- 跳表数通过随机函数来维护平衡
- 跳表插入数据时要维护索引和节点的平衡,否则极端情况下可能会导致跳表退化成为链表
- 跳表更加灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗.
- 跳表有可与红黑树匹敌的性能,跳表写起来却好写很多.很多时候可以直接替代红黑树
- 按照区间来查找数据这个操作,红黑树的效率没有跳表高.对于按照区间查找数据这个操作,跳表可以做到,O(logn) 的时间复杂度定位区间的起点,而后在原始链表中顺序往后遍历即可
理解跳表
二分查找法底层依赖的时数组随机访问的特性,所以只能用数组来实现.
链表也有类似二分的查找操作, 叫做跳表(skip list)
链表是一种各方面性能都很优秀的动态数据结构,支持: 快速插入,删除,查找.写起来也简单, 甚至可以代替红黑树.
其中Redis的有序列表(sorted set)就是利用跳表来实现的,因为:
严格来说Redis还用到了Hash table
主要Redis手册,有序集合的核心操作就是
插入一个数据;
删除一个数据;
查找一个数据;
按照区间查找数据(比如查找值在[100, 356]之间的数据);
迭代输出有序序列。
其中,插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。
对于按照区间查找数据这个操作,跳表可以做到 O(logn) 的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了
还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执行效率和内存消耗。
单项链表的数据就算是有序的,要获取指定的数据也要从头逐个遍历,时间复杂度为O(n)
如图:
一级索引
想要提高查询效率,可以通过对链表建一级索引来实现.在每两个节点中提取一个节点到作为索引或索引层
如图: 下面的down代表下一个节点的指针
设若获取节点16:
-
先遍历索引层,当遍历到索引层中值为13的节点时,发现下一个节点是17,那节点16必然就在这两个节点之间.
-
通过索引层及诶单的down指针,到原始接链表中继续向后遍历
-
此时,只需再向后遍历两个及诶单即可找到值等于16的节点
-
原来需要查找16次,现在只要7次遍历
可见, 加一层索引之后,查找一个节点需要遍历的次数就减少了很多,查找效率提升很高.
二级索引
和建立第一级索引的方式类似, 在第一级索引的基础上,每两个节点抽出一个节点到第二级作为二级索引.
此时再来查找16,只需要遍历6个节点.
如图:
当数据量够大,够大的时候, 查询效率会有更大的提升,下图一个64个节点的链表.建立了五级索引
要找到值为62的节点, 在没有索引时需要遍历62个节点.
现在只需要遍历11个节点即可
如图:
上面这种链表加多级索引的结构就是跳表 ,可以看到跳表大大减少了查询次数.对链表的优化是显而易见的.
跳表查询有多快
单项链表中查询指定数据的时间复杂度是O(n)
具有多级索引的跳表中, 假设有n个节点需要多少级索引:
设,若每两个节点抽出一个节点作为上一级索引
- 第一级索引约为n/2个
- 第二级索引约为n/4个
- 第三极索引约为n/8个
- 第四级索引约为n/16个
- ......以此类推
- 第k级索引的节点个数是
k-1
级索引的节点个数的1/2
- 第k级索引节点的个数就是
n/(2^k)
设,索引有h级,最高级的索引有2个节点,
- 套用上面的公式得到
n/(2^h)=2
,求得h=log2n-1
- 如果包含原始链表这一层,整个跳表的高度就是
log2n
- 在跳表查询某个数据时,若每一次都要遍历m个节点,那在跳表中查询一个数据的时间复杂度就是
O(m*logn)
多级索引
如果每三个或五个抽出一个作为索引,如图有14个节点:
- 第一级索引需要n/3个节点
- 第二级索引需要n/9个节点
- ......每向上一级,索引的个数都除以3
- 假设做高级的索引个数为1, 把每级节点个数列出来,就是一个等比数列
通过等比数列求和公式, 总的索引结点大约就是 n/3+n/9+n/27+…+9+3+1=n/2
尽管空间复杂度还是 O(n)
,但比上面的每两个结点抽一个结点的索引构建方法,要减少了一半索引结点存储空间.
一般在真正的开发中,不考虑索引占的空间,索引结点只需要存储关键值和几个指针,并不需要存储对象.
高效的动态插入和删除
插入和删除实际上是需要两步的:
- 找到合适的节点
- 插入或删除
查找
跳表还支持动态插入,删除,切插入和删除的时间复杂度都是O(logn)
相比之下,单项链表的插入是O(1),但是这是在定好插入位置之后的时间复杂度.
但是为了保证链表数据的顺序性, 在插入之前还需要找到插入位置,查找一通这就费了劲了.
单向链表, 需要遍历每一个节点来找到插入的位置
插入操作
上面说过了, 跳表通过查找指定节点的时间复杂度是O(logn),找到插入位置也一样, 插入过程如下图:
删除操作
-
如果这个节点同时在索引中,想要删除原始链表中的节点,同时还要删除索引中的节点.
-
单项连表的删除操作需要拿到要该节点的前一个节点,然后通过指针来删除后一个节点,以完成删除该节点的操作.
-
所以在查找要删除的节点时,一定要获取到该节点的前一个节点.(双向链表不考虑这个问题)
跳表索引动态更新
在不断的插入数据而不去更新索引时,可能会出现两个索引之间节点数特别多的情况.
在极端情况下,会导致跳表退化成为链表.
如下图:
跳表作为一个动态数据结构,需要我们不断地维护索引与原始链表之间的平衡.
如果链表节点多了,索引节点就要增加,以避免复杂度退化,导致查找和删除性能下降.
红黑树和avl数是通过左右旋的方式保持左右子树的大小平衡,而跳表数通过随机函数来维护平衡.
通过随机函数,决定该节点插入到哪几级索引中,
如随机函数生成了值k,那就将这个节点添加到第一级到第K级的, 这几级的索引中
如下图:
随机函数要比较高,从概率上来讲要保证跳表的索引大小和数据大小平衡性,不至于性能过度退化.
总结
跳表的实现方式是很简单的,但是要特别注意的是随机函数的选择,
如果随机函数选择不当,会导致索引分配极不均衡.
极端情况下,跳表的一部分节点之间会退化为链表, 那就尴尬了.
插入
- 首先随机,得到要索引要补充的高度
- 从大到小循环,高度为上次得到的索引高度
- 循环数据,在上一步的循环中嵌套循环, 直到找到数据要插入的位置或者查到了链表的最后
- 找到位置后,将该位置后面的节点取出,将当前要插入的节点的下一个指针标记为该节点.
- 将该位置的前一个节点的下一个节点的指针修改为当前节点
- 插入完成
删除
查找
删除和查找流程类似, 不再赘述.