浅识SkipList – 九茶

跳表(SkipList)简介:

给你一个有序数组,如果现在需要查找某一个数字,你可能会用二分法。

但是如果给你的是一个有序链表,那就用不上二分法了,你能想到什么方法?

跳表是一种很好的选择,理解和实现出来也相对比较容易。

 

 

跳表的查询:

例如给出链表: 30 → 40 → 50 → 60 → 70 → 90

现在要插入一个 80 ,如果是用普通方法从头到尾逐个搜索的话需要比较的次数是 6 。但是如果下面的跳表,则只需要比较 4 次(在元素数量大的时候优势将会很明显):

 

首先认识一下跳表的结构,以上例子的跳表有四层,其中最下面一层是完整的链表(即包含所有元素)。第 i 层的元素间隔取出,充当“索引”的功能,组成第 i-1 层的元素……

查找元素的步骤(以80为例):

首先在第四层比较:80<=30 不成立,第四层比较完毕,进入第三层;

在第三层:80<=50 不成立,第三层比较完毕,进入第二层;

在第二层:80<=70 不成立,第二层比较完毕,进入第一层;

在第一层:80<=90 成立,则找到80的位置,插入即可。

 

再例如下面的跳表(-1表示开头,1表示结尾):

查询 117 的步骤:

首先在第三层比较:117<=21 不成立,再比较 117<=37 不成立,第三层比较完毕,进入第二层;

在第二层:117<=71 不成立,第二层比较完毕,进入第一层;

在第一层:117<=85不成立,再比较 117<=117 成立,则找到117的位置。

 

 

跳表的插入:

以上步骤已经找到某个元素的位置了,然后在插入某个元素之后还需要考虑是否要将它当做“索引元素”?

例如在第一个例子中:在第一层的链表中查找到并插入80,之后还需要在第二层插入80吗?第三层呢?到底需要在多少层插入80?

 

很有意思,这个答案是由一个随机数决定的,也就是说你还需要添加一个产生随机数的代码,产生一个随机数来决定到底需要在多少层插入80(一般随机数的范围是 [1, 已有层数+1] )。

但不管插入几行跳表都要满足:如果元素在第 i 层出现了,则一定也出现在 i-1 层。例如对于第一例插入80的情况,如果产生随机数为2,则一定是在第一层和第二层插入80。

 

 

跳表的删除:

跳表的删除简单多了,如果要删除某元素,则所有层的该元素都要删除。例如对于第一例要删除50,则第一层、第二层、第三层的 50 都要删除。

 

 

跳表的核心思想及优点:

很明显,跳表主要是利用了“索引”的功能,以空间换时间的思想,使算法的时间复杂度降低到了 O(logn)!

相对于数组而言,链表最大的优点就是能动态地分配存储空间、增删改非常方便,但致命的缺点就在于查找。

而SkipList的思想简直就是链表的救星,大大缩减了它的缺陷,使链表的使用更加广泛和方便。

 

参考文献:https://en.wikipedia.org/wiki/Skip_listhttp://blog.sina.com.cn/s/blog_72995dcc01017w1t.html

本文链接:浅识SkipList,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量