DragonFly BSD
DragonFly kernel List (threaded) for 2005-04
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Re: Red/black trees


From: Anupam Kapoor <akapoor@xxxxxxxxxxxxxxxxxxx>
Date: Mon, 18 Apr 2005 14:31:36 +0530

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



[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]