数据结构和算法/数据结构与算法之美/9.跳表

跳表

用链表实现的类似于二分查找的数据结构，可以支持快速的插入、查找、删除操作

跳表类似于二分查找，但是因为是链表，不能随机访问。可以对原始链表跳跃性建立一级、二级索引…可以发现建立了索引之后，需要遍历的元素个数变少了。

链表如果有 n 个节点，第一级索引有 n/2 个节点，二级索引有 n/4 个节点，第 k 级索引的节点个数是 $n/2^k$ 个；

假设最高一级索引有两个节点 $n/2^k = 2$，$k = log_2n - 1$，整个跳表的高度是 $log_2n$，如果每一层要遍历 m 个节点，则时间复杂度是 $O(mlog_2n)$。每一层遍历的节点个数是常量级的，所以跳表的查询时间复杂度是 $O(log_2n)$。

如果步长为 2，需要的额外空间每一层是 n/2、n/4、n/8…4、2，求和 $S_n = (a_1-a_n*q)/(1-q)$ 共有 n-2 个节点。则空间复杂度为 $O(n)$。

跳表利用查询的性能可以很方便的找到插入位置，寻找插入位置的时间复杂度是 $O(logn)$，链表的插入时间复杂度是 $O(1)$，总体时间复杂度是 $O(logn)$。跳表如果在一个索引区间插入元素过多时可能会造成跳表的性能退化，极端情况下退化到单向链表，所以跳表的索引要能动态更新。

跳表的删除，也是需要查询到删除的位置，但是如果是单项跳表，需要记录删除位置的前一个元素，如果是双向列表则不需要。

Redis的有序集合 zset 使用了 ziplist(压缩链表)和 skiplist(跳表)两种实现方式。当有序结合的元素少于 128 个，所有元素大小小于 64 字节使用 ziplist，不满足这两个条件时使用 skiplist。