> 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 majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/