Re: Red/black trees
--L6iaP+gRLNZHKoI4
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
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. Search=
es
> basically cost the same. Insertions and deletions should theoretical=
ly
> be faster, but the trade-off is against additional loss of determinis=
m.
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.
>=20
> Patricia trees are basically just radix trees... unsuitable for=20
> arranging large fixed-length numerical values.
>=20
> -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
--L6iaP+gRLNZHKoI4
Content-Type: application/pgp-signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (FreeBSD)
iD8DBQFCY2LOSkf3jVXOdl0RAvBZAJ90jqhnz50OPsIpqQsaJvpY0eygAACgj34f
UmoyFHgkznx3wDiTYhqP2NQ=
=eaUh
-----END PGP SIGNATURE-----
--L6iaP+gRLNZHKoI4--
討論串 (同標題文章)
完整討論串 (本文為第 10 之 11 篇)：