skiplist 跳跃表

1713阅读 0评论2012-08-04 datao0907
分类:C/C++

skiplist

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

Alt skiplist

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

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

上一篇:语言中的闭包
下一篇:tcp/ip 分析(1)