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

[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)

如图:

一级索引

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

如图: 下面的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级的, 这几级的索引中

如下图:

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

总结

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

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

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

插入

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

删除

查找

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