跳表是个概率性的的数据结构,由William Pugh在1990年发明,列表基于平行的链接列表,效率相对二叉搜索树(对于大多数操作平均需要O(log n)时间)有显著改善
例子:
1
1-----4---6
1---3-4---6-----9
1-2-3-4-5-6-7-8-9-10
最底层为所有排好序的元素组成的链表
次底层为按概率1/p组成的排好序的链表
再次底层为1/p^2
直到顶层为首节点
可以看出层数为logpN,查找元素x时需要在每层中查找的步数为p,则总体查询代价为p*logpN
所以跳表查询的平均时间复杂度为Θ(logN),最好情况为1,最坏情况为N
跳表的ruby实现示例:
class Node
attr_accessor :key, :next, :down
def initialize(x)
key = x
next = nil
down = nil
end
end
class SkipList
def search(x)
return nil if head.nil?
p = head
while true
while !p.next.nil? && p.next.key < x
p = p.next
end
return p if p.down.nil?
p = p.down
end
end
end
BTW:谁能帮我实现完整的insert和update方法啊?
Skip List PPT
分享到:
相关推荐
skiplist 跳表C++实现,资料参考 en.wikipedia.org/wiki/Skip_list
二叉搜索树 B树 Skiplist跳表 哈希表 大数据哈希表应用,注意:此资源上传文件错误(选成快捷方式了),请移除,我没有找到删除按钮。
skiplist的C++实现,包含test程序
一种可以和平衡树字典操作匹敌的数据结构,它是链表最优秀的应用,思想简单,编程容易,基本字典操作能达到O(log(n))
跳表 (Skip List) 是一种有序的链表数据结构,它通过在每个节点中存储多个指针,来提高查询效率。它的特点如下: 有序性:跳表中的元素是按照键值排序的,查询时可以利用这种有序性来加速查询速度。 动态的高度:...
简单得实现跳表相关功能 SkipList<Integer> skipList = new SkipList(maxLevel); 提供insert和seach接口 删除接口可做类似操作
如果是说链表是排序的,并且节点中还存储了指向前面第二个节点的指针的话,那么在查找一个节点时,仅仅需要遍历N/2个节点即可。这基本上就是跳表的核心思想,其实也是一
跳表是由William Pugh发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees,在该论文中详 细解释了跳表的数据结构和插入删除操作。
这个是跳表的头文件
之前所有的答案都不太靠谱(完全扯淡)请看开发者说的,他为什么选用skiplist The Skip listThere are a few reasons:1)
#资源达人分享计划#
跳跃表 skiplist 技术分享
main.cpp 包含skiplist.h使用跳表进行数据操作 skiplist.h 跳表核心实现 README.md 中文介绍 README-en.md 英文介绍 bin 生成可执行文件目录 makefile 编译脚本 store 数据落盘的文件存放在这个文件夹 stress_test_...
跳表是redis的一个核心组件,也同时被广泛地运用到了各种缓存地实现当中,它的主要优点,就是可以跟红黑树、AVL等平衡树一样,做到比较稳定地插入、查询与删除。理论插入查询删除的算法时间复杂度为O(logN)。
A SkipList Implemented By Template, 一个支持模板的跳表
改造之后的数据结构叫作跳表。 定义 跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n),优于普通队列的O(n)。性能上和红黑树,AVL树...
跳表的C++实现,具体介绍可以参见文章:https://blog.csdn.net/qq_41453285/article/details/103449903
跳表 java实现版本,内含两个java文件。原文讲解链接:https://blog.csdn.net/weixin_38073885/article/details/86690517
跳表完整代码
此处定义了三种集合:SkipList的行为几乎与任何其他双端列表一样。 OrderedSkipList确保始终对元素进行排序。 仍允许使用给定索引的访问节点。 SkipMap在其中排序键的地图。 文档可以在docs.rs上找到,货箱可以在...