Re: Red/black trees

[Anupam Kapoor <akapoor@xxxxxxxxxxxxxxxxxxx>]

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.
> :
> :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@xxxxxxxxxxxxx>