Subj : Re: Balanced trees vs. B-trees
To   : comp.programming
From : Rob Thorpe
Date : Sun Sep 11 2005 05:02 pm

A. Bolmarcich wrote:
> On 2005-09-10, Ben Pfaff <blp@cs.stanford.edu> wrote:
> > "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> writes:
> >
> >> My general conclusions are that AVL trees have the best performance and
> >> least average node depth.  Red-Black trees have slightly lower
> >> performance than AVL tress and slightly greater average node depth.
> >> trees.  Binary B-Trees have slightly lower performance than Red-Black
> >> trees and even greater average node depth.  However, when parent
> >> pointers are not present the performance of the insert node function
> >> of Red-Black trees is much worse than that of AVL trees and Binary
> >> B-Trees.
> >
> > It is difficult to compare the performance of data structures in
> > the absence of description of how they are being used.  In what
> > situation do you obtain the above results?
>
> 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.

For those kind of things I think a large hash is better than tree
structures.
Tree structures are useful when usage has a pattern.

.