Re: Red/black trees

[Anupam Kapoor <akapoor@xxxxxxxxxxxxxxxxxxx>]

Matthew Dillon <dillon@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'.

kind regards
anupam