Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : Googmeister
Date : Mon Sep 12 2005 05:30 pm


A. Bolmarcich wrote:
> On 2005-09-11, Ben Pfaff <blp@cs.stanford.edu> wrote:
> >> Adding nodes to a tree in random order.  Searching the tree for all
> >> the nodes in it and for the same number of nodes not in it.  Deleting
> >> node from the tree in random order.

> > That's going to seriously bias performance in favor of the
> > simplest possible data structure.  When insertions, searches, and
> > deletions are done in random order, there is no advantage to
> > balancing.

Note that adding random deletions to the mix in a BST does not keep
the height log(n) - I think it becomes sqrt(n). So maybe "no advantage"
is too strong. But I agree that it will seriously bias performance.

> Do you have recommended orders for the insertions, searches, and
> deletions?

Test with random inputs, but also test with real-world inputs.
Ben's paper accomplishes the latter by analyzing the
performance of symbol tables that are components in
real-world applications. It's alot of work to do these kinds
of experiments, so I applaud Ben for his methodology.

.