分类： C/C++
2012-08-04 16:25:47
是一种类似于红黑树,B树,treap的平衡搜索树结构,不过相比实现而言,简单多了,也就是通过将二分搜索组织成链表数组的形式,每一层链表链接不同长度的元素(类似shell排序每次跳跃的偏移量),比较理想的跳跃间隔为2^n(n为链表数组索引),这样的话效率最高,但调整的代价非常高昂,最简单的情形就是通过随机决定.
搜索操作:通过链表数组的最上层开始进行搜索,根据元素的大小,一直搜索到最底层.
插入操作:插入元素时,随机决定插入的高度,然后插入到对应的高度.
删除操作:当搜索到指定元素后,开始类似于链表删除一样进行方面,不过还需要进行上下层之间的删除.
在实现skiplist时MIT的公开课(非常好的资料):
我也实现了一个版本在这里:
