数据结构与算法整理总结---跳表

如何理解“跳表”?

对于⼀个单链表来讲,即便链表中存储的数据是有序的,如果我们要想在其中查找某个数据,也只能从头到尾遍历链表。这样查找效率就会很低,时间复杂度会很⾼,是O(n)。

数据结构与算法整理总结---跳表

那怎么来提⾼查找效率呢?如果像图中那样,对链表建⽴⼀级“索引”,查找起来是不是就会更快⼀些呢?每两个结点提取⼀个结点到上⼀级,我们把抽出来的那⼀级叫作索引或索引层。

数据结构与算法整理总结---跳表

如果我们现在要查找某个结点,⽐如16。我们可以先在索引层遍历,当遍历到索引层中值为13的结点时,我们发现下⼀个结点是17,那要查找的结点16肯定就在这两个结点之间。然后我们通过索引层结点的down指针,下降到原始链表这⼀层,继续遍历。这个时候,我们只需要再遍历2个结点,就可以找到值等于16的这个结点了。这样,原来如果要查找16,需要遍历10个结点,现在只需要遍历7个结点。

跟前⾯建⽴第⼀级索引的⽅式相似,我们在第⼀级索引的基础之上,每两个结点就抽出⼀个结点到第⼆级索引。现在我们再来查找16,只需要遍历6个结点了,需要遍历的结点数量⼜减少了。

数据结构与算法整理总结---跳表

我举的例⼦数据量不⼤,所以即便加了两级索引,查找效率的提升也并不明显。为了让你能真切地感受索引提升查询效率。我画了⼀个包含64个结点的链表,按照前⾯讲的这种思路,建⽴了五级索引。

数据结构与算法整理总结---跳表

这种链表加多级索引的结构,就是跳表

跳表的查询效率

算法的执⾏效率可以通过时间复杂度来度量,这⾥依旧可以⽤。我们知道,在⼀个单链表中查询某个数据的时间复杂度是O(n)。那在⼀个具有多级索引的跳表中,查询某个数据的时间复杂度是多少呢?

按照我们刚才讲的,每两个结点会抽出⼀个结点作为上⼀级索引的结点,那第⼀级索引的结点个数⼤约就是n/2,第⼆级索引的结点个数⼤约就是n/4,第三级索引的结点个数⼤约就是n/8,依次类推,也就是说,第k级索引的结点个数是第k-1级索引的结点个数的1/2,那第k级索引结点的个数就是n/(2k)。

假设索引有h级,最⾼级的索引有2个结点。通过上⾯的公式,我们可以得到n/(2h)=2,从⽽求得h=log2n-1。如果包含原始链表这⼀层,整个跳表的⾼度就是log2n。我们在跳表中查询某个数据的时候,如果每⼀层都要遍历m个结点,那在跳表中查询⼀个数据的时间复杂度就是O(m*logn)。

假设我们要查找的数据是x,在第k级索引中,我们遍历到y结点之后,发现x⼤于y,⼩于后⾯的结点z,所以我们通过y的down指针,从第k级索引下降到第k-1级索引。在第k-1级索引中,y和z之间只有3个结点(包含y和z),所以,我们在K-1级索引中最多只需要遍历3个结点,依次类推,每⼀级索引都最多只需要遍历3个结点。

数据结构与算法整理总结---跳表

通过上⾯的分析,我们得到m=3,所以在跳表中查询任意数据的时间复杂度就是O(logn)。这个查找的时间复杂度跟⼆分查找是⼀样的。换句话说,我们其实是基于单链表实现了⼆分查找。

跳表的空间复杂度

假设原始链表⼤⼩为n,那第⼀级索引⼤约有n/2个结点,第⼆级索引⼤约有n/4个结点,以此类推,每上升⼀级就减少⼀半,直到剩下2个结点。如果我们把每层索引的结点数写出来,就是⼀个等⽐数列。

数据结构与算法整理总结---跳表

这⼏级索引的结点总和就是n/2+n/4+n/8…+8+4+2=n-2。所以,跳表的空间复杂度是O(n)。

⾼效的动态插⼊和删除

跳表这个动态数据结构,不仅⽀持查找操作,还⽀持动态的插⼊、删除操作,⽽且插⼊、删除操作的时间复杂度也是O(logn)。

在单链表中,⼀旦定位好要插⼊的位置,插⼊结点的时间复杂度是很低的,就是O(1)。但是,这⾥为了保证原始链表中数据的有序性,我们需要先找到要插⼊的位置,这个查找操作就会⽐较耗时。
对于纯粹的单链表,需要遍历每个结点,来找到插⼊的位置。但是,对于跳表来说,我们讲过查找某个结点的的时间复杂度是O(logn),所以这⾥查找某个数据应该插⼊的位置,⽅法也是类似的,时间复杂度也是O(logn)。
数据结构与算法整理总结---跳表

Redis中的有序集合是通过跳表来实现的,严格点讲,其实还⽤到了散列表。

Redis中的有序集合⽀持的核⼼操作主要有下⾯这⼏个:

插⼊⼀个数据;删除⼀个数据;查找⼀个数据;按照区间查找数据(⽐如查找值在[100, 356]之间的数据);迭代输出有序序列。

其中,插⼊、删除、查找以及迭代输出有序序列这⼏个操作,红⿊树也可以完成,时间复杂度跟跳表是⼀样的。但是,按照区间来查找数据这个操作,红⿊树的效率没有跳表⾼。 对于按照区间查找数据这个操作,跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。

当然,Redis之所以⽤跳表来实现有序集合,还有其他原因,⽐如,跳表更容易代码实现。虽然跳表的实现也不简单,但⽐起红⿊树来说还是好懂、好写多了,⽽简单就意味着可读性好,不容易出错。还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执⾏效率和内存消耗。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!