数据结构与算法-跳表

在学习二分查找时，我们知道二分查找需要依赖数组的随机访问的特性进行查找，而链表不具有随访问的特性，因此不能使用传统上的二分查找方法了。为了使得链表支持类似二分查找的算法，对原始的链表进行修改，修改后的链表就是跳跃表，简称跳表。跳表支持快速的插入、删除、查找操作，是一种动态的数据结构。

跳表的理解

我们知道对于链表中存储的数据有序的单链表，我们需要查找链表中的某个数据，需要从头到尾遍历，查找的时间复杂度位 O(n)，如下所示：

我们对原始链表加一级索引，如下所示：

如下图所示，对于查找值为6的节点，在原始节点上查找需要6次，而通过第一级索引进行查找，如下图所示，只需要5次，减少了查找次数。

我们再到第一级索引上在再加索引，如下图所示：

对于查找值为6的节点如下所示，查找次数为6次。

由于这个数据量不大，查找效率提升的不明显，对于数据量较大的时候，查找效率提高很快。

时间复杂度分析

首先来分析对于有 n个节点的链表，需要建立多少级索引。根据上面的例子可以得到，如果我们每两个节点会提取一个节点作为一个索引节点，那么第一级索引节点的个数为 n/2，第二级索引节点的个数为 n/4，依此类推，则第K级的索引节点的个数为 n/(2^k)。

假设索引有 h级，且第 h级的索引节点个数为2，如下图所示。则我们可以得出 n/(2^h)=2,这样可以得到 h=logn-1（这里的 log是指以2为底）,加上链表本身的一层，则整个跳表的高度为 logn。我们在跳表中查询某个数据时，如果每一层都需要遍历 m个节点，那么在跳表中查询某个数的时间复杂度为 O(m*logn)。

跳表空间复杂度分析

跳表查找效率的提高是通过建立多级索引实现的，而建立索引肯定需要消耗内存空间。对于跳表的内存空间分析并不难，对于有 n个节点的链表，第一级索引节点的个数为 n/2，第二级索引节点的个数为 n/4，最后一级的索引节点的个数为2，我们可以得出一个等比数列： n/2+n/4+n/8+...+4+2=n-2,因此跳表的空间复杂度为 O(n)。