Red/black trees

Anupam Kapoor akapoor at
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'.

kind regards

More information about the Kernel mailing list