Red/black trees

Matthew Dillon dillon at apollo.backplane.com
Mon Apr 18 00:15:52 PDT 2005


    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





More information about the Kernel mailing list