On Thu, Jan 21, 1999 at 08:56:12PM +0100, Andrea Arcangeli wrote:
> > I do not wish to start a religious war about data structures. Have you considered
> > the relatively new data structure called a 'skip list'? I have replaced several
>
> Never heard about them.
Pretty nice beasts. When I learned about them, I didn't quite consider them
a better alternative to various trees, but I guess smarter people (smarter
people with more time) have studied them extensively enough to show that
they are indeed a better choice at times.
The implementation is indeed simple. Far simpler than any self-balancing
tree (tough one has to admit that writing a B+ tree implementation is an
endless source of fun). Analyzing the complexity, at least in the variant
I've learned, isn't all that straight forward, as the algorithm is
probabilistic.
Anyway, a reference 'on the web' is http://wannabe.guru.org/alg/node35.html
(it is a very extensive reference of various algorithms. A must keep in your
bookmark file if your bank account doesn't look all that good...). I just
saw that it has a reference to the original paper presenting the data
structure, and this might make an interesting reading.
Nimrod