akapoor at starentnetworks.com
Mon Apr 18 02:59:32 PDT 2005
Matthew Dillon <dillon at xxxxxxxxxxxxxxxxxxxx> writes:
> Skip lists... Well, based on that documentation my first reaction
> is "ick". It looks like a flattened, bastardized n-way tree. Searches
> basically cost the same. Insertions and deletions should theoretically
> be faster, but the trade-off is against additional loss of determinism.
| > Degenerate conditions have a way of sneaking up on data structures
| > that try to be sneaky. I'd rather have the determinism of a red-black
| > tree, frankly.
that's exactly why, i had mentioned earlier about the 'deterministic'
version of the same data structure, called 'deterministic skip lists'.
More information about the Kernel