Red/black trees

[Devon H. O'Dell]

On Mon, Apr 18, 2005 at 12:14:27AM -0700, Matthew Dillon wrote:
>     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.

It's a quite interesting ADT that behaves in some ways like a
DAG, as I discovered after discussing it with Daniel Hartmeier.
PF uses skip lists for its ruleset, which behave in a quite
interesting way. In the case that two rules match the same
object, they are compiled in such a way that they will `skip' to
the node containing that check. I found this quite interesting,
because it performs very well in normal case, although it does
have a O(n) performance at worst case.

I've been researching various algorithms for use in packet
classification, which has produced a variety of various papers,
all with interesting discussions.

I've not been following this thread very well, so I'm not sure
what this is for. If the data is random, a skip list probably
wouldn't be great. So, if the rest of this email is off-key,
sorry.

>     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

I suppose a DAG deserves discussion as well, since it allows for
a good bit of compression since multiple nodes may point to each
other. For instance:

                     (23)
                    /    \
                  (15)--(19)
                 /     /    \
                 \    /    (12)
                  (11)----/  /
                     \      /
                      \    /
                       \  /
                       (10)

This graph has no real life purpose, but perhaps shows how such a
diagram could be compressed. The same thing as a binary tree
might look like:

                    (23)
                   /    \
                  /    (19)
                 /    /    \
               (15) (11)  (12)
              /   \      /    \
            (11) (19)  (11)  (10)

I'm sure there's a better way to order or balance this tree.

Anyway, hope this isn't too off topic.

--Devon
Attachment:
pgp00013.pgp
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pgp00013.pgp
Type: application/octet-stream
Size: 187 bytes
Desc: "Description: PGP signature"
URL: <http://lists.dragonflybsd.org/pipermail/kernel/attachments/20050418/c3fed49a/attachment-0020.obj>