- 浏览: 1408214 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
sdgxxtc:
[quo[color=red]te][/color]
C#使用OleDb读取Excel,生成SQL语句 -
zcs302567601:
博主,你好,一直都有个问题没有搞明白,就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻:
感谢楼主!
有向强连通和网络流大讲堂——史无前例求解最大流(最小割)、最小费用最大流 -
cp1993518:
感谢!从你的博客里学到了很多
Unity日志工具——封装,跳转 -
cp1993518:
学习了~,话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
Skip List(跳跃表)原理详解与实现
本文内容框架:
§1 Skip List 介绍
§2 Skip List 定义以及构造步骤
§3 Skip List 完整实现
§4 Skip List 概率分析
§5 小结
§1 Skip List 介绍
Skip List是一种随机化的数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。
§2 Skip List 定义以及构造步骤
Skip List定义
像下面这样(初中物理经常这样用,这里我也盗用下):
一个跳表,应该具有以下特征:
- 一个跳表应该有几个层(level)组成;
- 跳表的第一层包含所有的元素;
- 每一层都是一个有序的链表;
- 如果元素x出现在第i层,则所有比i小的层都包含x;
- 第i层的元素通过一个down指针指向下一层拥有相同值的元素;
- 在每一层中,-1和1两个元素都出现(分别表示INT_MIN和INT_MAX);
- Top指针指向最高层的第一个元素。
构建有序链表
Skip List构造步骤:
1、给定一个有序的链表。
2、选择连表中最大和最小的元素,然后从其他元素中按照一定算法(随机)随即选出一些元素,将这些元素组成有序链表。这个新的链表称为一层,原链表称为其下一层。
3、为刚选出的每个元素添加一个指针域,这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
4、重复2、3步,直到不再能选择出除最大最小元素以外的元素。
§3 Skip List 完整实现
下面来定义跳表的数据结构(基于C)
首先是每个节点的数据结构
typedef struct nodeStructure
{
int key;
int value;
struct nodeStructure *forward[1];
}nodeStructure;
跳表的结构如下
typedef struct skiplist
{
int level;
nodeStructure *header;
}skiplist;
下面是跳表的基本操作
首先是节点的创建
nodeStructure* createNode(int level,int key,int value)
{
nodeStructure *ns=(nodeStructure *)malloc(sizeof(nodeStructure)+level*sizeof(nodeStructure*));
ns->key=key;
ns->value=value;
return ns;
}
列表的初始化
列表的初始化需要初始化头部,并使头部每层(根据事先定义的MAX_LEVEL)指向末尾(NULL)。
skiplist* createSkiplist()
{
skiplist *sl=(skiplist *)malloc(sizeof(skiplist));
sl->level=0;
sl->header=createNode(MAX_LEVEL-1,0,0);
for(int i=0;i<MAX_LEVEL;i++)
{
sl->header->forward[i]=NULL;
}
return sl;
}
插入元素
插入元素的时候元素所占有的层数完全是随机的,通过随机算法产生
int randomLevel() { int k=1; while (rand()%2) k++; k=(k<MAX_LEVEL)?k:MAX_LEVEL; return k; }
跳表的插入需要三个步骤,第一步需要查找到在每层待插入位置,然后需要随机产生一个层数,最后就是从高层至下插入,插入时算法和普通链表的插入完全相同。
bool insert(skiplist *sl,int key,int value) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p, *q = NULL; p=sl->header; int k=sl->level; //从最高层往下查找需要插入的位置 //填充update for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<key)) { p=q; } update[i]=p; } //不能插入相同的key if(q&&q->key==key) { return false; } //产生一个随机层数K //新建一个待插入节点q //一层一层插入 k=randomLevel(); //更新跳表的level if(k>(sl->level)) { for(int i=sl->level; i < k; i++){ update[i] = sl->header; } sl->level=k; } q=createNode(k,key,value); //逐层更新节点的指针,和普通列表插入一样 for(int i=0;i<k;i++) { q->forward[i]=update[i]->forward[i]; update[i]->forward[i]=q; } return true; }
红色区域为辅助数组update的内容
删除节点
删除节点操作和插入差不多,找到每层需要删除的位置,删除时和操作普通链表完全一样。不过需要注意的是,如果该节点的level是最大的,则需要更新跳表的level。
bool deleteSL(skiplist *sl,int key) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<key)) { p=q; } update[i]=p; } if(q&&q->key==key) { //逐层删除,和普通列表删除一样 for(int i=0; i<sl->level; i++){ if(update[i]->forward[i]==q){ update[i]->forward[i]=q->forward[i]; } } free(q); //如果删除的是最大层的节点,那么需要重新维护跳表的 for(int i=sl->level-1; i >= 0; i--){ if(sl->header->forward[i]==NULL){ sl->level--; } } return true; } else return false; }
查找
跳表的优点就是查找比普通链表快,当然查找操作已经包含在在插入和删除过程,实现起来比较简单。
搜索key=14的示意图
int search(skiplist *sl,int key) { nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<=key)) { if(q->key==key) { return q->value; } p=q; } } return NULL; }
完整代码如下:
#include<stdio.h> #include<stdlib.h> #define MAX_LEVEL 10 //最大层数 //节点 typedef struct nodeStructure { int key; int value; struct nodeStructure *forward[1]; }nodeStructure; //跳表 typedef struct skiplist { int level; nodeStructure *header; }skiplist; //创建节点 nodeStructure* createNode(int level,int key,int value) { nodeStructure *ns=(nodeStructure *)malloc(sizeof(nodeStructure)+level*sizeof(nodeStructure*)); ns->key=key; ns->value=value; return ns; } //初始化跳表 skiplist* createSkiplist() { skiplist *sl=(skiplist *)malloc(sizeof(skiplist)); sl->level=0; sl->header=createNode(MAX_LEVEL-1,0,0); for(int i=0;i<MAX_LEVEL;i++) { sl->header->forward[i]=NULL; } return sl; } //随机产生层数 int randomLevel() { int k=1; while (rand()%2) k++; k=(k<MAX_LEVEL)?k:MAX_LEVEL; return k; } //插入节点 bool insert(skiplist *sl,int key,int value) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p, *q = NULL; p=sl->header; int k=sl->level; //从最高层往下查找需要插入的位置 //填充update for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<key)) { p=q; } update[i]=p; } //不能插入相同的key if(q&&q->key==key) { return false; } //产生一个随机层数K //新建一个待插入节点q //一层一层插入 k=randomLevel(); //更新跳表的level if(k>(sl->level)) { for(int i=sl->level; i < k; i++){ update[i] = sl->header; } sl->level=k; } q=createNode(k,key,value); //逐层更新节点的指针,和普通列表插入一样 for(int i=0;i<k;i++) { q->forward[i]=update[i]->forward[i]; update[i]->forward[i]=q; } return true; } //搜索指定key的value int search(skiplist *sl,int key) { nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<=key)) { if(q->key == key) { return q->value; } p=q; } } return NULL; } //删除指定的key bool deleteSL(skiplist *sl,int key) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<key)) { p=q; } update[i]=p; } if(q&&q->key==key) { //逐层删除,和普通列表删除一样 for(int i=0; i<sl->level; i++){ if(update[i]->forward[i]==q){ update[i]->forward[i]=q->forward[i]; } } free(q); //如果删除的是最大层的节点,那么需要重新维护跳表的 for(int i=sl->level - 1; i >= 0; i--){ if(sl->header->forward[i]==NULL){ sl->level--; } } return true; } else return false; } void printSL(skiplist *sl) { //从最高层开始打印 nodeStructure *p,*q=NULL; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--) { p=sl->header; while(q=p->forward[i]) { printf("%d -> ",p->value); p=q; } printf("\n"); } printf("\n"); } int main() { skiplist *sl=createSkiplist(); for(int i=1;i<=19;i++) { insert(sl,i,i*2); } printSL(sl); //搜索 int i=search(sl,4); printf("i=%d\n",i); //删除 bool b=deleteSL(sl,4); if(b) printf("删除成功\n"); printSL(sl); system("pause"); return 0; }
§4 Skip List 概率分析
§5 小结
本篇博文已经详细讲解了Skip List数据结构的所有内容,应该可以有一个深入的了解。如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。
参考:
①Skip List: http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_skl.htm
②Songeliu: http://www.spongeliu.com/63.html
③Shi Kai Lun : http://yilee.info/skip-list.html
④Michael T. Goodrich Roberto Tamassia Algorithm Design Foundations, Analysis, and Internet Examples
⑤http://epaperpress.com/sortsearch/skl.html
评论
每个节点应该有一个next,一个down指针,在您这里怎么只有一个forward指针呢。
你的这个forward到底是next还是down
另外在insert函数中,视乎没有很好地使用到跳跃表的查找优势,就是根据上层检查可以跳过下层的检索。
发表评论
-
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3548在C# 调用Delegate.Create ... -
数组问题集结号
2012-12-06 22:01 0数组是最简单的数据结构,数组问题作为公司招聘的笔试和面试题目 ... -
算法问题分析笔记
2012-12-05 11:59 01.Crash Balloon Zhejiang Univer ... -
Java基础进阶整理
2012-11-26 09:59 2313Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2633《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法(BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4124尊重他人的劳动,支持原创 本篇博文,D.S.Q ... -
基本技术——贪心法、分治法、动态规划三大神兵
2012-11-03 19:30 0基本技术——贪心法、分治法、动态规划三大神兵 -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:12 35620优先队列三大利器——二项堆、斐波那契堆、Pairing ... -
优先队列三大利器——二项堆、斐波那契堆、Pairing 堆
2012-11-03 13:01 3优先队列三大利器——二项堆、斐波那契堆、Pairing 堆 ... -
排序算法群星豪华大汇演
2012-10-30 00:09 3116排序算法群星豪华大汇演 排序算法相对简单些,但是由于 ... -
分布排序(distribution sorts)算法大串讲
2012-10-29 15:33 4636分布排序(distribution sorts)算法大串讲 ... -
归并排序(merge sorts)算法大串讲
2012-10-29 10:04 8298归并排序(merge sorts)算法大串讲 ... -
交换排序(exchange sorts)算法大串讲
2012-10-29 00:22 4390交换排序(exchange sorts)算法大串讲 本 ... -
选择排序(selection sorts)算法大串讲
2012-10-28 12:55 3694选择排序(selection sorts)算法大串讲 本文内 ... -
插入排序(insertion sorts)算法大串讲
2012-10-28 11:30 2724插入排序(insertion sorts ... -
伸展树(Splay Tree)尽收眼底
2012-10-27 15:11 5500伸展树(Splay Tree)尽收眼底 本文内容 ... -
红黑树(Red-Black Tree)不在话下
2012-10-26 20:54 2217红黑树(Red-Black Tree) 红黑树定义 红黑树 ...
相关推荐
跳跃表(Skiplist)是一种在Redis中广泛使用的数据结构,它作为一种概率性的平衡树替代方案,通过概率性平衡而非严格平衡,实现了更简单、更快的插入和删除算法。本篇将深入探讨跳跃表的基本概念、工作原理以及其在...
跳表(Skiplist)是一种高效的数据结构,它在实现上类似于多层索引的跳跃式访问,由Marc P. Lehmann在1990年提出。VB.NET是一种基于.NET Framework的面向对象的编程语言,它提供了丰富的库和工具,使得开发者能够...
### Skip List 数据结构详解 #### 一、引言与背景 Skip list 是一种概率性数据结构,它在很多场景下可以替代平衡树作为首选的实现方法。与平衡树相比,Skip list 具有更简单的实现、更快的速度以及更低的空间消耗...
下面我们将深入探讨跳表的基本原理、C++实现的关键点以及测试程序的设计。 跳表的核心思想是通过多层索引来加速查找过程。每一层索引称为一个“级别”,最底层被称为0级,而上一层则是下一层的两倍概率存在。最高...
跳跃表(Skiplist)技术分享 跳跃表(Skiplist)是一种高效的数据结构,能够快速查询一个有序连续元素的数据链表。它的平均查找和插入时间复杂度都是 O(log n) ,优于普通队列的 O(n) 。下面是跳跃表的详细知识点:...
下面将详细介绍跳跃表的工作原理以及如何在C#中实现它。 跳跃表的核心思想是通过随机概率增加节点的层级,使得查找效率近似于对数时间复杂度。每层节点都包含一部分下层节点,这样在查找时,可以跳过部分节点,从而...
本压缩包"skipList.rar"包含了一个用C++实现的跳跃表,该实现参考了Redis中的zskiplist。下面将详细介绍跳跃表的概念、工作原理以及C++实现的关键点。 跳跃表是一种随机化的数据结构,由多个层(level)组成,每层...
"Java实现跳跃表(skiplist)的简单实例" 跳跃表(Skiplist)是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间),并且对并发算法友好。跳跃表的结构是:假如...
2. SkipList.java: 这是跳表的主要实现文件,可能包含了一个名为`SkipList`的类,实现了跳表的数据结构和相关的操作方法,如插入、删除、查找等。这个类可能包括了节点结构的设计,以及如何随机决定每个节点的层级等...
在计算机科学领域,跳跃表(Skip List)是一种可以用来替代平衡树的数据结构,尤其是在实现有序映射(Sorted Map)和有序集合(Sorted Set)时被广泛使用。本文将详细介绍一个特殊类型的跳跃表——1-5确定性跳跃表,...
本篇将详细介绍C++实现跳跃表的原理、步骤以及如何与红黑树进行对比测试。 跳跃表(Skip List)的基本思想是通过在原有有序链表上增加多级索引,使得查找过程可以跳跃性地前进,从而减少查找次数。每条数据记录都有...
Skiplist是一种高效、随机化的数据结构,常用于数据库和搜索引擎等场景,它的主要特点是查找、插入和删除操作的时间复杂度平均为O(log N),与平衡二叉搜索树相当,但实现起来更为简单。在Go语言中实现Skiplist,可以...
ppt文档 详细介绍了skip list的算法和实现
skiplist模板类
skiplist不是传统意义上的平衡树或哈希表,而是基于链表的结构,通过多级跳转实现快速访问。 1. 跳跃列表基础概念: 跳跃列表由一系列节点组成,每个节点包含一个值和多个向前的指针。这些指针按层次排列,底层的...
跳表是一种高效的数据结构,常用于数据库和搜索引擎中,它以链表为基础并结合了随机化算法,使得在平均情况下查找、插入和删除...在实际应用中,跳表可以根据数据量动态调整层数,以达到更好的性能与空间效率的平衡。
在详细讲解二叉搜索树、B树、Skiplist跳表和哈希表的过程中,我们首先需要了解数据结构的定义及其特性,然后针对不同数据结构在大数据环境下的应用进行探究。 1. 二叉搜索树(BST): 二叉搜索树是一种特殊的二叉树...
最后,跳跃表(Skip List)是一种概率型数据结构,它通过构建多层索引来加速查找过程。每个元素在跳跃表中有多个节点,每个节点包含一个值和多个指向相邻节点的指针。较上层的节点跳过的步数更多,这样就可以快速从...
2. 定义跳跃表类(SkipList),包含头部节点,插入和查找方法。插入方法会根据概率决定节点的层级,查找方法则通过逐层遍历找到目标物品。 3. 在01背包问题的解决过程中,可能会用到跳跃表的查找方法来快速找到当前...