Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : Paul Dietz
Date : Thu Sep 15 2005 04:09 pm

Ben Pfaff wrote:

> For what it's worth, I now have empirical results comparing
> unbalanced BSTs, red-black trees, AVL trees, and splay trees.
> You can read them at
>         http://benpfaff.org/papers
> Look at "Performance Analysis of BSTs in System Software".

Very interesting!

I noticed the full version of that paper does not consider splay
trees for one application because '[splay trees do not] provide
guaranteed performance'  (section 5.2, last paragraph).

But this is not entirely accurate.  Splay trees do provide the guarantee
that N operations, starting from a tree of size <= N, will take
at most O(N log N) time.  This should be enough to avoid DOS
attacks, since the attacker must interleave many fast operations
between the occasional slow ones.

	Paul

.