[What]数据结构与算法 -> 跳表

课程:王争 –> <数据结构与算法之美>

跳表(Skip list)是各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除、查找操作。

概念

跳表是通过在 有序链表 之上建立多级索引的方式来达到快速查找的目的。

skip_list_overview.jpg

如上图所示,有序单链表建立了3级索引,其中每隔一个节点就建立一个上层索引。

当需要查找包含数据18的节点时,如果没有索引则只能顺序查找12次到目标节点。在索引的帮助下,仅需要查找7次即可。

  • 建立索引查找的好处在节点数量很多的时候效果尤为明显。

分析

时间复杂度

当链表的节点数为n时,如果按照每隔一个点建立一个索引的话,那么它上一级的索引个数就是 (n/2)。

依此推类到第k级的索引个数就是 n/(2^k),顶层的索引为2,也就是 n/(2^k) = 2。

最终得出索引的级数: k = log2n - 1,在此基础上每级索引的遍历个数为m,那么时间复杂度为O(m*logn)。

从顶层往下层看,每两个节点之间的下层节点个数为3,也就是说每层的遍历个数为3,所以时间复杂度为 O(3*logn),也就是 O(logn)

空间复杂度

根据上面时间复杂度的分析,可以看出其所需要的额外节点个数为: n + n/2 + n/4 …. 2 = n - 2

也就是说空间复杂度为 O(n)

在实际的工程应用中,常常会多个节点才建立一个索引,或者是只为几个关键的节点建立索引,这样的空间消耗就不大了。

插入和删除

在链表进行插入和删除时,很多时候需要先查找到对应的位置再进行操作。

在基于索引的方式时,插入和删除操作的时间复杂度就是O(logn).

  • 需要注意的是,在插入时需要根据应用场景判断是否需要新建索引节点,在删除时是否需要删除索引节点。
    • 建立索引是通过随机函数辅助实现的,随机函数生成K值,然后为此节点在1到k级索引中建立索引节点。
Last Updated 2019-02-12 Tue 07:41.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)