DragonFly kernel List (threaded) for 2005-04
Re: Red/black trees
Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx> writes:
> :is there are reason to not use skip lists ? now that we don't have to
> :rely on probabilistic measures anymore.
> :kind regards
> I'm not sure what you mean. What is a 'skip' list and how would it
> compare against a red-black tree ?
here is the link to the skip list paper from william pugh:
briefly (from the abstract of the above paper):
| Skip lists are a data structure that can be used in place of balanced trees.
| Skip lists use probabilistic balancing rather than strictly enforced balancing
| and as a result the algorithms for insertion and deletion in skip lists are
| much simpler and significantly faster than equivalent algorithms for
| balanced trees.
also, you can google for 'deterministic skip list' for a deterministic
alternatives to the data structure described in the above paper.
> Matthew Dillon