跳过列表 - 曾经使用过他们？ [英] Skip Lists -- ever used them?

问题描述

我想知道有人是否曾经使用跳过列表。它看起来具有与平衡二叉树大致相同的优点，但是更容易实现。如果你有，你是否编写自己的，或者使用预先写的图书馆（如果是的话，它的名字是什么）？

I'm wondering whether anyone here has ever used a skip list. It looks to have roughly the same advantages as a balanced binary tree, but is simpler to implement. If you have, did you write your own, or use a pre-written library (and if so, what was its name)?

推荐答案

几年前，我实现了自己的概率算法类。我不知道任何库实现，但是已经很久了。实现起来很简单我记得他们对大数据集有一些非常好的属性，并避免了一些重新平衡的问题。我认为实现也比二次尝试更简单。这里有一个很好的讨论和一些示例c ++代码：

Years ago I implemented my own for a probabilistic algorithms class. I'm not aware of any library implementations, but it's been a long time. It is pretty simple to implement. As I recall they had some really nice properties for large data sets and avoided some of the problems of rebalancing. I think the implementation is also simpler than binary tries in general. There is a nice discussion and some sample c++ code here:

http://www.ddj.us/cpp/184403579?pgno=1

还有一个小程序，运行示范。可爱的90年代的Java光阴在这里：

There's also an applet with a running demonstration. Cute 90's Java shininess here:

http://www.geocities.com/siliconvalley/network/1854/skiplist.html

这篇关于跳过列表 - 曾经使用过他们？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！