Skip List

Published: by Creative Commons Licence

  • Tags:

假设我们有一个列表,如果希望在列表中支持查询操作,那么最好的方法就是保证列表是有序的,并通过二分查找法来查找指定元素。

但是如果我们希望还能支持插入和删除操作,那么对列表预先排序就没有意义了。

跳跃链表的方法就是维护一个多级有序链表,之后就通过多级链表来优化。

查询操作。查询关键字k对应的值。首先我们选择一个链表级别L,之后我们从L级链表开始查找。找到元素x,记其后一个元素为y,使得x<=k<y。 之后查询L-1级链表,但是从x点开始查询。直到第0级,则从x开始暴力查找即可。

插入操作。首先我们要找到0级链表的插入位置(和查询一个时间复杂度),之后我们决定好插入位置后还要决定是否要插入到上级列表中。 决定的逻辑如下,投掷一枚硬币,硬币为反面的概率为P,如果硬币为正面则插入到上级链表,同时继续决定是否继续插入到上级链表,直到投出的硬币 为反面,才停止插入。比如"正正反",则插入到0级,1级,2级链表中。时间复杂度为查询的时间复杂度加上插入结点数目。

而删除操作也是类似的,先找到元素在各级链表中出现的位置,时间复杂度同样为查询的时间复杂度。

执行一次插入中,硬币反面出现之前正面出现的次数是几何分布问题,因此其期望次数为1/p,当p确认时,可以认为是常数。

之后我们再考虑一下查询操作的时间复杂度。我们记l(i)表示从第L级第一个元素开始到查询到第i级对应元素x(x是第i级列表中仅次于x的最大元素)所扫描 过结点的期望数目。由于考虑x有1-p的概率有上级结点,换言之,我们有l(i)<=p*(l(i)+1)+(1-p)*l(i+1)。可以推出l(i)=p/(1-p)+l(i+1),因此我们可以得出 l(i)=(L-i)*p/(1-p)+l(L)。由于l(L)是开始搜索的层,其期望链表长度为O(n*p^L)。考虑到当决定后p/(1-p)是常数,故时间复杂度为l(0)=O(L+n*p^L)。 我们可以取p=-ln(n)/ln(p),这样l(0)=O(1-ln(n)/ln(p))。若我们取p=0.5,则l(0)=O(1+log2(n))。