Gianni Mariani <gi*******@mariani.ws> writes:

Jerry Coffin wrote:

... I've yet to see any based around skip lists -- the range of

variation I've seen so far has been from Red/Black trees to AVL

trees.

What's a skip list ?

It's a list where some of the nodes contain additional pointers to

nodes farther away - every 2nd node points 2 nodes away, every 4th

node points 4 nodes away etc. - every Nth node has an additional

pointer N nodes away (called a pointer of order N).

In a perfect skip list, searching is always O(log n), but insertion

and deletion are O(N) - so you can use randomized skip lists, where

the probability that a given node gets a pointer of order N is

1/2^N - in worst case, this leads to an ordinary list, but in

average, it's as good as a perfect skip list.

for further reading, see

W. Pugh, Skip lists: A probabilistic alternative to balanced trees.

In Proc. Workshop of Algorithms and Data Structures, p. 437-449,

1989, Lecture Notes in Computer Science 382

W. Pugh, Skip lists: A probabilistic alternative to balanced trees.

Comm. ACM, 33(6):668-676, 1990

HTH & kind regards

frank

--

Frank Schmitt

4SC AG phone: +49 89 700763-0

e-mail: frankNO DOT SPAMschmitt AT 4sc DOT com