Messages in this thread | | | Date | Fri, 22 Jan 1999 10:13:06 -0800 | From | "David S. Miller" <> | Subject | Re: arca-vm-26 |
| |
Date: Fri, 22 Jan 1999 10:12:07 -0500 (EST) From: Benjamin Saller Bender <case@appliedtheory.com>
I too like skip-list, the avg cost per ptr is low and things like merges are very easy, but when raw perf. is an issue a good RBtree impl usually kills a skip-list. I have and use both, but skip-list is almost never a better solution than an RBtree.
I guess I'm usually biased towards hashes because most of the problems I care about (read as: socket demultiplex in the networking) requires excellent insert/delete latencies.
What sort of properties do RB trees have for insert and delete? Can they be done in O(1) time like a hash insert/delete can?
Later, David S. Miller davem@dm.cobaltmicro.com
- 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/
| |