Re: Red/black trees
Matthew Dillon <dillon@apollo.backplane.com> writes:
> :is there are reason to not use skip lists ? now that we don't have to
> :rely on probabilistic measures anymore.
> :
> :thanks
> :kind regards
> :anupam
>
> 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:
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf.
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.
kind regards
anupam
>
> -Matt
> Matthew Dillon
> <dillon@backplane.com>
討論串 (同標題文章)
完整討論串 (本文為第 8 之 11 篇)：