[lkml]   [1999]   [Jan]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: arca-vm-26
On Thu, 21 Jan 1999, Alan Mimms 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.

> subsystems in our system at work that would have been ready candidates for AVL or
> RB trees (or any of a cast of thousands of others) with skiplists to very good
> effect in insertion, deletion and search speed. I would be happy to supply
> pointers if you're interested. The code is trivial compared to any other tree

Sure, I _am_ interested. Please give me pointers (on the web, I don't have
money for books ;).

> management scheme I know. Skiplists maintain balance and give O(log2 N)
> performance for insert, delete AND search. There are variants that have no

I'll tell you what I'll think when I'll know what them are.

Andrea Arcangeli

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:49    [from the cache]
©2003-2014 Jasper Spaans. hosted at Digital Ocean