Chinaunix首页 | 论坛 | 博客
  • 博客访问: 308396
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2012-08-04 16:25:47

skiplist

skiplist 是一种类似于红黑树,B树,treap的平衡搜索树结构,不过相比实现而言,简单多了,也就是通过将二分搜索组织成链表数组的形式,每一层链表链接不同长度的元素(类似shell排序每次跳跃的偏移量),比较理想的跳跃间隔为2^n(n为链表数组索引),这样的话效率最高,但调整的代价非常高昂,最简单的情形就是通过随机决定.

Alt skiplist

  • 搜索操作:通过链表数组的最上层开始进行搜索,根据元素的大小,一直搜索到最底层.

  • 插入操作:插入元素时,随机决定插入的高度,然后插入到对应的高度.

  • 删除操作:当搜索到指定元素后,开始类似于链表删除一样进行方面,不过还需要进行上下层之间的删除.

在实现skiplist时MIT的公开课(非常好的资料):跳跃表

我也实现了一个版本在这里:skiplist

阅读(755) | 评论(0) | 转发(0) |
0

上一篇:语言中的闭包

下一篇:tcp/ip 分析(1)

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册