文档章节

跳表SkipList

j
 jack12153
发布于 2016/08/04 11:09
字数 1070
阅读 8
收藏 0

为什么选择跳表

目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等。

 

想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树

出来吗? 很难吧,这需要时间,要考虑很多细节,要参考一堆算法与数据结构之类的树,

还要参考网上的代码,相当麻烦。

 

用跳表吧,跳表是一种随机化的数据结构,目前开源软件 Redis 和 LevelDB 都有用到它,

它的效率和红黑树以及 AVL 树不相上下,但跳表的原理相当简单,只要你能熟练操作链表,

就能轻松实现一个 SkipList。

 

有序表的搜索

考虑一个有序表:


 

从该有序表中搜索元素 < 23, 43, 59 > ,需要比较的次数分别为 < 2, 4, 6 >,总共比较的次数

为 2 + 4 + 6 = 12 次。有没有优化的算法吗?  链表是有序的,但不能使用二分查找。类似二叉

搜索树,我们把一些节点提取出来,作为索引。得到如下结构:



 这里我们把 < 14, 34, 50, 72 > 提取出来作为一级索引,这样搜索的时候就可以减少比较次数了。

 我们还可以再从一级索引提取一些元素出来,作为二级索引,变成如下结构:

 

  

 

     这里元素不多,体现不出优势,如果元素足够多,这种索引结构就能体现出优势来了。

 

跳表

下面的结构是就是跳表:

 其中 -1 表示 INT_MIN, 链表的最小值,1 表示 INT_MAX,链表的最大值。

 

 

跳表具有如下性质:

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。

(5) 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

 

跳表的搜索


 

例子:查找元素 117

(1) 比较 21, 比 21 大,往后面找

(2) 比较 37,   比 37大,比链表最大值小,从 37 的下面一层开始找

(3) 比较 71,  比 71 大,比链表最大值小,从 71 的下面一层开始找

(4) 比较 85, 比 85 大,从后面找

(5) 比较 117, 等于 117, 找到了节点。

 

具体的搜索算法如下: 

 

C代码

/* 如果存在 x, 返回 x 所在的节点, 
 * 否则返回 x 的后继节点 */  
find(x)   
{  
    p = top;  
    while (1) {  
        while (p->next->key < x)  
            p = p->next;  
        if (p->down == NULL)   
            return p->next;  
        p = p->down;  
    }  
}  

 

跳表的插入

先确定该元素要占据的层数 K(采用丢硬币的方式,这完全是随机的)

然后在 Level 1 ... Level K 各个层的链表都插入元素。

例子:插入 119, K = 2


 

如果 K 大于链表的层数,则要添加新的层。

例子:插入 119, K = 4


 

丢硬币决定 K

插入元素的时候,元素所占有的层数完全是随机的,通过一下随机算法产生:

 

C代码 

int random_level()  
{  
    K = 1;  
  
    while (random(0,1))  
        K++;  
  
    return K;  
}  

相当与做一次丢硬币的实验,如果遇到正面,继续丢,遇到反面,则停止,

用实验中丢硬币的次数 K 作为元素占有的层数。显然随机变量 K 满足参数为 p = 1/2 的几何分布,

K 的期望值 E[K] = 1/p = 2. 就是说,各个元素的层数,期望值是 2 层。

 

 

跳表的高度。

n 个元素的跳表,每个元素插入的时候都要做一次实验,用来决定元素占据的层数 K,

跳表的高度等于这 n 次实验中产生的最大 K,待续。。。

 

跳表的空间复杂度分析

根据上面的分析,每个元素的期望高度为 2, 一个大小为 n 的跳表,其节点数目的

期望值是 2n。

 

跳表的删除

在各个层中找到包含 x 的节点,使用标准的 delete from list 方法删除该节点。

例子:删除 71


本文转载自:http://kenby.iteye.com/blog/1187303

共有 人打赏支持
j
粉丝 0
博文 1
码字总数 0
作品 0
东城
私信 提问
skiplist 跳跃表详解及其编程实现

skiplist介绍 跳表(skip List)是一种随机化的数据结构,基于并联的链表,实现简单,插入、删除、查找的复杂度均为O(logN)。跳表的具体定义, 请参考参考维基百科 点我,中文版。跳表是由Wil...

gfsfg8545
2014/03/01
0
0
Redis 2.8.9源码 - 跳表的实现

本文为作者原创,转载请注明出处:http://my.oschina.net/fuckphp/blog/280168 本文代码可以在 src/redis.h 和 src/tzset.c 两个文件中找到,关于跳表相关的api请参考另外一篇文章 Redis 2....

logbird
2014/06/16
0
1
Java 并发之 ConcurrentSkipListMap 简述

JCIP 提到了在 Java 6 中引入了两个新的并发集合类 和 。其实只要介绍一下 即可(后面简称为 CSLM),因为我们都知道 JDK 中 Set 是基于 Map 实现的。简而言之,CSLM 是一个并发的、可排序的...

编走编想
2014/01/08
0
0
leveldb 源码分析 —— SkipList跳表

leveldb 源码分析 —— SkipList跳表 原文 leveldb 存取数据,都在用 MemTable 这个结构体,而 MemTable 核心在于 level::MemTable::Table,也就是 。 SkipList 看名字就知道,跳表,是一种数...

Abson在简书
2017/12/21
0
0
RocksDB · 特性介绍 · HashLinkList 内存表

Table of Contents RocksDB 内存表简介 RocksDB 是一个基于 LSM 树(Log-Structured Merge-tree)结构的单机数据库引擎,内存表是它最重要的数据结构之一。除了默认的跳表(SkipList)之外,...

阿里云RDS-数据库内核组
2017/05/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 升级中的一些常见问题

升级的时候遇到了问题了吗? 如果你想尝试重新进行升级的话,你需要首先重新恢复老的备份。不要尝试再次对 Confluence 进行升级或者在升级失败后重新启动老的 Confluence。 在升级过程中的一...

honeymoose
今天
2
0
C++随笔(四)Nuget打包

首先把自己编译好的包全部准备到一个文件夹 像这样 接下来新建一个文本文档,后缀名叫.nuspec 填写内容 <?xml version="1.0"?><package xmlns="http://schemas.microsoft.com/packaging/201......

Pulsar-V
今天
2
0
再谈使用开源软件搭建数据分析平台

三年前,我写了这篇博客使用开源软件快速搭建数据分析平台, 当时收到了许多的反馈,有50个点赞和300+的收藏。到现在我还能收到一些关于dataplay2的问题。在过去的三年,开源社区和新技术的发...

naughty
今天
3
0
Python3的日期和时间

python 中处理日期时间数据通常使用datetime和time库 因为这两个库中的一些功能有些重复,所以,首先我们来比较一下这两个库的区别,这可以帮助我们在适当的情况下时候合适的库。 在Python文...

编程老陆
今天
2
0
分布式面试整理

并发和并行 并行是两个任务同时进行,而并发呢,则是一会做一个任务一会又切换做另一个任务。 临界区 临界区用来表示一种公共资源或者说是共享数据,可以被多个线程使用,但是每一次,只能有...

群星纪元
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部