Messages in this thread |  | | | Date | Thu, 21 Jan 1999 20:56:12 +0100 (CET) | | From | Andrea Arcangeli <> | | Subject | Re: 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 majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
|  |