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: Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>
Date: Mon, 18 Apr 2005 00:14:27 -0700 (PDT)

    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.

    Patricia trees are basically just radix trees... unsuitable for 
    arranging large fixed-length numerical values.

						-Matt



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