数据结构与算法之美-跳表-极客时间学习笔记

二分查找是针对数组结构的，那么链表结构有没有类似的方法可以实现快速查找？

按照以空间换时间的思路，我们把单链表想象成一本书，每个节点都是1页，那么快速搜索的方法就是建立目录索引（并非完全相同的概念，这里的索引也需要遍历，不能跳跃）。从一页页翻页变成在按照索引一个个查找，然后再下一层进入到节点层查找。

为了加快搜索速度，可以建立不止一级索引，上一层以下一层为基础，每次跳过1个元素（这里并不固定，只是常规是跳1个或者2个）。可以看到上图，5层索引后查找第62个节点，只需要11次。

先假设每层索引跳1个点来分析具体的时间复杂度和空间复杂度。每次索引数据点减少1半，最高一层索引假设是2个点。那么最大的索引层数是log2n-1，而每一层里面可能走过的数据点最多就是3个，故复杂度是O(3*logn)。额外增加的空间是等比数列，索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2，故空间复杂度是O(n)。实际场景中节点数据的空间可能远大于索引节点，所以这种额外的空间开销还是可以接受。

和红黑树类似，经过插入、删除操作后，原始的数据结构会变形，索引之间间隔的元素可能不再是单个元素。也就存在查找效率退化的风险，变成单链表，查找效率O(n)（好多精妙的数据结构经过插入删除后都存在退化风险）。为防止跳表退化，就需要使用一个随机函数，在插入数据的同时，将此数据点也同步插入到索引中