概述
SkipList 是由William Pugh发明的一种数据结构,它的作用类似平衡二叉树,对查找,删除,插入操作的时间复杂度为O(logN),是一种十分高效的查找结构。SkipList使用随机化的平衡方案取代了平衡二叉树的严格的平衡方案,因此它也是一种随机化的数据结构。SkipList基于并联的链表,是对有序的链表附加上随机个数的前进的链接,使得在查找过程中可以快速地跳过部分链表而得名。
如上图所示,a为普通的排好序的LinkList,在a中查找一个元素,最坏情况下,我们需要对比所有的节点,如果修改成如b那样,间隔的list中的元素加上指向前面第二个的元素指针,则查找一个元素最多需要【n/2】+ 1次对比,同理对应c来说,则需要【n/4】 + 1次,如果对任意第2^i个节点拥有i个指针来指向前面的i个节点,那么其查找效率就会降到logN,但是这种数据结构虽然可以很快的进行查找,但是对于插入和删除操作确实不切实际的。一个拥有k个向前指针的节点称为k层节点,像之前描述的结构,节点的层次分布模式为:%50为1层,25%为2层,12.5%为三层,以此类推。如果按一定比例来随机分配节点的层次的话(如图中的e),节点的第i个向前指针只需指向第i层的下一个节点。当插入一个节点时,随机的选择它的层次,并且不再需要改变。虽然有时候某些层次的安排会带来低效的执行效率,但是因为是随机化的,所以这种情况是很罕见的。
初始化
SkipList的所有层级的子list都终结于NIL(不带任何合法值的元素),刚创建的SkipList的层级为1,只有一个头结点,并且只包含一个指向NIL的向前结点。
随机化层次选择
设拥有第i个向前指针的节点,同时拥有第i+1个向前指针分布比例为p,若有一半的节点有第i个向前指针的节点,同时拥有第i+1个向前指针,则p等于1/2.则随机化的层次选择过程如下:
randomLevel() lvl := 1 -- random() that returns a random value in [0...1) while random() < p and lvl < MaxLevel do lvl := lvl + 1 return lvl
这里有个MaxLevel,它的值为 MaxLevel =L(N)= log(1/p)N (p=1/2)=log(2).N,它表示跳跃表最大允许的层次。
效率分析
设C(K)为查找第k个节点需要消耗的时间,则:
C(0) = 0 C(k) = (1–p) (在同一层查找) + p (向下一层查找)
化简得
C(k) = (1–p) (1 + C(k)) + p (1 + C(k–1)) C(k) = 1/p + C(k–1) C(k) = k/p
因为k《=MaxLevel=L(n)/p + 1/(1–p),为O(logN)
查找过程
Search(list, searchKey) x := list.eader -- loop invariant: x.key < searchKey for i := list.level downto 1 do while x.forward[i].key < searchKey do x := x.forward[i] -- x.key < searchKey <= x.forward[1].key x := x.forward[1] if x.key = searchKey then return x.value else return failure
模拟查找过程:
查找6的过程如下:
- 首先从最高层开始,发现6在 header跟6节点之间
-
然后继续降到第三层
- 还是发现6在 header跟6节点之间,降到第二层
- 第一层时,发现6在节点3和6直接,此时x指向3这个节点
-
3的下一个节点是6,刚好找到
插入过程
Insert(list, searchKey, newValue) local update[1..MaxLevel] x := list.header for i := list.level downto 1 do while x.forward[i].key < searchKey do x := x.forward[i] -- x.key < searchKey £ x.forward[i].key update[i] := x x := x.forward[1] if x.key = searchKey then x.value := newValue else lvl := randomLevel() if lvl > list.level then for i := list.level + 1 to lvl do update[i] := list.header list.level := lvl x := makeNode(lvl, searchKey, value) for i := 1 to level do x.forward[i] := update[i].forward[i] update[i].forward[i] := x
删除过程
Delete(list, searchKey) local update[1..MaxLevel] x := list.header for i := list.level downto 1 do while x.forward[i].key < searchKey do x := x.forward[i] update[i] := x x := x.forward[1] if x.key = searchKey then for i := 1 to list.level do if update[i].forward[i] != x then break update[i].forward[i] := x.forward[i] free(x) while list.level > 1 and list.header.forward[list.level] = NIL do list.level := list.level – 1
SCALA实现
package chiyx.algo.datastruct /** * Created with IntelliJ IDEA. * scala版本的跳跃表的实现 * @author qianshang@taobao.com * @since 下午11:00 13-9-2 * */ class SkipList[T <% Ordered[T]] { /** * 随机化的概率,每层节点拥有上一层指针的概率 */ private val P = 0.5 /** * 最高层级为8,则 N的合适范围在 2^^8 */ private val MaxLevel = 8 private val header: SkipNode[T] = new SkipNode[T](MaxLevel) /** * 当前的最大层级编号,从0开始编号 */ private var level = 0 /** * 随机产生插入节点的层高 * @return */ def randomLevel = { val lvl = (Math.log(1.0 - Math.random()) / Math.log(1 - P)).toInt Math.min(lvl, MaxLevel) } /** * 检查是否包含元素 * @param o * @return */ def contains(o: T) = { var x = header for (i <- level.to(0, -1)) { while (x.forward(i) != null && x.forward(i).value < o) { x = x.forward(i) } } x = x.forward(0) x != null && x.value.equals(o) } /** * 插入元素 * @param o */ def insert(o: T) { var x = header val update = new Array[SkipNode[T]](MaxLevel + 1) for (i <- level.to(0, -1)) { while (x.forward(i) != null && x.forward(i).value < o) { x = x.forward(i) } update(i) = x } x = x.forward(0) /** * 如果不存在,则创建节点 */ if (x == null || x.value != o) { val lvl = randomLevel if (lvl > level) { for (i <- level to lvl) { update(i) = header } level = lvl } x = new SkipNode[T](o, lvl) for (i <- 0 to lvl) { x.forward(i) = update(i).forward(i) update(i).forward(i) = x } } } /** * 删除操作 * @param o */ def delete(o: T) { var x = header val update = new Array[SkipNode[T]](MaxLevel + 1) for (i <- level.to(0, -1)) { while (x.forward(i) != null && x.forward(i).value < o) { x = x.forward(i) } update(i) = x } x = x.forward(0) //元素存在的情况下才需要删除 if (x != null && x.value == o) { for (i <- 0 to level) { if (update(i).forward(i) == x) { update(i).forward(i) = x.forward(i) } } while (level > 0 && header.forward(level) == null) { level = level - 1 } } } } /** * 跳跃表中的节点 * @tparam T */ private class SkipNode[T](val level: Int) { var value: T = _ /** * 指向多个层级的下个节点的指针数组 */ val forward: Array[SkipNode[T]] = new Array[SkipNode[T]](level + 1) def this(ve: T, level: Int) = { this(level) value = ve } } object SkipListApp { def main(args: Array[String]) { val sList = new SkipList[Int] sList insert 5 sList insert 4 sList insert 6 sList insert 9 println( sList contains 6) sList delete 6 println( sList contains 6) } }
相关推荐
redis中使用的skiplist数据结构
开源项目-MauriceGit-skiplist.zip,Go中非常快的Skiplist库
skiplist - Skiplist 在Go中的实现
前端开源库-fis3-deploy-skip-packedFIS3部署跳过压缩,跳过压缩文件。
跳跃表 skiplist 技术分享
信息安全_数据安全_AppSecEU2016-Timur-Khrotko-Lets-Skip-The-Pentest 安全管控 AI 安全攻击 安全可信 安全编码
跳过列表数据结构的纯python实现。 介绍 跳过列表是一种数据结构,可以用来代替平衡树。 跳过列表使用概率平衡而不是严格执行的平衡,因此,与等效树平衡算法相比,跳过列表中插入和删除的算法要简单得多,并且速度...
import SkipList from '@aureooms/js-skip-list' ;const list = SkipList . from ( decreasing , range ( 10000 ) ) ;[ ... list ] ; // [9999, 9998, ...]list . add ( ... )list . get ( ... )list . has ( ... )...
C++ 实现的跳跃表skiplist,支持模板,参照Redis的zskiplist跳跃表实现, 支持模板,适合用来做排行榜
跳表是redis的一个核心组件,也同时被广泛地运用到了各种缓存地实现当中,它的主要优点,就是可以跟红黑树、AVL等平衡树一样,做到比较稳定地插入、查询与删除。理论插入查询删除的算法时间复杂度为O(logN)。
数据结构原本,大一统,外文书原版 Data structures Contents Articles Introduction 1 Data structure 1 Linked data structure 3 Succinct data structure 6 Implicit data structure 8 Compressed data structure...
编写环境 VS2008 支持 添加,插入,搜索,输出 等功能
skiplist JAVA程序,数据结构课的Project
1. 介绍经典的skiplist数据结构,并进简单的算法分析 2. 讨论Redis的skiplist的具体实现 3. 讨论sorted set是如何在skipl
skiplist模板类
A 16-bit Carry Skip Adder Designed by Reversible Logic
介绍skip list实现的文档
ppt文档 详细介绍了skip list的算法和实现
Skip Lists
跳表(skiplist)是一个非常优秀的数据结构,实现简单,插入、删除、查找的复杂度均为O(logN),下面这篇文章主要介绍了c++实现跳跃表(Skip List)的相关资料,需要的朋友可以参考借鉴,下面随着小编来一起学习学习...