1 跳表的数据结构

跳表是在链表上做的改善,解决了链表查找时间复杂度为 O(n) 的问题,改善之后的跳表可以像二分查找一样,实现时间复杂度为 O(logn) 的效果。

单链表

对于单链表,查找的时间复杂度为 O(n),怎么才能改善这个问题,我们可以通过每两个节点提取一个索引的形式对链表做改善,下图是改善后的形式

增加第一级索引

使用改善后的链表,我们可以现在第一级索引里面找,比如说找 16,当我们找到 13,发现下一个是 17,比 16 大,那么我们就从 13 号索引下降到原始链表,然后向后查找就能迅速找到 16。

在此基础上,我们能再提一级索引,形成下面这种样子

增加二级索引

对于一个有 64 个节点的链表,我们能够构造出下图的索引结构,用黄色线标出了查询数据的路径,非常高效,链表长度越大,提升越明显

64 节点的跳表

这种结构的数据结构便是在链表的基础上实现了二分查找,时间复杂度为 O(logn)

2 跳表会不会很浪费内存

跳表相比于普通链表需要创建很多索引,我们先来算一算跳表索引的空间复杂度

跳表索引的空间复杂度

\[ n/2 + n/4 + ··· + 4 + 2 = n - 2 \]

也就是说跳表的空间复杂度是 O(n)

同时通过多个点提取一个索引的方式可以降低索引所需空间,但其实开发时无需过多关心这一点,因为存储的索引相较于存储的数据其实很小。

以下是每三个点提取一个索引

每三个点提取一个索引
每三个点提取一个索引

\[ n/3 + n/9 + ··· + 3 + 1 = n / 2 \]

所需空间减小了一半,不过空间复杂度还是 O(n)

3 插入和删除操作

插入数据只需要在查找到数据之后将数据插入到该数据的后面即可

删除数据同理,在查找到数据之后将该数据删除即可,不过如果该数据存在索引也需要将索引删除。

这里面有一个问题,在多次插入和删除之后,可能出现某一段数据中间没有索引,那么查询的效率就会退化,如下图所示。

查询效率退化

这个问题可以通过在插入数据的时候通过随机函数来判断是否为该节点建索引,以及索引放到哪一级来解决。